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

写对背包问题的容量遍历顺序

写对背包问题的容量遍历顺序

背包题最容易写错的不是状态转移式,而是容量循环方向。相同的 dp[j] 更新语句,正序会允许本轮再次使用当前物品,逆序则会阻止重复使用。本篇用 0-1、完全和多重背包对照,建立“选择次数决定遍历顺序”的判断方法。

学习目标

  • 根据物品可选次数判断容量应正序还是逆序遍历
  • 解释原地一维 dp 中“读到旧状态还是新状态”的语义差异
  • 写出 0-1、完全和多重背包的可运行实现并验证结果

从状态定义看循环方向

设 dp[j] 表示容量不超过 j 时能够取得的最大价值。处理一件重量为 w、价值为 v 的物品时,核心转移都是:

dp[j]=max⁡(dp[j],dp[j−w]+v)dp[j] = \max(dp[j], dp[j-w] + v)

真正决定语义的是更新 dp[j] 时,右侧 dp[j-w] 来自“处理当前物品之前”还是“处理当前物品之后”。

0-1 背包中,每件物品最多选一次,因此必须让 dp[j-w] 仍是上一轮物品集合的结果。容量从大到小遍历时,较小容量尚未被当前物品更新,正好满足这个要求。

完全背包中,同一件物品可以重复选择,因此希望 dp[j-w] 已经包含当前物品。容量从小到大遍历时,较小容量先更新,后续容量就能继续基于它追加同一件物品。

0-1 与完全背包容量遍历语义对比

三类背包如何选择顺序

可以先问“当前物品最多能被选几次”,再决定实现方式。

类型 单件物品可选次数 一维容量遍历 原因
0-1 背包 0 或 1 次 从大到小 防止本轮重复使用当前物品
完全背包 任意次 从小到大 允许读取本轮刚更新的新状态
多重背包 0 到 count 次 视拆分方式而定 先把数量约束转成若干 0-1 组或显式枚举数量

多重背包不能简单理解为“正序或逆序二选一”。如果把数量为 count 的物品拆成若干个只能选一次的组合包,每个组合包都按 0-1 背包逆序更新;若直接枚举选择个数,则由额外循环保证不超过上限。

用同一组数据验证差异

下面的程序分别实现 0-1、完全和多重背包。三者使用同样的 dp[j] 思路,但通过循环方向或数量拆分表达不同限制。

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

预期输出

text
0-1: 7
complete: 9
bounded: 7

容量为 6 时,0-1 背包只能各取一次,最大价值是 7;完全背包可以把重量 2、价值 3 的物品取三次,得到 9;多重背包把第一种物品限制为最多两次,因此又回到 7。这个结果正好说明循环方向和数量限制共同决定了“当前物品能否被重复使用”。

用依赖关系排查写错方向

遇到背包题时,不必死记模板,可以按下面顺序判断:

  1. 明确 dp[j] 的含义,是“恰好装满”还是“容量不超过”,以及存的是最大值、最小值还是方案数。
  2. 判断每种选择是否只能用一次、可无限使用,还是有固定次数上限。
  3. 若使用一维原地数组,检查右侧状态在本轮是否应该已经包含当前物品。
  4. 只能用一次时让依赖指向旧状态,通常逆序;可重复使用时允许依赖新状态,通常正序。
  5. 有数量上限时先把“最多几次”约束显式编码,再决定内部采用哪种遍历。

当你能用“本轮是否允许再次读到当前物品”解释循环方向时,0-1 与完全背包就不再是两套需要死记的模板,而是同一个状态压缩原则的两种语义。

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

目录与阅读设置

阅读设置

17

记录一个想法

写对背包问题的容量遍历顺序

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

登录哪都通