Coins
题面
给定 N 种硬币，其中第 i 种硬币的面值为 \(A_i\)，共有 \(C_i\) 个。
从中选出若干个硬币，把面值相加，若结果为 S，则称“面值 S 能被拼成”。
求 1∼M 之间能被拼成的面值有多少个。
\(1 \le N \le 100\)
\(1 \le M \le 10^5\)
\(1 \le A_i \le 10^5\)
\(1 \le C_i \le 1000\)
题解
这道题是个典型的多重背包题目，我们可以设 \(f(j)\) 表示考虑前 \(i\) 个硬币的情况下，\(j\) 这个面额能否被拼出来，如果暴力的将每个硬币拆分成 \(C_i\) 个硬币的话，时间复杂度为 \(O(M\sum C_i)\) ，是不能接受的
给出两种优化方案，第一种是二进制拆分法优化多重背包，时间复杂度为 \(O(M\sum \log C_i)\) ，第二种是单调队列优化多重背包，时间复杂度为 \(O(NM)\)
蓝书中还给了一种巧妙的解决方法（
对于一个面值 \(j\) ，如果它能够被拼成，那么有两种情况
- 在不使用硬币 \(i\) 的就已经能够被拼成
- 使用硬币 \(i\) ，在某一次枚举中 \(f(j - a_i) = 1\)
回忆完全背包的枚举过程，我们正序枚举，这样 \(f(j - a_i)\) 这个状态就有可能是用过 \(i\) 的，从而实现无限次使用的效果
但我们并不能让它无限次使用，而是要限制一个使用次数 \(C_i\) ，如果我们知道前面的状态 \(f(j - a_i)\) 最少用了几个 \(i\) ，那么我们也就能推出当前 \(j\) 要想被拼成，至少要用几个 \(i\)
于是我们可以用一个数组 \(used_j\) 表示要拼成 \(j\) ，至少需要用多少 \(i\)
那么就有转移 \(f(j) |= f(j - a_i),used(j) = used(j - a_i) + 1\)
时间复杂度为 \(O(NM)\)
code
二进制拆分优化多重背包
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 110, M = 1e5 + 10;int n, m;
int a[N], c[N], used[M];
int w[N * 10], tot;
bool f[M];void init () {tot = 0;for (int i = 1; i <= n; i++) {for (int j = 0; j <= 10; j++) {if (c[i] >= (1 << j)) {tot ++;w[tot] = (1 << j) * a[i];c[i] -= (1 << j);} else break;}if (c[i]) {tot ++;w[tot] = c[i] * a[i];}}
}int main () {while (cin >> n >> m && n && m) {for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> c[i];init ();f[0] = 1;for (int i = 1; i <= tot; i ++) {for (int j = m; j >= w[i]; j --) {f[j] |= f[j - w[i]];}}int ans = 0;for (int i = 1; i <= m; i ++) {ans += f[i];f[i] = 0;}cout << ans << endl;}return 0;
}
单调队列优化多重背包
//这个代码比妈二进制拆分还慢，卡半天没过 POJ
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bitset>using namespace std;const int N = 110, M = 1e5 + 10;int n, m, w[N], c[N];
int q1[M], q2[N], h, t;
bool f[M];int main () {while (cin >> n >> m && n && m) {for (int i = 1; i <= n; i ++) {cin >> w[i];}for (int i = 1; i <= n; i ++) {cin >> c[i];}f[0] = 1;for (int i = 1; i <= n; i ++) {for (int j = 0; j < w[i]; j ++) {h = 1, t = 0;for (int k = j; k <= m; k += w[i]) {while (h <= t && q1[h] < k - w[i] * c[i]) h ++;if (f[k]) q1[++ t] = k, q2[t] = f[k];if (h <= t && q2[h]) f[k] = 1;}}}int ans = 0;for (int i = 1; i <= m; i ++) {ans += f[i];f[i] = 0;}cout << ans << '\n';}return 0;
}
巧妙的转化
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 110, M = 1e5 + 10;int n, m;
int a[N], c[N], used[M];
bool f[M];int main () {while (cin >> n >> m && n && m) {for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> c[i];f[0] = 1;for (int i = 1; i <= n; i ++) {for (int j = 0; j <= m; j ++) {used[j] = 0;}for (int j = a[i]; j <= m; j ++) {if (!f[j] && used[j - a[i]] < c[i]) {f[j] |= f[j - a[i]];used[j] = used[j - a[i]] + 1;}}}int ans = 0;for (int i = 1; i <= m; i ++) {ans += f[i];f[i] = 0;}cout << ans << endl;}return 0;
}