01先把问题说具体
一种物品重量 2、价值 3,最多 13 件。直接逐件复制可以做,但数量很大时怎样减少物品数?
02一步步得到方法
把可选数量拆成若干包
将数量 13 拆成 1、2、4、6。每一包视作不可再拆的 0/1 物品,重量和价值同时乘包内件数。选若干包即可表达从 0 到 13 的任意整数数量。
为什么最后可以是 6 而不是 8?前面的 1、2、4 已能表示 0..7,再加 6 可表示 6..13,两段重叠且无空隙,合起来覆盖完整范围。
必须同时守住覆盖与上限
拆分包总件数等于原上限,因此任何包组合都不会超出数量。每次取不超过剩余数量的二次幂包,最后不足一包时取剩余。每个包只用一次,所以容量仍倒序更新。
复杂度从按数量展开变为按数量的对数展开。另一条进阶路线是按重量余数分类,用单调队列优化,但那是不同推导,不能把它的 O(nC) 界套到本版本。
拆包后仍要使用 0/1 更新
把数量上限拆成若干包,每包重量与价值同时乘包内件数。每个包作为一件0/1物品处理,容量仍应倒序,否则同一包会被无限重复,突破原上限。
二进制拆包保证从0到上限的每种件数都能表示,但表示不一定唯一。因此它适合可行性或最优值,不应直接用于要求每种选择只计一次的方案数问题。
03把一个小例子完全算清楚
数量 5 拆为 1、2、2;单件 (2,3),容量 8。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 第一包 1 件 | 重量 2、价值 3 | 独立 0/1 选择 |
| 第二、三包各 2 件 | 各重量 4、价值 6 | 两包身份不同 |
| 容量 8 | 选择两个 2 件包,价值 12 | 共 4 件,不超过 5 |
窄屏可左右滑动表格,阅读完整计算与理由。
两个大小相同的包也可以同时选择,因为它们代表不同的库存份额。
04为什么这个方法成立
- 拆分前已能表示 0..S,下一包大小≤S+1 时可将覆盖连续扩到 S+包大小。
- 所有包总量等于库存,保证不超量。
- 包的重量价值均成比例,0/1 最优组合与原有界数量问题等价。
05把推导翻译成代码
Python · 可独立运行的教学实现
def bounded_knapsack(items, capacity):
dp = [0]*(capacity+1)
for weight,value,count in items:
assert weight > 0 and count >= 0
bundle = 1
while count:
take = min(bundle,count)
w,v = weight*take, value*take
for c in range(capacity,w-1,-1):
dp[c] = max(dp[c],dp[c-w]+v)
count -= take
bundle *= 2
return dp[capacity]逐个理解关键决定
take = min(bundle,count)- 最后一包取剩余,不超过库存。
range(capacity,w-1,-1)- 每个拆分包只能选择一次,仍是 0/1 更新方向。
06时间、空间与实现范围
时间 O(C Σlog(countᵢ+1)),空间 O(C),不必显式存储所有拆分包。
库存为 0 自然跳过;金额与重量要同时乘包大小,不能只放大价值。
07改变条件,检查哪里会出错
把 13 件只拆为 1、2、4、8
总量变成 15,可能选择超过原上限;最后应取剩余 6。
用拆包后的方案数冒充原题方案数
同一数量可能由不同包组合表示,计数可能重复,需要专门的有界计数转移。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
数量 6 拆成什么?
需要一点提示
每次取 1、2,再取剩余。
查看解析与答案
1、2、3,覆盖 0..6。
只有 2 件 (2,3),容量 10 得多少?
需要一点提示
容量充足但库存有限。
查看解析与答案
6。
数量远大于 capacity/weight 可先做什么?
需要一点提示
不可能装入更多件。
查看解析与答案
先把数量截断到 floor(capacity/weight),减少无意义拆分。