题目链接：HDOJ 2844
多重背包，不过没用模板 省事写了二进制
代码：
#include<cstdio> #include<iostream> #include<cstring> #define debug 1 #define M(a) memset(a, 0, sizeof(a)) const int maxn = 100000 + 5; int n, m, f[100005], s[maxn], c[maxn], w[maxn], num; void Do() { for (int i = 1; i< num; i++) for (int j = m; j >= c[i]; j--) { if (f[j - c[i]]) { f[j] = f[j - c[i]] + w[i]; f[j] = 1; } } int ans = 0; for (int i = 1; i <= m; i++) { if (f[i]) ++ans; } printf("%d\n", ans); } int main() { #if debug freopen("in.txt", "r", stdin); #endif //debug int k; while (~scanf("%d%d", &n, &m), m + n) { M(s); M(c); M(w); M(f); for (int i = 1; i <= n; i++) { scanf("%d", &s[i]); } num = 1; for (int i = 1; i <= n; i++) { scanf("%d", &k); int t = 1; while (t <= k) { c[num] = t * s[i]; w[num++] = t * s[i]; k -= t; t *= 2; } c[num] = k * s[i]; w[num++] = k * s[i]; } f[0] = 1; Do(); } return 0; }
