背包问题里最容易被高估的其实是“模型识别”。很多朋友一上来就背0-1背包模板背得滚瓜烂熟结果看到卡码网56题《携带矿石资源》这种题就懵了每种矿石有重量、有价值还带一个“数量”这到底算什么背包我第一次做这道题时第一反应是把每种矿石按块拆开全当成0-1背包做结果小数据能过数据一多就超时。后来才意识到这题考的是多重背包而且必须用二进制拆分去做数量层级的优化。这篇文章会把这道题从头到尾拆开包括题面建模、三种背包的差异、为什么二进制拆分能成立、完整C实现、常见报错和调试心得给正在被背包问题折磨的朋友一个可以直接照着写的方案。1. 题面拆解与问题归类1.1 从“携带矿石”到背包模型背包问题的核心其实就一句话在容量有限的情况下怎么选东西能让总价值最大。卡码网56题《携带矿石资源》的题面通常可以理解成你有一个背包承重是bagWeight面前有n种矿石每一种矿石有三个参数——重量、价值、数量。你需要决定每种矿石带几块使得总重量不超过背包承重同时总价值最大。这个模型看起来和0-1背包很像但多了一个数量字段很多人第一次见容易懵。其实只要把它理解成“有n组物品第i组最多能取count[i]件每件重量为weight[i]、价值为value[i]”问题就清楚了。这就是典型的多重背包模型也是动态规划里最经典的一类资源分配问题。为什么要单独把数量提出来因为0-1背包里的“选”是二元选择带或不带这里的“选”是一个整数范围可以选择0、1、2…count[i]件。这个“整数范围”就是多重背包和0-1背包、完全背包的本质区别。如果你只会写0-1背包这个多出来的维度就会让你觉得所有状态都对不上尤其是容量循环和物品循环的嵌套关系稍不注意就写错。1.2 三种背包问题怎么区分刷题的时候我习惯用一句话记0-1背包是“每件最多拿一次”完全背包是“每件能拿无限次”多重背包是“每件拿的次数有限”。如果题目里出现“数量不超过x”这种描述就往多重背包上靠。卡码网56题给了每种矿石的数量所以它是多重背包不是完全背包。这个区别在代码里表现得更直接完全背包的容量循环可以从小到大走因为同一个物品可以反复使用。但多重背包不能直接照搬这个写法因为如果内层循环改成从小到大那相当于把count[i]当成正无穷最终答案一定会偏大。不少人在0-1背包和完全背包刚学会之后就急着做这道题结果就栽在“为什么我的答案比预期大”这个问题上。另外还要区分“多重背包”和“分组背包”。分组背包是每组只能选一个多重背包是每组能选多个但选多个的动作最终要通过二进制拆分或者枚举件数来体现。别看这两个概念名字像转移逻辑完全不同。做卡码网56的时候别被“组”这个字带跑偏。1.3 为什么不能直接把每种矿石硬拆成独立物品最朴素的做法是把count[i]块矿石全拆成独立物品然后直接跑0-1背包。这个思路完全正确但效率可能吃不消。假设背包容量是1000矿石种类100种每种数量10000拆完之后是100万件0-1背包复杂度O(物品数*容量)一下就到了10亿次运算OJ基本会给你一个超时。所以题目真正想考察的是在“数量”这个维度上做优化。你不能老老实实按“块”拆而要把“数量”按二进制的方式做压缩。这样拆出来的物品数量不是count[i]而是log2(count[i])级别整体复杂度就能降到能接受的范围。这里我要多说一句不要因为“二进制拆分”听起来难就直接放弃理解去背模板。这个技巧的本质并不复杂后面我会用13块矿石的例子把它彻底讲透。只要理解了那个例子代码写出来就不容易错。2. 从暴力拆解到二进制优化2.1 最朴素的写法三重循环先跑一次在说二进制优化之前先看一种不拆物品直接枚举选几件的写法方便对比for (int i 0; i n; i) { for (int k 0; k count[i]; k) { for (int j bagWeight; j k * weight[i]; --j) { dp[j] max(dp[j], dp[j - k * weight[i]] k * value[i]); } } }这个三重循环在逻辑上是正确的对每种矿石枚举“选0件、选1件、…、选count[i]件”然后按0-1背包的滚动数组方式更新。复杂度是O(bagWeight * sum(count[i]))如果所有count[i]加起来不大比如总和1000以内它是可以过的。但如果数量级到10^4、10^5这个三重循环就会变成灾难。我想说的是遇到多重背包先别急着优化先把这种朴素枚举在脑子里过一遍因为它能帮你确认“这是在枚举一个整数选择范围”。有了这个基础再看二进制拆分就不会觉得那是魔法。2.2 二进制拆分的核心思想二进制拆分的出发点很朴素既然要枚举0到count[i]这么多件能不能少枚举一点比如13块一模一样的矿石我不拆成13块而是分成四堆1块、2块、4块、6块。这四个堆每堆作为一个独立的0-1物品带或不带。它们的组合能覆盖0到13之间任意数量吗可以。1、2、4能表示0到76和它们组合能表示6到13两个区间连起来就是0到13。这里要注意为什么最后一堆是6而不是8因为8加上前面1247就变成15超过13了。所以最后一堆只能取“剩余数”。反过来如果数量正好是8拆出来会是1、2、4、1看起来好像有两个1这是正常的不是bug。原因很简单1、2、4只能表示0到7没法表示8必须再留一个1两个1件组同时选就表示取2件合法。从复杂度看13块矿石原本要枚举13种数量拆完只需要做4次0-1决策。count越大节省越明显。这就是二进制优化它的本质是把线性枚举变成对数级别。2.3 为什么任意数量都能覆盖先记住一个结论1、2、4、…、2^(k-1)这些二进制堆加起来是2^k-1它们能组合出0到2^k-1之间任意整数。这其实就是二进制计数每一位表示选或不选。接着如果前面这些堆的和是s最后一堆是restrest满足什么条件按拆分逻辑rest是第一次满足rest≤s时的剩余数量也就是rest≤s。这样前一堆能覆盖0~s后一堆加上前面能覆盖rest~rests因为rest≤s≤s1两个区间没有断档所以0到rests也就是总量total全覆盖。如果你觉得这段证明绕就记住一个更直观的说法任意目标数量t如果trest直接用前面的二进制堆去凑如果t≥rest先把rest这一堆选上再用前面的二进制堆去凑t-rest。两种情况都能凑出来。这个理解方式对写代码帮助很大至少你不会在拆分时把最后一个剩余数丢掉。实际写代码的时候我更喜欢用“取min”的写法每次从当前数量里取min(k,剩余)件合成一个新物品然后剩余数量减掉这部分k翻倍。这个写法天然就处理了“最后一堆是剩余数”的情况不用单独写if。2.4 为什么不能直接用完全背包的无限循环有些同学会想count[i]给了上限能不能把每种物品当成完全背包然后在状态里额外记一下用了多少个理论上可以但要给DP数组加一个维度复杂度跟直接暴力做差不多。更常见的错误是只把内层循环改成从小到大这样同一组物品会被反复选中数量限制形同虚设。比如数量只有3循环完可能选到5件、8件结果自然错误。“从小到大”是给“无限量”用的不是给“有限量”用的。多重背包要么用二进制拆分转成0-1要么用单调队列去优化千万不要图省事改成完全背包的循环方向。我在调试自己写的代码时经常看到新手把0-1背包模板里的for (int j bagWeight; j weight[i]; --j)改成for (int j weight[i]; j bagWeight; j)然后皱着眉问为什么答案偏大原因就是这里。3. 实操实现完整解法3.1 输入约定与状态定义卡码网的输入我按常见约定来写第一行两个整数第一个是背包容量bagWeight第二个是矿石种类数n接下来n行每行三个整数分别表示重量、价值、数量。如果你的题目输入顺序不一样把读入的两个数调换一下就行。状态定义用一维滚动数组dp[j]表示可用容量为j时能获得的最大总价值。初始化时全部填0因为题目只要求“在容量范围内带走最大价值”不要求恰好装满装不满也算合法方案。如果你把dp[1..bagWeight]初始化成负无穷反而会让很多合法方案变成负值最后max结果不对这个细节后面还会再说。3.2 二进制拆分后的代码实现完整可跑的C代码如下#include iostream #include vector #include algorithm using namespace std; int main() { int bagWeight, n; while (cin bagWeight n) { vectorint weights, values; for (int i 0; i n; i) { int w, v, c; cin w v c; int k 1; while (c 0) { int num min(k, c); weights.push_back(w * num); values.push_back(v * num); c - num; if (c 0) break; k 1; } } vectorint dp(bagWeight 1, 0); for (int i 0; i (int)weights.size(); i) { for (int j bagWeight; j weights[i]; --j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } cout dp[bagWeight] endl; } return 0; }代码里的while循环是核心。每次从当前剩余数量c中取出num min(k, c)件合成一个新物品。比如c13k1时取1件c变12k2时取2件c变10k4时取4件c变6k8时取6件c变0结束。每一堆合成的新物品重量是wnum价值是vnum这就可以直接丢进0-1背包处理。这里有一个细节k的翻倍放在c减为0的判断之后。如果c已经减到0就直接break不再让k继续翻倍。这个习惯可以避免在某些极端数据下k翻倍到int溢出。如果题目数据范围更大可以把k和num都声明成long longweights和values也用long long稳妥得多。3.3 一维滚动数组的遍历方向拆完之后问题就变成了标准的0-1背包每个新物品最多选一次。0-1背包的滚动数组必须从右往左更新for (int j bagWeight; j weights[i]; --j) { dp[j] max(dp[j], dp[j - weights[i]] values[i]); }原因很简单如果从左往右更新dp[j - weights[i]]可能已经被本轮更新过再拿它去更新dp[j]就相当于同一个新物品被用了两次。在0-1背包里这绝对不允许。在多重背包的二进制拆分之后每个新物品同样是0-1物品所以必须沿用这个倒序规则。很多人的错误是前面拆得好好的结果内层循环写成for (int j weights[i]; j bagWeight; j)一提交答案偏大。这就是把0-1背包写成了完全背包的样子等价于每个新物品无限次取用二进制分的那几个组全都被当成了无限库存。排查方法也简单把这个循环方向改回倒序如果wa立刻消失那问题就只在这一行。3.4 手工推演一个简单数据光看代码不够我举一个很小的例子。背包容量10有两种矿石A重量3价值4数量4B重量4价值5数量2。拆分后A变成3件新物品3/4、6/8、3/4B变成2件新物品4/5、4/5。0-1背包跑下来最优方案是选一个A的1件组、再选一个A的1件组、再选一个B的1件组总重量33410总价值44513。注意拆出来的A有两个相同的“1件组”同时选两个表示这种矿石实际取了2件。这个例子很小但能说明两件事第一二进制拆分后的新物品可以自由组合组合后对应的原始数量不会重复也不会遗漏第二DP结果和直观看答案是一致的。我建议拿到题先手推一个样例再写代码能减少很多无谓的调试。3.5 复杂度分析拆分后每种矿石最多拆出O(log count[i])个新物品总物品数从sum count[i]降到sum log count[i]。0-1背包部分的复杂度是O(bagWeight * sum log count[i])空间复杂度O(bagWeight)。和暴力拆成每块矿石的O(bagWeight * sum count[i])相比提升非常明显。如果bagWeight是1000count[i]是10000100种矿石暴力是10亿二进制拆分后大约1000 * 100 * 14 140万次轻松过。当然如果count[i]特别大而bagWeight也特别大二进制优化可能还不够那就需要单调队列优化把复杂度压到O(bagWeight * n)。不过卡码网56这题用二进制优化已经足够而且二进制优化好在代码简单、不容易写错。4. 常见问题与排查技巧实录4.1 拆出来的物品总数不对怎么办一个很好用的自检方法写完拆分后统计一下weights.size()是不是远远小于原来的总块数同时所有新物品的num加在一起要等于原count。如果等于说明没有丢数量如果不等于八成是最后剩余数忘了加或者循环break写错位置。我调试时经常在拆分循环里加一行cout输出当前push的重量和价值看几组数据就知道哪一步不对。尤其注意数量恰好等于2的幂的情况。比如8很多模板会拆出1、2、4、1这不是重复错误而是因为1、2、4只能表示0到7没法表示8所以必须再留一个1。组合时两个1件组可以同时选正好表示取2件没有问题。如果调试时输出发现这种“看起来重复”的组先别急着删。4.2 dp数组初始值用0还是负无穷这个问题我在博客评论区至少看过十次。判断标准很简单如果题意是“必须恰好把背包装满”那dp[0]0dp[1..bagWeight]负无穷因为只有容量0这个状态是合法起点如果题意只是“容量不超过bagWeight”那所有初始值都是0表示什么都不选也是一种方案。“携带矿石”这类题通常只问能带走的最大价值所以用全0初始化。如果你用了负无穷你会发现dp[bagWeight]可能一直是负的或者即使有正数也偏小因为中间很多未装满状态无法参与转移。反过来如果题意要求恰好装满而你用了全0答案会偏大因为状态会从“空余容量”里带出本来不该存在的组合。做题前先看题目有没有“恰好装满”四个字这比背结论更可靠。4.3 内层循环写成从小到大答案为什么偏大这是多重背包最常见的错误。二进制拆分后每个新物品都是独立的0-1物品用顺序遍历等于允许同一个新物品被反复使用。比如拆出来一个重量4价值8的新物品代表2件矿石顺序遍历时先更新dp[4]8再更新dp[8]时会用dp[4]816相当于这个新物品用了两次也就是原始矿石选了4件甚至更多。原始count可能只有3结果就超了。调试方法也简单把内层循环改成倒序之后再看wa不wa。如果改成倒序就好了说明就是循环方向错了。如果还有问题再检查拆分逻辑。不要一上来就怀疑动态规划公式我见过很多次公式完全正确就是内层循环方向写反了。4.4 多组测试数据时状态没有清空如果OJ的输入有多组我建议代码里直接写成while(cin bagWeight n)每轮循环里重新定义weights、values和dp让它们自动覆盖不会残留上一组数据。如果你定义在循环外面每轮开始就要手动调用clear()或重新赋值。很多人栽在“第一组答案对第二组答案越来越大”上多半就是因为dp数组没清空。另外要注意输出格式卡码网通常要求每个结果占一行。如果题目说“每组输出一个结果空格隔开”再按题目要求调整。不确定时先看一下题目样例的结尾有没有多换行有时候一个换行都会让presentation error。4.5 数据范围与类型溢出如果矿石重量和价值都能到很大比如10^9dp[j]用int可能溢出。通用做法是把dp和values都开成long long代价是内存多一点但至少不会莫名其妙wa。还有拆分时wnum、vnum也可能超出int范围建议在读取后转成long long再乘。我之前习惯用int直到有一次价值一累加成负数才发现是溢出。不过卡码网56的常规数据规模一般不会逼你开long long但养成“看数据范围再定类型”的习惯很重要。看到最大乘积超过2^31就别懒直接long long。尤其在线做题时wa到怀疑人生的情况里类型溢出是排在前三的隐性原因。5. 一点实战心得和扩展5.1 多重背包的三种解法怎么选做这题的时候我先把0-1背包、完全背包、多重背包放在一起对比着刷收获比单独刷大得多。简单说物品数量是1就是0-1背包数量无限就是完全背包数量有限但不是1就是多重背包。多重背包里如果数据小三重循环硬枚举也OK如果数据大先上二进制优化如果还不行再学单调队列优化。单调解法我这次没写因为容易劝退新手。但你心里要知道有这么个东西等以后遇到count10^5、capacity10^5的题目再回头看也行。到那个阶段二进制优化就已经不够看了单调队列的滑动窗口思想反而更占内存和速度优势。5.2 一个小习惯先写暴力再优化个人经验是动态规划题目不要一上来就背模板。先用最笨的三重循环跑通一个样例哪怕超时至少确认模型没理解错然后再把暴力拆解换成二进制拆分。这样出现错误时你能区分是模型问题还是优化手段问题。我刷卡码网56时就是这么做的暴力答案对了再上二进制一次就过。最后再分享一个别处不太会跟你说的细节拆分循环里k的更新顺序要小心。我习惯在push完一个堆之后判断c0如果已经拆完就直接break不继续翻倍k这样k不会在数量很大时溢出。你看到的很多模板把k翻倍写在循环表达式里数据小时没问题数据一极端就可能有未定义行为。自己写的时候留个心。5.3 这题还能怎么变着用多重背包在现实里的影子到处都是比如一笔预算下买几种不同规格的原材料每种材料有库存上限再比如集装箱配货每种货物最多能装几箱。换层皮就是另一道题。把卡码网56吃透后面遇到“有数量限制的装箱问题”“有库存限制的选择问题”基本都能直接套这个模板。如果还想继续深入可以把二进制拆分和完全背包、分组背包放在一起看。三者在动态规划转移方程上只差一点点但正是这点差别决定了循环方向、枚举方式和解法结构。把这几个模型串起来之后你会发现背包问题不是一堆模板而是一套统一的“选与不选”的思想。