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=5 | max(3,dp[2]+4)=7 | 组合重量 2+3 |
| 第三件 | c=5 候选 dp[1]+5=5 | 不如 7 |
窄屏可左右滑动表格,阅读完整计算与理由。
答案 7;高价值重量比不是普遍可靠的 0/1 背包选择规则。
04为什么这个方法成立
- 按最后一件选或不选穷尽所有合法方案。
- 容量倒序保证转移读取不含当前物品的旧状态。
- 逐件处理后,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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
只有 (2,3),容量 4 应得多少?
需要一点提示
物品只有一件。
查看解析与答案
3;正序错误实现会得到 6。
为何全零不适合恰好装满?
需要一点提示
未达到容量也被当作合法 0。
查看解析与答案
需要用负无穷标记不可达,只有容量 0 初值为 0。
怎样恢复选择的物品?
需要一点提示
最优值没有保存决策。
查看解析与答案
保留二维表或父状态记录,根据某状态是否来自选择当前物品回溯。