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
#include <cstdio>
#include <algorithm>
#include <functional>

const int MAXN = 25, MAXM = 101, INF = 1000000;
int n,m,items[MAXN],bags[MAXM],results[(1<<MAXN)][2];

void init();

int main()
{
	scanf("%d%d", &n, &m);
	init();
	for(int i = 0; i < n; ++i)
		scanf("%d", &items[i]);
	for(int i = 0; i < m; ++i)
		scanf("%d", &bags[i]);
	
	std::sort(bags,bags+m,std::greater<int>());
	std::sort(items,items+n,std::greater<int>());

	int newState;
	results[0][0] = 0; results[0][1] = 0;
	for(int i = 0; i < (1<<n); ++i)
	{
		if(results[i][0] == INF) continue;
		for(int j = 0; j < n; ++j)
		{
			if( (i & (1<<j)) > 0) continue;
			newState = (i | (1 << j));
			if( results[i][1] + items[j] > bags[results[i][0]-1] ) // trzeba dodać nowy plecak
			{
				if(results[i][0] >= std::min(n,m)) break;
				if(items[j] > bags[results[i][0]]) break;
				if(results[newState][0] > results[i][0] + 1)
				{
					results[newState][0] = results[i][0] + 1;
					results[newState][1] = items[j];
				}
				else if(results[newState][0] == results[i][0] + 1)
					results[newState][1] = std::min(results[newState][1],items[j]);
			}
			else
			{
				if(results[newState][0] > results[i][0])
				{
					results[newState][0] = results[i][0];
					results[newState][1] = results[i][1]+items[j];
				}
				else if(results[newState][0] == results[i][0])
					results[newState][1] = std::min(results[newState][1],results[i][1]+items[j]);
			}
		}
	}

	if(results[(1<<n)-1][0] == INF) printf("NIE\n");
	else printf("%d\n", results[(1<<n)-1][0]);
}

void init()
{
	for(int i = 0; i < (1<<n); ++i)
		results[i][0] = INF;
}