数据结构与算法 / 系统课时
写对背包问题的容量遍历顺序
写对背包问题的容量遍历顺序
背包题最容易写错的不是状态转移式,而是容量循环方向。相同的 dp[j] 更新语句,正序会允许本轮再次使用当前物品,逆序则会阻止重复使用。本篇用 0-1、完全和多重背包对照,建立“选择次数决定遍历顺序”的判断方法。
学习目标
- 根据物品可选次数判断容量应正序还是逆序遍历
- 解释原地一维
dp中“读到旧状态还是新状态”的语义差异 - 写出 0-1、完全和多重背包的可运行实现并验证结果
从状态定义看循环方向
设 dp[j] 表示容量不超过 j 时能够取得的最大价值。处理一件重量为 w、价值为 v 的物品时,核心转移都是:
真正决定语义的是更新 dp[j] 时,右侧 dp[j-w] 来自“处理当前物品之前”还是“处理当前物品之后”。
0-1 背包中,每件物品最多选一次,因此必须让 dp[j-w] 仍是上一轮物品集合的结果。容量从大到小遍历时,较小容量尚未被当前物品更新,正好满足这个要求。
完全背包中,同一件物品可以重复选择,因此希望 dp[j-w] 已经包含当前物品。容量从小到大遍历时,较小容量先更新,后续容量就能继续基于它追加同一件物品。

三类背包如何选择顺序
可以先问“当前物品最多能被选几次”,再决定实现方式。
| 类型 | 单件物品可选次数 | 一维容量遍历 | 原因 |
|---|---|---|---|
| 0-1 背包 | 0 或 1 次 | 从大到小 | 防止本轮重复使用当前物品 |
| 完全背包 | 任意次 | 从小到大 | 允许读取本轮刚更新的新状态 |
| 多重背包 | 0 到 count 次 |
视拆分方式而定 | 先把数量约束转成若干 0-1 组或显式枚举数量 |
多重背包不能简单理解为“正序或逆序二选一”。如果把数量为 count 的物品拆成若干个只能选一次的组合包,每个组合包都按 0-1 背包逆序更新;若直接枚举选择个数,则由额外循环保证不超过上限。
用同一组数据验证差异
下面的程序分别实现 0-1、完全和多重背包。三者使用同样的 dp[j] 思路,但通过循环方向或数量拆分表达不同限制。
def zero_one_knapsack(capacity, items):
dp = [0] * (capacity + 1)
for weight, value in items:
# 逆序保证当前物品不会在同一轮被再次读取。
for j in range(capacity, weight - 1, -1):
dp[j] = max(dp[j], dp[j - weight] + value)
return dp[capacity]
def complete_knapsack(capacity, items):
dp = [0] * (capacity + 1)
for weight, value in items:
# 正序允许后续容量复用本轮刚得到的新状态。
for j in range(weight, capacity + 1):
dp[j] = max(dp[j], dp[j - weight] + value)
return dp[capacity]
def bounded_knapsack(capacity, items):
expanded = []
for weight, value, count in items:
k = 1
while count > 0:
take = min(k, count)
expanded.append((weight * take, value * take))
count -= take
k *= 2
return zero_one_knapsack(capacity, expanded)
if __name__ == "__main__":
capacity = 6
base_items = [(2, 3), (3, 4)]
bounded_items = [(2, 3, 2), (3, 4, 1)]
print("0-1:", zero_one_knapsack(capacity, base_items))
print("complete:", complete_knapsack(capacity, base_items))
print("bounded:", bounded_knapsack(capacity, bounded_items))预期输出
0-1: 7
complete: 9
bounded: 7容量为 6 时,0-1 背包只能各取一次,最大价值是 7;完全背包可以把重量 2、价值 3 的物品取三次,得到 9;多重背包把第一种物品限制为最多两次,因此又回到 7。这个结果正好说明循环方向和数量限制共同决定了“当前物品能否被重复使用”。
用依赖关系排查写错方向
遇到背包题时,不必死记模板,可以按下面顺序判断:
- 明确
dp[j]的含义,是“恰好装满”还是“容量不超过”,以及存的是最大值、最小值还是方案数。 - 判断每种选择是否只能用一次、可无限使用,还是有固定次数上限。
- 若使用一维原地数组,检查右侧状态在本轮是否应该已经包含当前物品。
- 只能用一次时让依赖指向旧状态,通常逆序;可重复使用时允许依赖新状态,通常正序。
- 有数量上限时先把“最多几次”约束显式编码,再决定内部采用哪种遍历。
当你能用“本轮是否允许再次读到当前物品”解释循环方向时,0-1 与完全背包就不再是两套需要死记的模板,而是同一个状态压缩原则的两种语义。