01先把问题说具体
同样的背包,但每种物品可取任意多件。只有物品 (2,3),容量 4 时为何答案变成 6?
02一步步得到方法
依赖从上一行变成当前行
完全背包选第 i 种物品后,剩余容量仍然允许使用第 i 种,所以二维式为 max(dp[i−1][c],dp[i][c−w]+v)。和 0/1 的关键差别是选择分支依赖当前行。
一维从小到大更新容量,dp[c−w] 可能已加入本种物品,再加一件正好实现不限次数。不能只说正序是模板,要把对应的状态依赖解释清楚。
计数问题还要分清顺序是否重要
本页代码求最大价值,max 不计算方案数。若改为加法计数,物品在外、容量在内通常数不考虑顺序的组合;容量在外、物品在内通常数有顺序的排列。
所有重量必须正数。重量为零且价值为正会使最优价值无界,普通有限 DP 无法表达;输入检查属于数学模型的一部分。
重复使用来自同一层依赖
完全背包允许当前物品继续被选,所以读取 dp[c−w] 时希望它已经包含当前物品的贡献。这正是容量正序的含义,不只是一个需要背诵的循环习惯。
若研究方案数,外层遍历物品还是外层遍历容量还会影响组合与排列的计数语义。最大价值问题与计数问题不能只换一个加号就认为完全等价。
03把一个小例子完全算清楚
物品 (2,3)、(3,4),容量 6。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 处理重量 2 | dp[2]=3,dp[4]=6,dp[6]=9 | 正序使同种累积 |
| 处理重量 3 | dp[3]=4,dp[5]=7 | 可与重量 2 组合 |
| c=6 | max(9,dp[3]+4=8)=9 | 三件重量 2 更优 |
窄屏可左右滑动表格,阅读完整计算与理由。
答案 9;重复使用由当前行依赖自然产生。
04为什么这个方法成立
- 不选当前种类与至少选一件构成全部方案。
- 选择一件后剩余容量仍可选同种,对应 dp[i][c−w]。
- 正序保证较小容量当前行已求好,且重量正保证依赖严格向小容量。
05把推导翻译成代码
Python · 可独立运行的教学实现
def unbounded_knapsack(items, capacity):
dp = [0]*(capacity+1)
for weight,value in items:
assert weight > 0
for c in range(weight, capacity+1):
dp[c] = max(dp[c], dp[c-weight]+value)
return dp[capacity]逐个理解关键决定
range(weight, capacity+1)- 从小到大,让本种物品的影响继续向更大容量传播。
assert weight > 0- 防止零重量正价值造成数学上的无界最优。
06时间、空间与实现范围
n 种物品、容量 C,时间 O(nC),空间 O(C)。
本版本求不超过容量的最大价值,允许空选择;恰好装满仍需不可达状态。
07改变条件,检查哪里会出错
只把 0/1 代码的名称改成完全背包
必须更改依赖和容量方向,否则仍最多使用一次。
允许零重量且正价值的无限物品
最优价值会无界,必须排除这种输入或明确返回无界状态。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
只有 (3,5),容量 8 得多少?
需要一点提示
最多装两件。
查看解析与答案
10,允许剩余容量 2。
面值 1、2,金额 3,组合数与排列数各几种?
需要一点提示
1+2 与 2+1 是否算不同?
查看解析与答案
组合 2 种:1+1+1、1+2;排列 3 种,多了 2+1。
不限次数但要求至少一件,负价值怎么办?
需要一点提示
初值 0 会选空集。
查看解析与答案
需要额外状态或初始化约束;先改数学问题定义,再改代码,不能只在答案上补一个判断。