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
56
57
58
59
60
61
62
63
64
65
// kawałek wzięty z http://uwfsucks.blogspot.com/2008/01/generating-all-subsets.html
#include <cstdio>
#include <functional>
#include <algorithm>
#define PRZED 24
#define PLEC 100
using namespace std;
typedef unsigned int uint;
uint a[PRZED];
uint c[PLEC];
uint suma[(1 << PRZED)];
bool dyna[2][(1 << PRZED)];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%u",&a[i]);
    for(int i=0;i<m;i++)scanf("%u",&c[i]);
    sort(c,c+m,greater<uint>());
    
    suma[0]=0;
    uint N=(uint(1) << uint(n));
    for(uint i=1;i<N;i++)
    {
        uint poprz=__builtin_ffs(i)-1;
        suma[i]=a[poprz]+suma[i&(i-1)];
    }
    
    int akt=0;
    int poprz;
    dyna[akt][0]=true;
    for(uint i=1;i<N;i++)
    {
        if(suma[i]<=c[0])dyna[akt][i]=true;
        else dyna[akt][i]=false;
    }
    if(dyna[akt][N-1]){puts("1");return 0;}
    for(int x=1;x<m;x++)
    {
        poprz=akt;
        akt=1-akt;
        
        dyna[akt][0]=true;
        for(uint i=1;i<N;i++)
        {
            dyna[akt][i]=dyna[poprz][i]; // nie bierzemy nic do tego plecaka
            if(dyna[akt][i])continue;
            for(uint subset = i;subset>0; subset = (subset - 1) & i)
            {
                if(suma[subset]>c[x])continue;
                if(dyna[poprz][i^subset])
                {
                    dyna[akt][i]=true;
                    break;
                }
            }
        }
        if(dyna[akt][N-1])
        {
            printf("%d\n",x+1);
            return 0;
        }
    }
    puts("NIE");
}