·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：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
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;
}