背包问题是算法学习中的经典问题，也是面试中的常客。今天我们就来聊聊几个常见的背包问题：0-1背包、完全背包、多重背包和分组背包。不用担心，我会用最简单的方式带你理解它们！
一、0-1背包问题：选还是不选？
问题描述
想象你有一个容量为V的背包，面前有N件物品，每件物品有自己的重量w[i]和价值v[i]。你的任务是选择一些物品放入背包，使得背包里的物品总价值最大。注意：每件物品只能选一次！
解决思路
我们可以用一个表格来记录不同情况下的最大价值。假设dp[i][j]表示前i件物品放入容量为j的背包时的最大价值。
关键点：每件物品有两种选择——选或不选。
- 不选：当前物品的价值
(dp[i-1][j])与前i-1件物品的结果相同。 - 选：如果当前物品的重量不超过背包容量，那么选它可以获得更大的价值：
dp[i-1][j-w[i]] + v[i]。
用公式表示就是：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
一维数组优化的原理
由于二维数组的空间可能较大，我们可以使用滚动数组来优化。逆序遍历是为了防止多次选择同一物品，例如：
- 当处理第
i件物品时，如果正序遍历，前面的j - w[i]可能已经加上了当前物品，导致物品被多次选择。
优化后的代码实现如下：
def zero_one_pack(N, V, w, v):dp = [0] * (V + 1)for i in range(N):for j in range(V, w[i] - 1, -1):if dp[j] < dp[j - w[i]] + v[i]:dp[j] = dp[j - w[i]] + v[i]return dp[V]
小提示：逆序遍历是为了防止同一件物品被多次选择。
示例
| 物品编号 | 重量 (w) | 价值 (v) |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
初始化dp数组
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 0 | 0 | 0 | 0 |
更新过程
处理物品1 (w=2, v=3)
从后往前遍历，j从5到2：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 3 | 3 | 3 |
处理物品2 (w=3, v=4)
从后往前遍历，j从5到3：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 4 | 7 | 7 |
处理物品3 (w=4, v=5)
从后往前遍历，j从5到4：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 4 | 7 | 8 |
最终结果：dp[5] = 8，即最大价值为8。
二、完全背包问题：无限选择！
问题描述
和0-1背包类似，但这次每件物品可以选择无数次！
解决思路
物品可无限选，因此，在遍历到当前物品时，容量j可以重复利用之前更新过的结果。为了允许多次选择，需从前往后遍历容量。
示例：
- 物品
i重量为1，价值为2。容量为3时：j=1:dp[1] = max(0, dp[0]+2) = 2j=2:dp[2] = max(0, dp[1]+2=4)j=3:dp[3] = max(0, dp[2]+2=6)，相当于选择了3次该物品。
只有正序遍历才能允许每次选择时使用已更新的最大值。
代码实现：
def complete_pack(N, V, w, v):dp = [0] * (V + 1)for i in range(N):for j in range(w[i], V + 1):dp[j] = max(dp[j], dp[j - w[i]] + v[i])return dp[V]
示例
| 物品编号 | 重量 (w) | 价值 (v) |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
初始化dp数组
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 0 | 0 | 0 | 0 |
更新过程
处理物品1 (w=2, v=3)
从前往后遍历，j从2到5：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 6 | 9 | 12 |
处理物品2 (w=3, v=4)
从前往后遍历，j从3到5：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 6 | 9 | 13 |
处理物品3 (w=4, v=5)
从前往后遍历，j从4到5：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 6 | 9 | 14 |
最终结果：dp[5] = 14，即最大价值为14。
三、多重背包问题：有限次选择
问题描述
这次每件物品最多只能选s[i]次。
解决思路
直接将每个物品拆分为多个单位（如s[i]次），但这样效率较低。优化技巧——二进制拆分：
将物品数量拆分为二进制形式，例如，s[i] = 13 → 拆分成1, 2, 4, 6（1+2+4=7，剩余6），这样可以覆盖所有可能的选择次数。然后使用0-1背包的思路处理这些拆分后的物品。
代码实现：
def multi_pack(N, V, w, v, s):dp = [0] * (V + 1)for i in range(N):# 二进制拆分物品k = 1while k <= s[i]:# 添加拆分后的物品weight = w[i] * kvalue = v[i] * kfor j in range(V, weight - 1, -1):dp[j] = max(dp[j], dp[j - weight] + value)s[i] -= kk *= 2# 处理剩余部分if s[i] > 0:weight = w[i] * s[i]value = v[i] * s[i]for j in range(V, weight - 1, -1):dp[j] = max(dp[j], dp[j - weight] + value)return dp[V]
示例
| 物品编号 | 重量 (w) | 价值 (v) | 数量(s) |
|---|---|---|---|
| 1 | 2 | 3 | 2 |
| 2 | 3 | 4 | 1 |
| 3 | 4 | 5 | 2 |
初始化dp数组
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 0 | 0 | 0 | 0 |
更新过程（二进制拆分）
处理物品1 (w=2, v=3, s=2)
二进制拆分：1个和1个
从后往前遍历，j从5到2：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 3 | 6 | 6 |
处理物品2 (w=3, v=4, s=1)
从后往前遍历，j从5到3：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 4 | 6 | 7 |
处理物品3 (w=4, v=5, s=2)
二进制拆分：1个和1个
从后往前遍历，j从5到4：
| 背包容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
dp[j] | 0 | 0 | 3 | 4 | 7 | 9 |
最终结果：dp[5] = 9，即最大价值为9。
四、分组背包问题：每组只能选一个
问题描述
物品被分成了K组，每组物品中只能选一个。
解决思路
遍历每组时，对背包容量逆序更新。在每组中，遍历该组的每个物品，同时更新状态。这样，在处理当前组时，后续的处理不会覆盖当前组的信息，确保同组物品仅选一个。
代码实现：
def group_pack(K, V, groups):dp = [0] * (V + 1)for group in groups:for j in range(V, -1, -1):for w, v in group:if j >= w:dp[j] = max(dp[j], dp[j - w] + v)return dp[V]
五、总结对比
| 背包类型 | 物品限制 | 遍历顺序 | 时间复杂度 |
|---|---|---|---|
| 0-1背包 | 每个物品选1次 | 逆序 | O(NV) |
| 完全背包 | 物品无限 | 正序 | O(NV) |
| 多重背包 | 物品选s[i]次 | 二进制拆分优化 | O(NVlogS) |
| 分组背包 | 每组选一个物品 | 组外逆序 | O(KV*M) |
六、实战应用
- 0-1背包：投资组合选择、资源分配。
- 完全背包：零钱兑换问题。
- 多重背包：原材料切割问题。
- 分组背包：课程选修问题。