1. 从一道题说起为什么暴力拆解多重背包会超时第一次在题库里刷到“Kirito”这道题的时候我下意识地把它当成了一个普通的完全背包来做。题目大意是有若干种物品每种物品有数量上限要在给定容量内拿到最大价值。看起来跟完全背包就差一个“数量限制”于是我很自然地写了一个三层循环外层枚举物品中层枚举容量内层枚举当前物品拿几个。提交超时。这个结果其实完全在意料之中。假设有 n 种物品背包容量为 V每种物品最多拿 s 个那么朴素多重背包的时间复杂度是 O(n × V × s)。当 n、V、s 都达到几百甚至上千的量级时这个复杂度会直接爆炸。我当时算了一下如果 n100V1000s100那运算量就是 10^7 级别看似还行但如果数据再大一点比如 n1000V10000s1000那就是 10^10任何评测机都扛不住。所以问题就来了怎么在不改变问题本质的前提下把“每种物品有 s 个”这个条件处理得更高效这就是多重背包这个经典模型要解决的核心矛盾而二进制优化则是解决它最常用、也最优雅的手段之一。这篇文章我会从这道题出发把多重背包的几种解法思路、二进制优化的原理推导、代码实现细节、以及我在实际写题过程中踩过的坑完整地梳理一遍。不管你是刚接触背包问题的新手还是已经写过几道但总是被卡常数的老手应该都能从中找到对自己有用的东西。2. 多重背包的三种解法与选型逻辑2.1 朴素解法能过但不够用朴素多重背包的思路最直观把每种物品的 s 个数量当成 s 个独立的物品然后跑 0/1 背包。或者更直接一点在状态转移的时候多套一层循环枚举拿几个。// 朴素多重背包 for (int i 1; i n; i) { for (int j V; j w[i]; j--) { for (int k 1; k s[i] k * w[i] j; k) { dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]); } } }这段代码逻辑上没有问题但第三层循环是性能杀手。当 s[i] 很大的时候内层循环的次数会非常多。我实测过一组数据n500V5000每种物品数量在 1 到 500 之间随机朴素写法跑了将近 3 秒而二进制优化版本只用了不到 0.1 秒。差距就是这么明显。注意有些题目会给出“数据保证所有物品数量之和不超过某个值”这样的条件这种情况下朴素写法也能过。但你不能指望每道题都这么仁慈养成优化习惯比临时抱佛脚靠谱得多。2.2 单调队列优化理论最优但实现复杂多重背包还有一种 O(n × V) 的单调队列优化解法。它的核心思想是利用状态转移方程中“同余类”的性质把内层枚举转化为滑动窗口求最大值。理论上这是最优解法但实现起来比较绕需要对同余类分组、维护单调队列代码量大概是二进制优化的两倍以上。我在实际刷题的时候除非题目数据规模特别大比如 V 达到 10^5 级别且物品数量也很大否则一般不会优先选择单调队列。原因很简单二进制优化的 O(n × V × log s) 在绝大多数题目里已经足够快了而且代码好写、不容易出错。竞赛里时间就是分数能用简单方法解决的问题没必要为了炫技去写复杂代码。2.3 二进制优化性价比最高的选择二进制优化的核心思路是把“第 i 种物品有 s 个”这个条件转化为“有若干个体积和价值分别为 w×1, w×2, w×4, ... 的物品组”。通过这种拆分方式任何 0 到 s 之间的数量都可以由这些组组合出来。举个例子假设某种物品有 13 个二进制拆分会把它分成 1、2、4、6 四组。为什么最后一组是 6 而不是 8因为 124713-76如果继续拆成 8那 124815 就超过了 13会导致多拿。所以最后一组的数量是剩余值保证总和恰好等于 s。这样拆分之后问题就变成了一个 0/1 背包每组物品要么拿要么不拿。而组数从 s 降到了 log₂(s) 级别时间复杂度自然就下来了。解法时间复杂度代码难度适用场景朴素多重背包O(n × V × s)低数据规模很小二进制优化O(n × V × log s)中绝大多数场景单调队列优化O(n × V)高数据规模极大3. 二进制优化的原理拆解与正确性证明3.1 为什么二进制拆分能覆盖所有数量这个问题的本质是用最少的组数表示出 0 到 s 之间的所有整数。二进制拆分给出的方案是 1, 2, 4, ..., 2^(k-1), s-(2^k-1)其中 2^k-1 ≤ s。前 k 组可以组合出 0 到 2^k-1 之间的任意整数这是二进制的基本性质。而最后一组 r s-(2^k-1)它的取值范围是 1 到 2^k。把最后一组加进来之后能表示的范围就扩展到了 r 到 r2^k-1也就是 s-2^k1 到 s。由于 r ≤ 2^k这两个区间是连续的合起来就覆盖了 0 到 s 的所有整数。我当初理解这一点的时候用了一个很直观的类比假设你有若干张面额不同的纸币1 元、2 元、4 元、8 元……你可以凑出任何不超过总额的金额。二进制拆分就是把“数量”当成“金额”来凑保证每种拿法都能被表示出来。3.2 拆分后的 0/1 背包为什么等价于原问题原问题中第 i 种物品可以拿 0 到 s 个拿 k 个的收益是 k×v[i]代价是 k×w[i]。拆分之后我们得到了若干组物品每组只能选或不选。如果选了数量为 1、2、4 的三组等价于拿了 7 个原物品如果选了 1、4、6 三组等价于拿了 11 个。关键在于任何一种拿法拿 0 个、拿 1 个、……、拿 s 个都对应拆分后物品组的一个子集且这个子集的总数量恰好等于拿的个数。反过来拆分后物品组的任何一个子集其总数量也不会超过 s。所以两个问题的解空间是一一对应的最优解自然也相同。提示二进制拆分不改变问题的可行解集合只是换了一种表达方式。这是它能保证正确性的根本原因。3.3 拆分过程中的边界处理拆分的时候有几个细节容易出错。第一当 s0 时这种物品实际上不存在应该直接跳过。第二当 s1 时拆分成一组就够了不需要额外处理。第三最后一组的数量 r 必须大于 0如果 r0 说明前面的拆分已经恰好覆盖了 s不需要再加一组。// 二进制拆分 int cnt 0; for (int i 1; i n; i) { int k 1; int remain s[i]; while (k remain) { cnt; new_w[cnt] k * w[i]; new_v[cnt] k * v[i]; remain - k; k 1; } if (remain 0) { cnt; new_w[cnt] remain * w[i]; new_v[cnt] remain * v[i]; } }这段代码我写过不下几十遍但每次写的时候还是会下意识检查一下 remain 的处理。因为如果这里写错了比如把k remain写成k remain就会导致最后一组多出来或者少掉答案直接错。4. 完整代码实现与关键步骤注释4.1 数据读入与预处理以“Kirito”这道题为例输入格式通常是先给出物品数量 n 和背包容量 V然后每行给出 w[i]、v[i]、s[i] 三个值。读入的时候要注意数据范围如果 w 和 v 比较大dp 数组要用 long long 防止溢出。#include bits/stdc.h using namespace std; const int MAXN 100005; int w[MAXN], v[MAXN], s[MAXN]; int new_w[MAXN], new_v[MAXN]; long long dp[MAXN]; int main() { int n, V; cin n V; for (int i 1; i n; i) { cin w[i] v[i] s[i]; } // ... }我一般会把新数组开得足够大。二进制拆分后物品组数的上界是 n × log₂(max_s)如果 n1000max_s1000那大概是一万组左右开 100005 完全够用。4.2 二进制拆分与 0/1 背包合并拆分和背包可以写在同一个循环里也可以先拆分再统一跑背包。我习惯先拆分再跑这样逻辑更清晰调试的时候也方便查看拆分结果。int cnt 0; for (int i 1; i n; i) { int k 1; int remain s[i]; while (k remain) { cnt; new_w[cnt] k * w[i]; new_v[cnt] k * v[i]; remain - k; k 1; } if (remain 0) { cnt; new_w[cnt] remain * w[i]; new_v[cnt] remain * v[i]; } } for (int i 1; i cnt; i) { for (int j V; j new_w[i]; j--) { dp[j] max(dp[j], dp[j - new_w[i]] new_v[i]); } }内层循环必须从 V 倒序遍历这是 0/1 背包的标志。如果写成正序就变成了完全背包每种物品会被重复拿多次答案就错了。这个点我在初学的时候踩过坑当时怎么调试都找不到问题后来才发现是循环方向写反了。4.3 参数选择与复杂度估算假设 n1000V10000每种物品最多 1000 个。二进制拆分后每种物品最多拆成 10 组左右总组数约 10000。背包部分的时间复杂度是 O(cnt × V) 10^8在 C 里大概跑 0.3 到 0.5 秒可以接受。如果 V 再大一个数量级就需要考虑单调队列优化了。空间方面dp 数组开 V1 大小新物品数组开 cnt1 大小。如果 V 达到 10^6dp 数组用 int 是 4MB用 long long 是 8MB一般不会超内存。参数典型值说明n100~1000物品种数V1000~10000背包容量s1~1000每种物品数量上限cntn × log₂(s)拆分后组数时间复杂度O(cnt × V)约 10^7~10^85. 常见问题与排查技巧实录5.1 答案偏小拆分不完整这是最常见的问题。现象是样例能过但提交后部分测试点答案偏小。原因通常是拆分时最后一组没有正确处理。比如 s13拆成 1、2、4 之后 remain6如果忘记加这一组那 8 到 13 之间的数量就表示不出来导致某些最优解拿不到。排查方法很简单拆分完之后把 new_w 和 new_v 数组打印出来手动验证一下能不能组合出 0 到 s 的所有数量。我一般会写一个临时的小循环来检查。5.2 答案偏大循环方向写反如果内层循环写成了正序每种物品会被重复拿答案会偏大。这个错误的隐蔽性在于小数据可能看不出来因为小数据下最优解可能恰好不需要重复拿。但数据一大就会暴露。注意0/1 背包倒序完全背包正序。这是铁律写的时候默念一遍。5.3 运行超时数组开太小或拆分效率低有时候代码逻辑没问题但就是超时。原因可能是 new_w 和 new_v 数组开小了导致越界访问程序行为异常。或者拆分的时候用了 vector 的 push_back频繁扩容影响性能。我一般直接用静态数组加计数器效率最高。还有一种情况是读入用了 cin 但没关同步数据量大的时候会慢很多。加上ios::sync_with_stdio(false); cin.tie(0);就能解决。5.4 常见问题速查表问题现象可能原因解决方法答案偏小最后一组未加入检查 remain 0 的分支答案偏大内层循环正序改为倒序遍历运行超时数组越界或 IO 慢开大数组、关同步部分点 WA数据类型溢出dp 数组改用 long long编译错误数组大小是变量使用常量或动态分配5.5 独家避坑心得我在写多重背包的时候养成了一个习惯先把二进制拆分的结果打印出来确认无误后再跑背包。这个习惯帮我省了很多调试时间。另外如果题目中 s[i] 的值特别大比如 10^9二进制拆分后的组数会达到 30 左右这时候要注意 cnt 的上界数组要开够。还有一个细节有些题目中物品的体积可能为 0这时候内层循环的终止条件要特别注意否则会死循环。虽然这种情况少见但遇到了就是大坑。6. 从这道题延伸出去多重背包的实际应用场景多重背包不仅仅是竞赛题它在实际工程中也有很多对应场景。比如资源分配问题你有若干种服务器配置可选每种配置有数量限制要在预算内最大化算力。这就是一个典型的多重背包模型。再比如生产计划工厂有若干种产品每种产品的生产数量有上限要在原材料限制下最大化利润。二进制优化的思想也可以迁移到其他问题。它的本质是“用最少的组表示一个范围内的所有整数”这个技巧在状态压缩、集合划分等问题中都有应用。理解了这一点你就不只是在做一道题而是在掌握一种通用的思维工具。我在实际项目中遇到过一个类似的场景需要把一批数量不等的任务分配给若干个执行单元每个执行单元的处理能力有上限。当时就是用二进制拆分的思路把任务分组然后跑 0/1 背包来求最优分配方案。代码写起来很快效果也很好。最后分享一个小技巧如果你不确定二进制拆分写得对不对可以用一个暴力程序对拍。随机生成小数据分别跑朴素解法和二进制优化解法比较结果。对拍个几百组没问题就可以放心提交了。这个方法我在刷题的时候经常用比肉眼检查靠谱得多。