数据结构与算法 / 系统课时

让物品可以重复进入背包

让物品可以重复进入背包

完全背包与零一背包只有一个关键差异:同一种物品可以重复选择。这个变化会直接改变一维 DP 的读取规则。只要允许当前轮读取刚更新的状态,就能让同一物品继续累加,因此容量遍历方向要从逆序改为正序。

学习目标

  • 理解完全背包“同一物品可重复使用”的状态语义
  • 从状态依赖推导容量正序遍历,而不是死记模板
  • 区分零一背包与完全背包的一维更新方式

重复选择改变了依赖来源

仍然设 dp[c] 表示容量不超过 c 时能取得的最大价值。处理重量为 w、价值为 v 的当前物品时,转移仍可写成:

dp[c]=max⁡(dp[c], dp[c−w]+v)dp[c] = \max(dp[c],\ dp[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。

python
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))

预期输出

text
10

一种最优组合是选择两件重量 2、一件重量 3 的物品,总重量为 7,总价值为 3 + 3 + 4 = 10。

与零一背包对照

两类问题的状态定义可以完全一致,真正变化的是“当前阶段能不能复用自己刚产生的结果”。

模型 当前物品使用次数 容量遍历 dp[c-w] 的语义
零一背包 最多一次 从大到小 本轮更新前的旧状态
完全背包 可重复 从小到大 可以是本轮刚更新的新状态

如何判断题目属于完全背包

看到“硬币可重复使用”“商品数量不限”“步长可以使用任意次”这类描述时,应检查是否存在容量、金额、长度或次数上限,并且每种选择可以反复取用。如果是,就可以考虑完全背包。

还要区分“求最大价值”和“求方案数”。前者通常使用 max 转移;后者会改成加法累计,并且物品与容量的循环顺序还可能决定是在数“组合”还是“排列”。因此,本节应掌握的不是某一段固定代码,而是一个判断原则:是否允许读取同一轮刚更新的状态,决定了当前物品能否被重复使用。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

让物品可以重复进入背包

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通