回顾三种传统背包问题
前面我们已经学完了三种传统背包问题了。
这里再回顾一下三种传统背包：
- 01 背包：强调每件物品**「只能选择一次」。对其进行「一维空间优化」并不能降低时间复杂度，进行「一维空间优化」时要求「容量维度“从大到小”进行遍历」**。
- 完全背包：强调每件物品**「可以选择无限次」。对其进行「一维空间优化」具有数学意义，可以将时间复杂度从 降低到 ，进行「一维空间优化」时要求「容量维度“从小到大”进行遍历」**。
- 多重背包：强调每件物品**「只能选择有限次」**。对其无论是进行「一维空间优化」还是「普通扁平化」都不能降低时间复杂度，要应用额外的优化手段：二进制优化 或 单调队列优化 。
三种背包问题的**「难易程度」是「递增」，但「重要程度」则是「递减」** 的。
虽然「多重背包」的 二进制优化 和 单调队列优化 都比较 trick。
但其实「多重背包」并没有这么常见，以至于在 LeetCode 上我都没找到与「多重背包」相关的题目。
同时三种背包问题都有**「不超过」和「恰好」**两种状态定义。
这两种状态定义只在「初始化」上有区别。
至于该如何初始化则要抓住 什么样的状态是合法的 ：
- 对于「不超过」的状态定义： 均为合法值 。
代表不考虑任何物品，背包容量「不超过 」的所取得的最大价值为 。 - 对于「恰好」的状态定义： 中只有 为合法值 ，其他值均为“无效值”。
代表不考虑任何物品，只有背包容量「恰好为 」时所取得的最大价值为 ；其他容量「恰好为非 」是无法取得有效价值的（因为不考虑任何物品）。
总的来说，三种背包问题都很经典（本质上都是组合优化问题），以至于「背包问题」直接成为了一类的动态规划模型。
我的建议是三种背包都需要掌握。但如果实在要分侧重点的话，我更愿意你将大多数时间花在「01 背包」和「完全背包」上。
混合背包
给定物品数量 和背包容量 。第 件物品的体积是 ，价值是 ，可用数量为 ：
- 当 为 代表是该物品只能用一次
- 当 为 代表该物品可以使用无限次
- 当 为任意正整数则代表可用 次
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本分析
混合背包其实就是综合了「01 背包」、「完全背包」和「多重背包」三种传统背包问题。
我们知道在一维空间优化方式中「01 背包」将当前容量 按照“从大到小”进行遍历，而「完全背包」则是将当前容量 按照“从小到大”进行遍历。
同时「多重背包」可以通过「二进制优化」彻底转移成「01 背包」。
所以我们只需要根据第 个物品是「01 背包」物品还是「完全背包」物品，选择不同的遍历顺序即可。
代码：
class Solution { public int maxValue(int N, int C, int[] w, int[] v, int[] s) { // 构造出物品的「价值」和「体积」列表 List<Integer> worth = new ArrayList<>(); List<Integer> volume = new ArrayList<>(); for (int i = 0; i < N; i++) { int type = s[i]; // 多重背包：应用「二进制优化」转换为 0-1 背包问题 if (type > 0) { for (int k = 1; k <= type; k *= 2) { type -= k; worth.add(w[i] * k); volume.add(v[i] * k); } if (type > 0) { worth.add(w[i] * type); volume.add(v[i] * type); } // 01 背包：直接添加 } else if (type == -1) { worth.add(w[i]); volume.add(v[i]); // 完全背包：对 worth 做翻转进行标记 } else { worth.add(-w[i]); volume.add(v[i]); } } // 使用「一维空间优化」方式求解三种背包问题 int[] dp = new int[C + 1]; for (int i = 0; i < worth.size(); i++) { int wor = worth.get(i); int vol = volume.get(i); // 完全背包：容量「从小到大」进行遍历 if (wor < 0) { for (int j = vol; j <= C; j++) { // 同时记得将 worth 重新翻转为正整数 dp[j] = Math.max(dp[j], dp[j - vol] - wor); } // 01 背包：包括「原本的 01 背包」和「经过二进制优化的完全背包」 // 容量「从大到小」进行遍历 } else { for (int j = C; j >= vol; j--) { dp[j] = Math.max(dp[j], dp[j - vol] + wor); } } } return dp[C]; } } 复制代码
就这样我们解决了这个混合背包问题。
先将一个「多重背包」问题通过「二进制优化」的思路，转化为「01 背包」问题。
然后根据物品是属于「01 背包」还是「完全背包」决定容量 是"从大到小"还是"从小到大"进行推算。
换句话说就是根据物品的类型不同，选择不同的转移方式。
总结
今天我们在学习「混合背包」之前先梳理了前面学的三种传统背包问题。
三种传统背包的主要区别在于「物品可被选择的次数」，其中「01 背包」的一维空间的优化方式是其余背包问题的基础。
对于「完全背包」和「多重背包」而言，一个可以选择「任意个数的物品」，另外一个则存在「选择物品的上界」。
这导致这两种背包问题在转移某个 时，其实本质是分别在求「整个前缀的最值」和「滑动窗口的最值」。
这就意味着「完全背包」可以直接通过一维空间优化降低时间复杂度；而「多重背包」则要通过「二进制优化」（减少总的物品数量）或者「单调队列优化」（实现直接求得滑动窗口最值）来降低时间复杂度。
背包问题（目录）
- 01背包 : 背包问题 第一讲
- 【练习】01背包 : 背包问题 第二讲
- 多重背包 : 背包问题 第八讲
- 多重背包（优化篇）
- 【练习】分组背包 : 背包问题 第十三讲
- 多维背包 : 背包问题 第十四讲
- 【练习】多维背包
- 树形背包
- 【练习篇】树形背包
- 背包求方案数
- 【练习】背包求方案数
- 背包求具体方案
- 【练习】背包求具体方案
- 泛化背包
- 【练习】泛化背包
最后
到这一节结束，我们就已经完成「背包问题」的第一阶段的学习了 🎉 🎉
接下来的「背包问题」更多的偏向于「多维」、「分组」、「有依赖」、「求方案数/具体方案」此类问题。
这类问题往往才是真正用来考察「背包思维」的题目，第一阶段的学习更多的是模板题，打基础用的。
继续加油吧 ~
