数据结构与算法 / 系统课时
让物品可以重复进入背包
让物品可以重复进入背包
完全背包与零一背包只有一个关键差异:同一种物品可以重复选择。这个变化会直接改变一维 DP 的读取规则。只要允许当前轮读取刚更新的状态,就能让同一物品继续累加,因此容量遍历方向要从逆序改为正序。
学习目标
- 理解完全背包“同一物品可重复使用”的状态语义
- 从状态依赖推导容量正序遍历,而不是死记模板
- 区分零一背包与完全背包的一维更新方式
重复选择改变了依赖来源
仍然设 dp[c] 表示容量不超过 c 时能取得的最大价值。处理重量为 w、价值为 v 的当前物品时,转移仍可写成:
公式表面与零一背包相同,差异在于 dp[c-w] 应该来自哪里。完全背包允许再次使用当前物品,所以希望 dp[c-w] 可以是本轮已经更新后的状态。这样它内部即使已经包含当前物品,也可以继续加一个 v。

正序遍历如何产生重复使用
使用重量 2、价值 3 的物品举例。容量正序扫描时,先得到 dp[2] = 3;之后计算 dp[4],会读取已经更新后的 dp[2],于是得到 6;继续到 dp[6],又能基于 dp[4] 得到 9。
这条更新链实际上就是“同一种物品再拿一次”。因此,完全背包恰恰需要利用同一轮的新状态。
下面给出完整示例。物品重量为 2、3,价值为 3、4,容量为 7。
def complete_knapsack(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# 正序允许读取本轮已更新的 dp[c - w],从而重复使用当前物品
for c in range(w, capacity + 1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
weights = [2, 3]
values = [3, 4]
print(complete_knapsack(weights, values, 7))预期输出
10一种最优组合是选择两件重量 2、一件重量 3 的物品,总重量为 7,总价值为 3 + 3 + 4 = 10。
与零一背包对照
两类问题的状态定义可以完全一致,真正变化的是“当前阶段能不能复用自己刚产生的结果”。
| 模型 | 当前物品使用次数 | 容量遍历 | dp[c-w] 的语义 |
|---|---|---|---|
| 零一背包 | 最多一次 | 从大到小 | 本轮更新前的旧状态 |
| 完全背包 | 可重复 | 从小到大 | 可以是本轮刚更新的新状态 |
如何判断题目属于完全背包
看到“硬币可重复使用”“商品数量不限”“步长可以使用任意次”这类描述时,应检查是否存在容量、金额、长度或次数上限,并且每种选择可以反复取用。如果是,就可以考虑完全背包。
还要区分“求最大价值”和“求方案数”。前者通常使用 max 转移;后者会改成加法累计,并且物品与容量的循环顺序还可能决定是在数“组合”还是“排列”。因此,本节应掌握的不是某一段固定代码,而是一个判断原则:是否允许读取同一轮刚更新的状态,决定了当前物品能否被重复使用。