# PBinfo #4266 – MITM – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Fie un număr natural s și un șir de n numere naturale nenule. Să se determine suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.

Date de intrare
Programul citește de la tastatură numărul n și s, apoi n numere naturale, separate prin spații, reprezentând elementele șirului.

Date de ieșire
Programul va afișa pe ecran numărul M, reprezentând suma maximă posibilă, mai mică sau egală cu s ce se poate obține dintr-un subșir al șirului.

Restricții și precizări

3 ≤ n ≤ 40
1 ≤ s ≤ 2.000.000.000
Șirul va conține numere naturale nenule mai mici decât 50.000.001.
Toate elementele șirului vor fi mici sau egale decât s.

Exemplul 1:
Intrare

5 20
5 10 6 8 3
Ieșire

19
Explicație
Suma maximă mai mică sau egală decât 20 este 19 și se formează din 10, 6 și 3.

Exemplul 2:
Intrare

5 20
17 16 10 12 14
Ieșire

17
Explicație
Suma maximă mai mică sau egală decât 20 este 17 și se formează doar din numărul 17.

## Cod sursă C++

```cpp
// solutie Meet in the Middle
#include <bits/stdc++.h>
#define nmax 1050000
using namespace std;
int a[23], b[23], n, na, nb, s, M;
int x[nmax], y[nmax], nx, ny;
void Citire()
{
    int i;
    cin >> n >> s;
    na = n / 2;
    for (i = 1; i <= na; i++)
        cin >> a[i];
    nb = 0;
    for (i = na + 1; i <= n; i++)
    {
        nb++;
        cin >> b[nb];
    }
}
void Subsets(int a[], int n, int x[], int &nx)
{
    int i, suma;
    int t[23] = {0};
    nx = 0;
    while (t[0] == 0)
    {
        suma = 0;
        for (i = 1; i <= n; i++)
            if (t[i] == 1) suma += a[i];
        x[++nx] = suma;
        for (i = n; t[i] == 1; i--)
            t[i] = 0;
        t[i] = 1;
    }
}
void Rezolvare()
{
    int i, j;
    M = 0;
    sort(x + 1, x + nx + 1);
    sort(y + 1, y + ny + 1);
    for (i = 1; i <= nx && x[i] <= s; i++)
        if (M < x[i]) M = x[i];
    for (i = 1; i <= ny && y[i] <= s; i++)
        if (M < y[i]) M = y[i];
    j = ny;
    for (i = 1; i <= nx; i++)
    {
        while (j >= 1 && x[i] + y[j] > s)
            j--;
        if (j >= 1) M = max(M, x[i] + y[j]);
    }
    cout << M;
}
int main()
{
    Citire();
    Subsets(a, na, x, nx);
    Subsets(b, nb, y, ny);
    Rezolvare();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4266)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4266/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4266/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)