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

用二进制拆分表达数量上限,再还原为 0/1 背包。

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

多重背包Bounded Knapsack

每件物品数量有限,可二进制拆分或使用单调队列优化。

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

本课要建立的能力

用二进制拆分表达数量上限,再还原为 0/1 背包。

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

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为什么这个方法成立

  1. 拆分前已能表示 0..S,下一包大小≤S+1 时可将覆盖连续扩到 S+包大小。
  2. 所有包总量等于库存,保证不超量。
  3. 包的重量价值均成比例,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从手算到独立迁移

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

练习 1 · 复现与理解

数量 6 拆成什么?

需要一点提示

每次取 1、2,再取剩余。

查看解析与答案

1、2、3,覆盖 0..6。

练习 2 · 边界与辨析

只有 2 件 (2,3),容量 10 得多少?

需要一点提示

容量充足但库存有限。

查看解析与答案

6。

练习 3 · 变式与迁移

数量远大于 capacity/weight 可先做什么?

需要一点提示

不可能装入更多件。

查看解析与答案

先把数量截断到 floor(capacity/weight),减少无意义拆分。

继续深入这个专题

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

MIT 6.006 · 算法讲义

理解之后,继续递进

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