HDU - 2844 - coins (多重背包)
题意：
大壮想买东西，他有n种不同面值的硬币，每种有 $c_i$ 个，他不想找零，也不想买超过价值m的东西，问他有多少种支付方式。$n(1 ≤ n ≤ 100),m(m ≤ 100000)$
分析：
可以发现m的范围不大，直接在m中遍历。转化为给定一个容量为m的背包，问装入不同方案时，不同价值的数量。
显然是一个多重背包，需要使用二进制优化，标记出现过的不同价值即可。
为什么呢？因为求的是m中出现过的价值，那么如果一个价值可以被凑出来，假设为x，那么当背包容量刚好为x时，一定没有比它更优的方案。
const int N = 110;
const int M = 1e5 + 10;
void solve() {
int n, m;
while (cin >> n >> m && n != 0 && m != 0) {
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++)cin >> a[i];
int pos = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
int k = 1;
while (k <= x) {
if (pos > m)break;
v[++pos] = a[i] * k;
x -= k;
k <<= 1;
}
if (x && pos < m) v[++pos] = a[i] * x;
}
for (int i = 1; i <= pos; i++) {
for (int j = m; j >= v[i]; j--) {
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
if (dp[j] > 0)vi[dp[j]]++;
}
}
int ans = 0;
for (int i = 1; i <= m; i++) {
if (vi[i])ans++;
}
cout << ans << endl;
memset(vi, 0, sizeof vi);
}
}