1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include #include #include using namespace std; #define ll long long #define ld long double #define vi vector #define pb push_back #define pii pair #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,(b)) #define maxi(a,b) a=max(a,(b)) #define RE(i,n) for(int i=0,_n=(n);i<_n;++i) #define RI(i,n) for(int i=1,_n=(n);i<=_n;++i) const int inf=1e9+5, nax = 1 << 24; int n, m, MM, t[nax]; int waga[105], poj[105]; int main() { ios_base::sync_with_stdio(0); cin >> n >> m; RE(i, n) cin >> waga[i]; sort(waga, waga + n); waga[n] = inf; RE(i, m) cin >> poj[i]; sort(poj, poj + m); reverse(poj, poj + m); MM = 1 << n; RE(mask, MM) t[mask] = inf; t[0] = 0; RE(plecak_id, min(m, n)) { RE(mask, MM) if(t[mask] != inf) { int wolne = poj[plecak_id] - t[mask]; int memo = t[mask]; for(int k = 0; waga[k] <= wolne; ++k) if((mask & (1 << k)) == 0) { mini(t[mask | (1 << k)], memo + waga[k]); t[mask] = inf; } } if(t[MM - 1] != inf) { cout << plecak_id + 1 << "\n"; return 0; } RE(mask, MM) if(t[mask] != inf) t[mask] = 0; } cout << "NIE\n"; return 0; }