如果你已经啃完了 01 背包和完全背包站到多重背包面前时会觉得它只是多了一个“每件物品最多能拿 c 件”的条件。但真正上手之后你会发现这个“最多 c 件”才是最容易出事的——它把很多在 01 背包里理所当然的结论全打碎了。这个系列前面几篇一直用的那套一维数组滚动优化放在多重背包里直接套会翻车完全背包优化掉物品循环的思路在这里也走不通。我最早学多重背包的时候以为看懂了状态转移就能秒杀题目结果第一次提交就 TLE后来才明白多重背包真正考的不是你会不会写转移方程而是你会不会把“数量的维度”降下来。这篇文章就把“朴素三重循环”和“二进制优化”这两板斧彻底讲透适合刚学完 01 背包、准备进阶的算法入门者也适合刷题时被多重背包卡住想搞懂底层逻辑的朋友。1. 三个背包问题里为什么偏偏多重背包最容易写错1.1 先从一个具体的资源分配场景说起假设你的背包容量是 10面前有三种物资物资 A体积 3价值 4最多拿 3 件物资 B体积 4价值 5最多拿 2 件物资 C体积 2价值 3最多拿 4 件问能装下的最大价值是多少。这就是一个标准的多重背包问题每种物品有固定数量上限不能像完全背包那样无限取也不能像 01 背包那样每件只取一次。01 背包问的是“这件物品我拿不拿”完全背包问的是“反正无限件我顺着容量方向一路拿下去”而多重背包问的是“有限件我到底该拿几件刚好凑出最优解”。多出来的这层“数量决策”就是它比前两个容易写错的根源。1.2 数量上限让很多“小聪明”直接失效先说一个容易踩的直觉误区既然每件物品有数量上限那我能不能贪心每次优先拿“单位体积价值最高”的物资答案是绝大多数情况下不行。背包问题一旦带上容量限制局部最优不等价于全局最优。举一个反例容量 10物品 X 体积 6 价值 9单位价值 1.5物品 Y 体积 4 价值 5单位价值 1.25两种物品都只能拿 1 件。按贪心先拿 X剩 4 个容量刚好拿 Y总价值 14但如果只拿两件 Y如果数量允许容量 8 价值 10甚至不如前者可如果有一件 Z 体积 5 价值 6、数量 1那最优解是 XZ15贪心直接错过。数量限制和容量限制叠加后局部“性价比”排序并不可靠。所以多重背包只能老老实实回到状态规划的思路。三个背包问题的核心差异可以用一张表说清楚问题每种物品数量一维滚动数组遍历方向时间复杂度01 背包1 件容量倒序O(NV)完全背包无限件容量正序O(NV)多重背包有限 c 件需要额外处理数量层O(VΣc)这张表里最值得注意的是复杂度那一栏。01 背包和完全背包可以通过改变遍历方向把物品循环“消化”掉多重背包做不到因为数量上限 c 必须显式处理这就逼着你必须多写一层循环。1.3 为什么不能直接套完全背包的正序循环很多初学者会想完全背包正序遍历容量可以无限累加同一物品那多重背包是不是限制一下数量就行理论上可以但实现起来很别扭。完全背包的正序 dp[j] max(dp[j], dp[j - w] v) 天然允许“同一件物品被不断选中”它的正确性依赖“当前容量下可以继续取同一物品”这一前提。多重背包一旦限制“最多 c 件”你就得额外记录每个状态用了多少件维度直接膨胀代码复杂度反而更高。正确的做法是把数量 c 当成一个显式的第三维或第三层循环去枚举。下面从最朴素的写法开始逐步优化。2. 朴素解法把“有限件”强行变成“一件件”以及它的代价2.1 三层循环的状态转移方程多重背包最直观的思路就是既然每种物品最多拿 c 件那我就在 01 背包的基础上多枚举一个“当前这件物品拿几件”。设 dp[j] 表示容量为 j 的背包能获得的最大价值物品 i 的体积为 w[i]、价值为 v[i]、数量上限为 c[i]则转移方程为dp[j] max(dp[j], dp[j - k * w[i]] k * v[i])其中 1 ≤ k ≤ min(c[i], j / w[i])这个方程的意思是面对第 i 种物品我可以在 0 到 c[i] 件之间选一个数量 k然后看看“之前 i-1 种物品在容量 j - k*w[i] 上的最优解”加上“当前这 k 件物品的价值”能不能刷新 dp[j]。2.2 朴素版代码长什么样用 Python 写出来是这样n, V map(int, input().split()) dp [0] * (V 1) for i in range(n): w, v, c map(int, input().split()) # 枚举容量倒序遍历保证每个数量 k 只被用一次 for j in range(V, -1, -1): # 枚举当前物品拿几件 for k in range(1, c 1): if j k * w: break dp[j] max(dp[j], dp[j - k * w] k * v) print(dp[V])这个写法非常直白三重循环k 从 1 枚举到 c一旦当前容量装不下 k 件就直接 break。在一些教材里也会把 k 的枚举放到容量循环外面写成 dp[j] max(dp[j], dp[j-kw]kv) 的二维形式本质一样。2.3 复杂度分析朴素解法为什么在大数据下必挂假设物品总数 n100背包容量 V1000每种物品数量 c1000。朴素写法的时间消耗大约是n × V × c 100 × 1000 × 1000 1 亿次状态更新这个量级在 C 里勉强能卡时间在 Python 里几乎必然超时。更可怕的是如果 c 和 V 继续放大到 1e4、1e5朴素三重循环直接指数级爆炸。所以朴素解法的定位非常明确适合数据量小的情况比如 n ≤ 100、V ≤ 1000、c ≤ 100更多时候它只是作为验证二进制优化正确性的“对拍工具”——先用朴素写法跑小数据再用优化写法跑大数据两个结果一致才能确认优化没写错。2.4 朴素写法里最容易忽略的两个边界问题第一个是容量边界。内层枚举 k 时必须保证 j - kw ≥ 0否则数组越界。很多人的写法是在 for k 循环里写 if (j kw) break这个没问题但如果你把容量循环写成从 0 到 V 的正序就会出大问题——同一件物品会被同一个分组反复选择退化成完全背包。第二个是数量边界。k 的上限不是 c而是 min(c, j // w)因为即使物品有 100 件当前容量只够装 3 件枚举到 4 件也没意义。上面代码用 break 处理了这个逻辑但如果你先算好 max_k min(c, j // w) 再循环性能会更好一点。3. 二进制优化用数学分组替代一件件枚举3.1 为什么一件件枚举是浪费朴素解法慢慢在 k 要逐个枚举 1 到 c。但仔细想一个问题我真的需要枚举“拿 1 件、拿 2 件、拿 3 件……”每一种情况吗数量 c 本身可能很大但从“决策空间”的角度看我只要能组合出 0 到 c 之间的任意一种拿取数量就行不需要按顺序一件件试。这就是二进制优化的切入点——把数量 c 拆成若干个小的“物品包”每个包只能整体拿或不拿但这些包的数量组合起来刚好能表示 0 到 c 的任意取值。3.2 核心数学原理任意整数都能拆成二进制块我们知道任意正整数都可以用二进制表示。比如 13 1101₂ 8 4 1。如果把 13 件物品分成三组1 件一组、4 件一组、8 件一组那么这三组“选或是不选”一共能组合出多少种总数量答案是 0、1、4、5、8、9、12、13 这 8 种但中间缺了 2、3、6、7、10、11并不能覆盖 0 到 13 的全部整数。问题出在分组方式上。用纯 2 的幂分组只适合 c 恰好等于 2^p - 1 的情况比如 1、3、7、15因为 124...2^(p-1) 2^p - 1 正好能表示 0 到 2^p - 1 的所有整数。如果 c 不是这种形式就要用一套更聪明的拆法。3.3 标准拆法按 2 的幂倍增剩下的单独成组二进制优化的标准分组流程如下k 1 while c 0: take min(k, c) # 本组取多少件 生成一个物品包体积 take * w价值 take * v c - take k 1 # k 翻倍以 c13 为例完整过程是轮次k 的值c 剩余take min(k, c)生成的分组111311 件组221222 件组341044 件组48666 件组51600结束所以 13 件物品被拆成 1、2、4、6 四组。为什么最后一组是 6 而不是 8因为前面 1247已经能表示 0 到 7 的任意数量再来一组 6就能把表示范围扩展成 0 到 13。验证一下要表示数量 x如果 x ≤ 7直接用前几组凑如果 x 7先拿最后一组 6剩下 x-6 在 0 到 7 之间再用前几组凑。这就覆盖了 8 到 13 的所有情况。这个拆法的精妙之处在于每组只能选或不选但若干组组合出来的数量能覆盖 0 到 c 的所有整数等于用 O(log c) 个“01 背包物品”等价替换了原来要枚举 c 次的数量循环。3.4 分组正确性的严格说明为什么按 “1、2、4……2^p、余数 r” 拆分后一定能表示 0 到 c 的任意整数设前 p 组分别包含 1、2、4、…、2^(p-1) 件它们的总和是 2^p - 1。前 p 组能组合出 0 到 2^p - 1 的所有整数这由二进制计数保证。最后一组包含 r c - (2^p - 1) 件r 的取值范围是 0 ≤ r ≤ 2^p因为如果 r 超过 2^p就可以继续拆一组 2^p 出来。任意目标数量 x ∈ [0, c]如果 x 2^p直接用前 p 组组合出来。如果 x ≥ 2^p取最后一组 r 件剩余 x - r。因为 x ≤ c (2^p - 1) r所以 x - r ≤ 2^p - 1而 x ≥ 2^p 时 x - r x - (c - 2^p 1) ≥ 2^p - (c - 2^p 1) 2^p - r 2^p - 1实际上只需要保证 x - r ≥ 0 即可由于 x ≥ 2^p 且 r ≤ 2^p这个条件成立。因此 x - r 落在 0 到 2^p - 1 之间前 p 组能组合出来。所以任意 0 到 c 的数量都能被表示分组是完备的。3.5 为什么这种拆法行逐件枚举也行但前者快这么多从复杂度角度看拆成 1、2、4……后物品总量从 c 件降到了 O(log c) 件。原本多重背包是“一个物品循环 × 一个数量循环 × 一个容量循环”现在数量循环被吃掉了只剩下“O(log c) 个 01 物品 × 容量循环”。方法时间复杂度物品数量规模朴素三重循环O(V × Σc)c 多大就枚举多少轮二进制优化O(V × Σlog c)每组拆成约 log c 个包单调队列优化预告O(NV)不拆组直接滑动窗口二进制优化不是唯一的优化手段但它从“每件物品逐个考虑”提升到“每组物品按二进制块考虑”思路最简单、代码量最少、理解成本最低非常适合作为多重背包的第一课。4. 优化后的完整代码与三个最容易踩的坑4.1 用二进制优化重写完整解法下面这份代码是竞赛里最常见的写法输入格式为“n、V然后每行 w、v、c”。n, V map(int, input().split()) dp [0] * (V 1) for i in range(n): w, v, c map(int, input().split()) k 1 while c 0: take min(k, c) # 这一组实际取多少件 c - take # 把 take 件物品打包成一个“01 物品”容量倒序更新 pack_w take * w pack_v take * v for j in range(V, pack_w - 1, -1): dp[j] max(dp[j], dp[j - pack_w] pack_v) k 1 print(dp[V])核心逻辑就两句话把数量 c 按二进制拆包每包当 01 背包处理。注意容量循环必须是倒序因为拆出来的每一个包只能使用一次。4.2 坑一分组时把最后一组算错了最常见的错误发生在“取剩余量”那一步。有人会写成while c 0: pack min(k, c) # 错误做法分组后没有正确更新 c 和 k或者干脆用除法写成每次取 c 的一半导致分组不正确。正确的方式是上面展示的 min(k, c) 加上每次 k 左移一位。如果 c13最后一定会得到 1、2、4、6 四组如果写成“每次都取 c // 2”得到的分组会遗漏某些数量组合最终答案出错。判断分组是否正确的小技巧把各组数量加起来必须等于原始 c。比如 124613说明每件物品都被装进了一个包没有漏也没有重。4.3 坑二内层容量循环忘了倒序这是从 01 背包继承过来的铁律但在多重背包里更容易犯因为多了分组逻辑注意力全在 while 循环上。如果你把 for j in range(V, pack_w - 1, -1) 写成 for j in range(pack_w, V1)同一个包就会被重复使用等价于把一个数量有限的包用成了无限次答案会偏大。怎么自查如果跑样例时答案比预期大十有八九是遍历方向错了。4.4 坑三初始化方式和题目要求不匹配如果题目问“背包恰好装满的最大价值”dp[0] 要初始化为 0dp[1..V] 初始化为负无穷如果只是问“不超过容量 V 的最大价值”全部初始化为 0 就可以。区分方法很简单看到“恰好装满”“正好达到”这类字眼用负无穷初始化看到“最多能装”“最大价值”用 0 初始化。这个规则和 01 背包、完全背包完全一致多重背包不特殊但很多新手在转移方程写对之后栽在初始化上挺可惜的。4.5 实测对比同一组数据两种写法差距有多大我用一组随机数据做对比n100V1000每件物品体积在 1~20 之间价值在 1~50 之间数量 c 固定为 1000。朴素三重循环大约需要 1 亿次内层更新在本地 Python 环境运行超过 10 秒OJ 上直接 TLE。二进制优化每件物品拆成约 10 个包1000 拆成 1、2、4、8、16、32、64、128、256、489总共约 1000 个 01 物品每个物品只需要 O(V) 次更新总操作量约 1000×1000100 万次运行时间不到 0.1 秒。差距是百倍量级。数据量再放大到 V10000、c10000朴素写法基本跑不动二进制优化依然能在一秒内完成。这就是你必须在真正比赛或项目里使用二进制优化的原因。5. 从这道“1”往后看二进制优化不够用怎么办5.1 什么时候二进制优化也不够二进制优化的复杂度是 O(V Σlog c)如果 V 很大比如 1e5n 也很大比如 1000Σlog c 大约是 1000×10 1e4乘积就是 1e9还是会超时。这时候就要上更进阶的单调队列优化也叫滑动窗口优化。核心思路是把容量维度按余数分类对于每个余数 rdp 值在 k 方向上的更新其实是一个滑动窗口取最大值的操作可以在 O(V) 内完成整个物品的处理。这样多重背包的复杂度就是 O(NV)不再依赖数量 c 的大小。这一块是这个系列的下一篇文章要细讲的内容我这里只提醒一件事二进制优化和单调队列优化解决的是不同层面的问题。二进制优化是“减少物品数量”单调队列优化是“加速转移过程”两者甚至可以结合理解但比赛里通常二选一。5.2 多重背包在真实场景里的典型应用除了算法竞赛多重背包在实际工程里也经常出现采购预算分配预算有限几种不同规格的服务器配件每种库存有限怎么组合收益最大。游戏礼包搭配每种礼包限购玩家有代币上限怎么买战力提升最多。物流装箱同一规格货品有限量车厢容量固定怎么装总价值最高。这些场景的共同点是“有容量上限 有数量上限”恰好就是多重背包的适用范围。理解了二进制优化的分组思想你面对这类“有限资源组合优化”问题时就多了一个高效的建模工具。5.3 个人调试经验写优化代码前先写朴素版我在刷题时养成了一个习惯任何多重背包题先写好朴素三重循环版本用小数据验证答案正确再改成二进制优化版本继续用同一组小数据对拍两个版本输出必须一致。一旦发现二进制优化版本和朴素版不一致不要急着调 OJ先回到小数据去定位分组逻辑有没有写错。这个方法看着多花几分钟实际上帮你省下反复提交 TLE 或 WA 的大量时间。尤其是刚接触多重背包的一两周内对拍就是最可靠的调试方式。等你把“1、2、4、余数”这套分组逻辑写到肌肉记忆之后就可以跳过朴素版直接写优化版了。最后再分享一个我现在写多重背包的固定套路拿到题先看 c 的范围。如果 Σc 小直接朴素三重循环如果 c 大但 V 适中用二进制优化如果 V 和 c 都大到离谱才考虑单调队列优化。先判断数据范围再动手就不会出现“题目过了小数据换了大样例就卡死”的情况。