专题进阶 · 动态规划推荐总顺序 · 第 66 / 148 课

从二维选与不选推到容量倒序,证明每件物品最多使用一次。

先学会这些,再进入本课 一维 DP 二维 DP
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

0/1 背包0/1 Knapsack

每件物品最多选一次;压缩成一维时容量倒序,避免本轮重复使用。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

从二维选与不选推到容量倒序,证明每件物品最多使用一次。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

背包容量 5,物品 (重量,价值) 为 (2,3)、(3,4)、(4,5),每件最多一件,最大价值是多少?

02一步步得到方法

两个维度分别限制可用物品与容量

定义 dp[i][c] 为只用前 i 件物品、总重量不超过 c 的最大价值。第 i 件不选时取上一行 dp[i−1][c];能装下且选择时取 dp[i−1][c−w]+v。

两条依赖都必须来自上一行,因为本件不能重复使用。初始化全零代表允许空选择、不要求恰好装满;如果要求恰好容量,除 dp[0][0] 外应初始化为不可达负无穷。

一维压缩为何要倒着更新

用同一数组覆盖上一行时,从大容量往小容量走。此时 c−w<c 对应位置尚未被本物品更新,仍是上一行状态,所以每件最多使用一次。

若正序更新,刚得到的 dp[c−w] 可能已经用过本件,再加一次 v 就重复选择,变成完全背包语义。循环方向承载了物品使用次数限制。

把一维压缩对应回二维表

二维递推的取物品分支读取上一行:dp[i−1][c−w]+v。一维倒序遍历容量时,c−w 位置尚未被本物品更新,因此仍代表上一行,保持每件最多一次。

若容量正序,较小容量已经用了当前物品,后续又读取它就可能重复使用。用只有一件重量2、价值3、容量4的输入手算,最容易看出错误版本会得到6而正确答案只有3。

03把一个小例子完全算清楚

容量 5,先处理物品 (2,3),再 (3,4)、(4,5)。

步骤计算与状态为什么这样做
第一件后dp=[0,0,3,3,3,3]倒序,不会得到容量 4 价值 6
第二件,c=5max(3,dp[2]+4)=7组合重量 2+3
第三件c=5 候选 dp[1]+5=5不如 7

窄屏可左右滑动表格,阅读完整计算与理由。

答案 7;高价值重量比不是普遍可靠的 0/1 背包选择规则。

04为什么这个方法成立

  1. 按最后一件选或不选穷尽所有合法方案。
  2. 容量倒序保证转移读取不含当前物品的旧状态。
  3. 逐件处理后,dp[c] 就是所有已处理物品在容量 c 下的最优值。

05把推导翻译成代码

Python · 可独立运行的教学实现

def knapsack(items, capacity):
    dp = [0]*(capacity+1)
    for weight,value in items:
        assert weight > 0
        for c in range(capacity, weight-1, -1):
            dp[c] = max(dp[c], dp[c-weight]+value)
    return dp[capacity]

逐个理解关键决定

range(capacity, weight-1, -1)
容量倒序,且包含恰好等于 weight 的位置。
dp[c-weight]+value
取旧行更小容量的最优值,再加入本件。

06时间、空间与实现范围

n 件物品、整数容量 C,时间 O(nC),空间 O(C),称为伪多项式:它依赖 C 数值而非只依赖编码位数。

容量极大时可考虑按价值 DP、折半搜索或其他结构,不能无条件开大数组。

07改变条件,检查哪里会出错

从小到大枚举容量

可能重复使用同一物品,不再是 0/1 背包。

混淆最多装到容量与必须恰好装满

恰好装满时除容量0外应把不可达状态设为 −∞,不能全部初始化为0。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

只有 (2,3),容量 4 应得多少?

需要一点提示

物品只有一件。

查看解析与答案

3;正序错误实现会得到 6。

练习 2 · 边界与辨析

为何全零不适合恰好装满?

需要一点提示

未达到容量也被当作合法 0。

查看解析与答案

需要用负无穷标记不可达,只有容量 0 初值为 0。

练习 3 · 变式与迁移

怎样恢复选择的物品?

需要一点提示

最优值没有保存决策。

查看解析与答案

保留二维表或父状态记录,根据某状态是否来自选择当前物品回溯。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。