其他背包问题简单总结
1.完全背包
0/1背包问题：
已知有第 \(i\) 个物品的重量 \(w_{i}\)，价值 \(v_{i}\)，以及背包的总容量 \(W\)。
设 DP 状态 \(f_{i,j}\) 为在只能放前 \(i\) 个物品的情况下，容量为 \(j\) 的背包所能达到的最大总价值。
而完全背包，即是在\(0/1\)背包问题中，将一个物品只可以选取\(1\)次改为无限次。
从\(0/1\)背包的学习中，可以知道他的状态转移方程为：
\[f_j=\max \left(f_j,f_{j-w_i}+v_i\right) \]它的枚举顺序是从右向左枚举，因为如果从左到右枚举，\(f_j\) 会被 \(f_{j-w_i}\) 影响，会出现一个物品重复拿多次的情况，而完全背包正好可以重复选取，所以完全背包的状态转移方程和\(0/1\)背包的状态转移方程相同，但是枚举顺序变成了从左向右，代码如下：
for (int i = 1; i <= m; i++)
for (int j = w[i]; j <= W; j++) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
cout << dp[W];
2.多重背包
问题：
多重背包，即是在\(0/1\)背包的基础上，将一个物品只可以选取\(1\)次改为 \(s_i\) 次
考虑将多重背包转换为\(0/1\)背包问题，可以将一个物品选取 \(s_i\) 次转换为有 $ s_i$ 个相同的物品，每个物品选一次
代码如下：
for (int i = 1; i <= n; i++)
for (int k = 1; k <= s[i]; k++)
for (int j = m; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
二进制分组优化：
\(0\) ~ \(s_i\) 的枚举时间复杂度实在是太高了，我们可以考虑将物品数量分组。
考虑将 \(s_i\) 分成 \(2^{j}\) 组，如果最后一个分解不彻底，需要添加上剩下的。
比如：
\(5 = 1 + 2 + 3\)
\(11 = 1 + 2 + 4 + 4\)
\(16 = 1 + 2 + 4 + 8 + 1\)
\(63 = 1 + 2 + 4 + 8 + 16 + 32\)
具体代码实现：
for (int i = 1; i <= n; i++) {
cin >> a >> b >> num;
for (int j = 1; j <= num; j *= 2) {
num -= j;
w[++cnt] = a * j;
c[cnt] = b * j;
}
if (num) {
w[++cnt] = a * num;
c[cnt] = b * num;
}
} //二进制分组优化
for (int i = 1; i <= cnt; i++)
for (int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]); //0/1背包直接求解即可
3.混合背包
就是把前面学过的各种背包组合一下，可能有的取\(1\)次，有的无限次， 有的 \(s_i\) 次，需要判断是哪个背包，代码略。