HDU2844 (Coins)[背包]

发表于 | 更新于 | 0 Comments | 阅读次数： 128

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844
这题可以转化为多重背包问题，套用二进制优化即可，可以参考《背包九讲》。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn = 100 + 10;
const int maxm = 100000 + 10;

bool f[maxm];
int a[maxn], c[maxn];
int n, m;
int main() {
	while(scanf("%d%d", &n, &m) != EOF) {
		if(n==0 && m==0) break;
		memset(f, 0, sizeof(f));
		for(int i = 1; i <= n; i++) 
			scanf("%d", a + i);
		for(int i = 1; i <= n; i++) 
			scanf("%d", c + i);
		f[0] = 1;
		for(int i = 1; i <= n; i++) {
			int k = 1;
			while(c[i] > 0) {
				int w = std::min(k, c[i]) * a[i];
				for(int j = m; j >= w; j--) 
					f[j] |= f[j-w];
				c[i] -= k; 
				k <<= 1;
			}
		}
		int ans = 0;
		for(int i = 1; i <= m; i++)
			if (f[i]) ans++;
		printf("%d\n", ans);
	}
	return 0;
}