卡码网第56题《携带矿石资源》是动态规划背包专题里非常有代表性的一道多重背包应用题。如果你跟着《代码随想录》的节奏刷到这里大概率会产生一个很真实的困惑前面0-1背包的每个物品只有一个完全背包的每个物品都有无限个都挺好处理可现在每种矿石是有数量上限的直接当0-1背包拆吧物品总数可能爆炸当完全背包处理吧又明显违背题目里“最多k个”的限制。这篇文章我把从暴力三重循环、到二进制拆分、再到单调队列优化的完整思考过程摊开讲清楚尤其是“二进制拆分到底在拆什么、为什么拆完再跑0-1背包答案依然正确”这种多数教程一笔带过的关键点。不管你是刚学背包的新手还是准备笔试面试想快速捡起多重背包的老手都建议花十几分钟把这道题彻底吃透。另外先提醒一句卡码网和力扣的刷题模式不太一样它是标准ACM风格需要自己写main函数、自己读标准输入不能像力扣那样只填空函数。所以下面给的代码都是完整可运行的直接复制到编辑器里就能跑。1. 题目拆解卡码网56到底在考什么背包模型1.1 输入输出先看明白类型判断是关键题目大意很直白一辆卡车载重为C有N种矿石每种矿石有重量w、价值v、数量上限k。问你最多能带走多少价值的矿石。这里最核心的一个判断点是每种矿石的数量不是1个也不是无限个而是有限个。就凭这一点它既不是0-1背包也不是完全背包而是多重背包。这三种背包模型极其容易混我先把它们的关系列成一个表背包类型每种物品可选个数典型转移方式复杂度特征0-1背包0或1个容量倒序循环O(N*C)完全背包0个或任意多个容量正序循环O(N*C)多重背包0到k个k有限枚举件数或拆分物品O(NCK) 起步判断一个题目到底属于哪一类背包别看题目名字看约束描述如果题干说“每个最多选一次”是0-1如果“数量不限”是完全如果“该种物品最多k件”“库存有限”这类词就是多重背包。《携带矿石资源》里的“每种矿石最多携带k个”就是典型的多重背包信号。1.2 为啥不能直接贪心或套前面的背包模板有同学看到“求最大价值”第一反应是按单位价值排序从单位价值高的开始装。这个思路在可以“只装一部分”的场景下有效但背包问题是离散的每个矿石要么装要么不装不能切半个进去。我举个简单反例卡车载重是3矿石A重量2、价值3、数量1矿石B重量3、价值4、数量1。按单位价值排序A是1.5B约1.33贪心先装A容量剩1什么都装不下总价值3但实际最优方案是直接装B总价值4。所以贪心直接淘汰。套用完全背包模板也不行因为完全背包允许某种物品选无限个而这里数量被k限制了。如果一味套完全背包结果一定会偏大。也有同学硬把它当成0-1背包把每种矿石拆成k个体积相同、价值相同的物品这思路方向是对的但后面会看到直接拆会带来物品数量膨胀的问题。1.3 数据规模决定你该用哪种解法刷题不能只会一种写法还要会根据数据范围选算法。多重背包的常见套路有三层递进数据很小时N、C、k都在几十上百直接三重循环枚举取几件最朴素也好写。数据常规时k达到几千甚至几万三重循环会超时用二进制拆分把多重背包转成0-1背包这是最推荐的“性价比之王”。数据极大时容量C到1e5甚至1e6k也很大二进制拆分的物品总数可能还是偏大此时上单调队列优化到O(N*C)。我在实际做题中见过不少人在数据范围上栽跟头题目给的是小数据非要用单调队列把代码写复杂题目给的是大数据还在用朴素三重循环硬跑最后TLE。所以读题时先看范围再定解法。2. 从0-1到多重最暴力的三重循环怎么从原理写出来2.1 状态定义与转移方程的来源先用老套路定义状态dp[j]表示当前已经处理完前若干种矿石后载重为j时能带走的最大价值。对于当前这种矿石我们可以选择带走t件t的范围是0到k而且t*w不能超过j。于是最自然的转移方程就出来了dp[j] max(dp[j], dp[j - tw] tv)其中1 t k且 j - t*w 0。这个方程的意思很朴素要么不拿当前这种矿石维持dp[j]要么拿t件腾出t*w的载重然后加上t件矿石的价值。把所有可能的t都试一遍取最大值。2.2 一维滚动数组写法的循环顺序用二维数组当然也能写但空间复杂度是O(N*C)大多数情况没必要。用一维dp数组做滚动更新写法如下#include bits/stdc.h using namespace std; int main() { int C, N; // 兼容单组/多组输入 while (cin C N) { vectorint dp(C 1, 0); for (int i 0; i N; i) { int w, v, k; cin w v k; // 枚举当前载重 for (int j C; j 0; j--) { // 枚举取 t 件当前矿石 for (int t 1; t k t * w j; t) { dp[j] max(dp[j], dp[j - t * w] t * v); } } } cout dp[C] endl; } return 0; }这段代码里有一个特别需要注意的细节容量j的循环一定要从大到小。为什么因为在三重循环中我们希望在计算dp[j]时dp[j - tw]还是上一轮的旧值而不是这一轮已经被更新过的值。如果j从小到大循环当计算dp[j]时dp[j - tw]可能已经因为“当前这种矿石”被更新过了这相当于允许同一轮里多次使用当前矿石语义就变成了完全背包结果会偏大。我当年第一次写多重背包就踩过这个坑把j写成正序样例数据小没跑出来一提交答案偏大。后来拿了个大k值的数据对拍才发现是滚动数组方向错了。记住一句话0-1背包和多重背包容量维度倒序完全背包容量维度正序。2.3 复杂度分析与什么时候会超时朴素三重循环的复杂度是O(N * C * K)这里的K是平均每种矿石的数量。假设N100C1000每个k1000那一共有1e8次操作在大多数OJ上基本是超时的边缘。如果C和k再大一点比如1e4、1e5三重循环跑起来就是灾难。那问题出在哪出在内层枚举t上。对于同一种矿石我们其实做了很多重复计算每次都在试“拿1件、2件、3件……一直到k件”。能不能把这些“件数组合”提前打包让复杂度降下来这就引出下一节的二进制拆分。3. 二进制拆分把有限个数变成2的幂组合3.1 拆的不是物品是“件数”我第一次学二进制拆分时最大的困惑在于为什么k件矿石能被拆成1、2、4、8这样的组然后每组当成一个新物品去做0-1背包结果还是对的这里的关键认知是我们要拆的不是“1个矿石”而是“矿石的件数范围”。也就是说把“可以选择0到k件”这个范围拆成若干个小组每个小组预先是打包好的小组内件数固定。只要这些小组的件数组合起来能覆盖0到k之间的所有整数那么做0-1背包时选与不选这些小组就能模拟出“选任意件原矿石”的效果。为什么2的幂能做到因为任意正整数k都可以拆成若干个2的幂之和而且这些2的幂的子集和能表示0到k之间的所有整数。可以类比人民币的纸币面额你不需要准备k张1元只需要准备1元、2元、4元……这些面额就能组合出任意金额。举个例子k13拆成1、2、4、6。这四组能组合出0到13的任意数吗能。1、2、4可以组合出0到7再加上6就是6到13整体覆盖0到13。虽然看起来比标准二进制多了一个6但6是13减掉124后的余数必须补上否则最多只能表示7漏掉了8到13的情况。3.2 拆分代码与边界处理拆分的代码非常短但边界条件很容易写错。我直接给出一个比较稳妥的模板struct Item { long long weight; long long value; }; vectorItem goods; for (int i 0; i N; i) { int w, v, k; cin w v k; // 注意如果 k 0直接跳过别把0件物品塞进去 if (k 0) continue; int cnt 1; while (k cnt) { goods.push_back({1LL * w * cnt, 1LL * v * cnt}); k - cnt; cnt 1; } // 剩下的余数必须单独成一组否则会漏解 if (k 0) { goods.push_back({1LL * w * k, 1LL * v * k}); } }拆分的核心逻辑是每次从k中切出一块cntcnt从1开始每次翻倍直到k小于cnt说明剩下的数量无法再凑出下一个整倍数的2的幂这时候把它单独作为一个余数组。这里有几个边界要注意如果k刚好是2的幂比如4按这个循环会拆成1、2、1最后那个1是余数。有的资料会写“拆成1、2、4”其实从数学上说1、2、1也能完整表示0到4因为112组合出的最大值是4且子集和覆盖0到4。所以我一直强调不要纠结拆出来的组具体长什么样核心标准只有一个拆出来的所有组的件数之和等于原k且这些组能组合出1到k的任意件数。满足这两条01背包结果就一定正确。如果k很大cnt不断左移可能溢出。虽然通常在循环退出前就结束了但保险起见可以用long long存cnt。每组的重量是wcnt价值是vcnt不是只存cnt。3.3 拆完之后如何接01背包模板拆完之后goods数组里每个元素就是一个标准的0-1背包物品选或不选。剩下的工作直接套0-1背包模板容量倒序vectorlong long dp(C 1, 0); for (const Item it : goods) { for (int j C; j it.weight; j--) { dp[j] max(dp[j], dp[j - it.weight] it.value); } } cout dp[C] endl;到这里复杂度从O(NCK)降到了O(sum(log2(k_i)) * C)。物品总数从sum(k_i)变成sum(log2(k_i))效果是非常明显的。举个例子k10000原来要拆10000个物品现在只需要拆成1、2、4、8、16、32、64、128、256、512、1024、2048、4096再加一个余数4878一共13个物品。这个优化比大多数人想象的要大得多。4. 进阶优化单调队列把容量维度拉满4.1 什么时候值得上单调队列二进制拆分已经能解决绝大多数题目但有一种情况它还不够当容量C非常大比如1e5甚至1e6同时每种物品的k也很大时二进制拆分后的物品总数大约是Nlog2(K)再做一遍O(totalItemsC)的0-1背包操作次数可能还是达到1e8以上。此时就要请出多重背包的终极形态单调队列优化。它的核心思想是直接对状态转移方程下手把“枚举取t件”的过程用滑动窗口最大值来替代整体复杂度压到O(N*C)。说实话一般笔试面试中能写出二进制拆分已经足够单调队列更多是作为知识储备和进阶能力。但如果你已经能熟练写出二进制拆分我建议还是把单调队列的原理理解一遍因为它能让你对dp优化的理解上一个台阶。4.2 推导状态转移的“同余分组”先回到转移方程dp[j] max( pre[j - tw] tv )其中0 t kj - t*w 0。这里pre表示上一轮的结果。注意一个关键观察j和j - tw对w取模的结果是一样的。也就是说载重j只会从跟它同余的那些j - tw转移过来。于是我可以把j按下标除以w的余数r分成w类。对于固定的余数r设j r pw那么j - tw r (p-t)*w。令q p - t原方程就变成dp[r pw] max( pre[r qw] (p-q)v ) pv max( pre[r qw] - qv )其中q的范围是 [p-k, p]且q 0。看这个式子右边的max部分只依赖于q区间内的“pre[r qw] - qv”这是一个典型的滑动窗口最大值问题随着p增大窗口左边界p-k右移右边界p也右移。单调队列就是专门处理这种“固定窗口长度、求窗口最大值”的数据结构。4.3 滑动窗口最大值维护的代码骨架每个物品处理一遍核心代码如下vectorlong long dp(C 1, 0); for (int i 0; i N; i) { int w, v, k; cin w v k; vectorlong long pre dp; // 拷贝上一轮结果 dequeint q; for (int r 0; r w; r) { q.clear(); // p 表示 j r p*w 里的系数 for (int p 0; r p * w C; p) { int idx r p * w; // 1. 弹出窗口左边超出范围的 if (!q.empty() q.front() p - k) { q.pop_front(); } // 2. 维护单调递减队列用旧值比较 while (!q.empty() pre[r q.back() * w] - q.back() * v pre[idx] - p * v) { q.pop_back(); } q.push_back(p); // 3. 队首就是窗口内最大值对应的 q dp[idx] pre[r q.front() * w] - q.front() * v p * v; } } }这个代码我第一次写的时候在两步上卡了壳一是忘了拷贝pre直接用dp做比较结果更新后的值污染了队列二是窗口范围没把t0的情况算进去导致k件物品全部不选的情况被漏掉。写的时候务必想清楚窗口长度是k1因为你允许从0件选到k件。值得注意的是单调队列优化虽然快但代码复杂度和理解成本都高。我还是建议先掌握二进制拆分把它写熟写透再考虑是否进阶单调队列。在面试现场能把二进制拆分讲清楚、并能分析出复杂度已经是不错的加分项。5. 完整AC代码三个可直接落地的版本5.1 C版本二进制拆分推荐背诵模板这个版本是我最推荐背诵的模板代码短、思路清晰、不容易写错#include bits/stdc.h using namespace std; struct Item { long long weight; long long value; }; int main() { int C, N; while (cin C N) { vectorItem goods; for (int i 0; i N; i) { int w, v, k; cin w v k; if (k 0) continue; int cnt 1; while (k cnt) { goods.push_back({1LL * w * cnt, 1LL * v * cnt}); k - cnt; cnt 1; } if (k 0) { goods.push_back({1LL * w * k, 1LL * v * k}); } } vectorlong long dp(C 1, 0); for (const Item it : goods) { for (int j C; j (int)it.weight; j--) { dp[j] max(dp[j], dp[j - it.weight] it.value); } } cout dp[C] endl; } return 0; }需要注意dp数组用long long是因为当N、k、v都很大时总价值可能超过int范围。有些题目数据不大用int也能过但写成long long不会亏。5.2 Java版本ACM模式导入与类名细节如果你习惯用Java刷卡码网注意类名必须是Main否则提交会报编译错。代码逻辑和C完全一样import java.util.*; public class Main { static class Item { long weight; long value; Item(long weight, long value) { this.weight weight; this.value value; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); // 如果平台提示有多组用例套一层 while (sc.hasNextInt()) int C sc.nextInt(); int N sc.nextInt(); ListItem goods new ArrayList(); for (int i 0; i N; i) { int w sc.nextInt(); int v sc.nextInt(); int k sc.nextInt(); if (k 0) continue; int cnt 1; while (k cnt) { goods.add(new Item((long) w * cnt, (long) v * cnt)); k - cnt; cnt 1; } if (k 0) { goods.add(new Item((long) w * k, (long) v * k)); } } long[] dp new long[C 1]; for (Item it : goods) { for (int j C; j it.weight; j--) { dp[j] Math.max(dp[j], dp[j - (int) it.weight] it.value); } } System.out.println(dp[C]); } }Java版本要注意cnt 1在k较大时可能溢出int好在循环退出条件通常会在溢出前拦截但如果你不放心可以把cnt和k都声明为long。5.3 手算验证用一组小数据走一遍流程光看代码不踏实我拿一组小数据手动走一遍假设载重C10两种矿石矿石1重量2价值3数量3矿石2重量3价值4数量2第一步对矿石1做二进制拆分k3拆成1、2得到两个新物品(2,3)和(4,6)。第二步对矿石2做二进制拆分k2拆成1、1得到两个新物品(3,4)和(3,4)。第三步跑01背包。容量10时最优组合是矿石1拿2件重量4价值6矿石2拿2件重量6价值8总重量10总价值14。另一种方案是矿石1拿3件重量6价值9加上矿石2拿1件重量3价值4总价值13比14小。所以最终答案是14。你可以试着在纸上把四组新物品的01背包dp表填一遍会发现在物品组层面做选择得到的组合方式确实等价于“每种矿石选0到k件”。这就是二进制拆分正确性的直观验证。6. 常见问题与排查技巧实录6.1 拆分结果加起来不等于原数量的自查我第一次写二进制拆分时经常在“余数”这里翻车。拆完组数对了但有的组件数是0有的组漏了答案错误。我的习惯是拆完先自查一遍把拆出来的每组件数累加看是不是等于原始k。由于每个新物品的weight都是w的整数倍其实可以用weight除以w得到件数。常见错误是循环条件写成了while(k cnt)当k恰好等于cnt时余数变成0导致少拆一组。while循环结束后漏写最后那个if(k 0)余数直接丢了。把k是0的物品也拆进去多出一组重量0、价值0的物品虽然不影响答案但会拖慢程序。自查代码可以这样写int sumCheck 0; for (auto it : goods) { sumCheck it.weight / w; // w是当前原始矿石的重量 } // 理论上 sumCheck 应该等于原始 k如果你在调试时发现sumCheck不等于原始k不要急着检查01背包先把拆分逻辑单独测一遍。6.2 读入顺序与多组输入的处理卡码网这题的输入格式在不同版本描述里可能略有差异有的题面第一行是“载重 种类”有的排序是“载重C 数量N”还有的每行三个数顺序可能是重量、价值、数量。写代码时不能凭记忆盲写要以题目描述为准。我在多个OJ之间切换时吃过亏同一个算法模板在A平台能过在B平台读入顺序反了直接全错。所以拿到题目先花30秒看输入输出描述特别是每行的数到底按什么顺序给。别看样例的大小就对号入座有时候样例恰好有迷惑性。多组输入的问题也值得提前处理。虽然有些题目明确只有一组输入但我在C模板里习惯写成while(cin C N)这样就算平台偷偷塞了多组样例代码也能兼容。如果题目只有一组这个while只会执行一次完全不影响。6.3 正序倒序的区分与调试方法这是所有背包问题新手都绕不开的点。多重背包里如果我们用“枚举t件”的朴素写法容量j必须倒序如果我们用二进制拆分后跑01背包容量j也必须倒序只有完全背包的裸模板才用正序。怎么快速判断自己有没有写反我分享一个非常实用的对拍技巧用一个很小的数据比如容量6、一种物品重量3价值5数量2手算出答案应该是10只能拿2件重量6价值10。如果代码输出大于10比如输出了15那多半是循环方向错了导致同一个物品被反复多次计入退化成完全背包。这个技巧我几乎每次讲解背包都会提因为比起看代码用“反例数据”验证是更直接的排错方式。多准备几组小数据在手边调试效率能高很多。6.4 常见问题速查表现象可能原因排查方向dp结果明显偏大01背包容量循环写成了正序退化成完全背包把内层容量循环改为从大到小拆出的物品组数和预期不符循环退出后余数没补或k为0没过滤自查拆分后的件数总和是否等于原始k代码运行超时还在用朴素三重循环数据规模较大改用二进制拆分或上单调队列优化数组下标越界dp数组大小写成了C而合法下标最大是C确保vector大小为C1结果少算了一部分拆分的while循环条件写错导致2的幂组没拆全逐行打印goods数组观察每组件数Java提交编译不过类名不是Main确认public class Main这些坑都不是偏门冷知识而是每一个认真刷过多重背包的人都会遇到的高频问题。我每次复刷这道题都会刻意在草稿纸上把拆分、读入、循环方向这三件事重新过一遍为的就是防止手生。说几个我实际刷题过程中的体会。多重背包在代码随想录的题单里篇幅不大但它是个很好的承上启下位置往上承接0-1和完全背包往下衔接单调队列优化甚至分组背包。我建议大家不管面试用不用得到都至少把二进制拆分这一步手写三遍写到自己能在一分钟之内把拆分循环写对。我第一次写的时候余数经常会漏后来养成了习惯拆完先数一遍拆出来的组数加起来是否等于原来的k。这个自查习惯帮我避开了大量边界错误。如果后续想拓展可以把这道题和“混合背包”有的物品只能选一次、有的物品可以选无限次、有的物品限次数对比着刷你会发现多重背包的拆分思路在其中依然成立只是需要在0-1和完全背包之间切换状态转移。祝刷题顺利。