NSUOJ 3188这道题在背包专题里算是非常亲民的入门级别了。题面讲的是小P暑假找了一份计时零工手头有好几种工作可以做每种工作花固定时间、赚固定报酬而且每种工作最多只能做固定的次数小P暑假总共只有有限的时间问怎么安排收益最大。剥掉故事外壳这就是一道标准的“多重背包”有若干种物品每种有体积、有价值、有数量上限背包容量有限求最大价值。而它对你真正的意义不是AC那一瞬间的快感而是帮你把“01背包到完全背包再到多重背包”这条递进路线彻底打通顺带把二进制拆分这个高频技巧吃透。这篇就围绕这道题展开从建模、推导、代码实现到踩坑排查一条龙讲清楚。1. 先把这个暑假工问题翻译成背包语言1.1 从题目故事里抽出三个关键参数多重背包的题面往往套了层故事外衣但核心参数永远逃不出三样背包容量、物品体积、物品价值。小P这道题里暑假总时间就是背包容量每份工作单次要花费的时间就是物品体积每份工作能带来的收入就是物品价值而每种工作能做的最大次数就是物品数量上限。把故事里的名词替换成算法里的名词题目立刻变得通透。题目一般会给出几组数据比如总时间上限 Time工作种类数 n然后对每一种工作给出三个数单次耗时 cost单次收入 val最多可做次数 cnt。读入之后你要输出的就是在 Time 时间内最多能赚多少报酬。举个例子方便理解假设暑假总共 10 天有 3 种工作。发传单干 3 天赚 50 块最多干 2 次。家教干 4 天赚 70 块最多干 1 次。搬货干 2 天赚 30 块最多干 3 次。这时问题就变成了总天数只有 10 天每种“工作次数”的组合有上限凑哪些工作能让总收入最大。你当然可以全选 3 次搬货加 1 次家教总共耗时 2*3 4 10收入 30*3 70 160。但这不一定是最优解万一搬货干 3 次加发传单干 2 次耗时 2*3 3*2 12已经超了不算。这种穷举多起来之后就必须上背包 DP而不是拍脑袋。这道题的数据范围一般不会太变态种类数可能在几十到几百容量上限可能在几千到一万左右单种数量上限也不至于大到天上去。这个量级正好卡在“普通多重背包能过但用完全背包写一定错”的位置非常适合用来理解多重背包和完全背包的本质差别。1.2 为什么是多重背包而不是01背包或完全背包很多新手拿到这题第一反应是“每种工作还不简单要么选要么不选直接上 01 背包”。这就是问题所在小P每种工作可以做好几次不是只能做一次。你有 60 天时间一份家教工作 4 天你可以接 15 次家教这在 01 背包里做不到。反过来也有人觉得“次数是有限的那和完全背包有什么区别”区别大了。完全背包对物品数量没有限制同一件物品可以无限拿多重背包限制第 i 种物品最多拿 cnt_i 件。比如搬货工作最多干 3 次那第 4 次就不能再选了而完全背包里它随时可以再拿这个数量天花板就是多重背包区别于完全背包的核心。所以在做这道题之前一定要把三种背包的模型搞清楚01背包每件物品最多选一次。完全背包每件物品可以选无限次。多重背包每件物品最多选有限次cnt_i 次。小P这道题每种工作有明确的“最多可做次数”自然落到了多重背包这一档。做题的第一步永远不是抄模板而是判断题型然后把题面参数映射到对应模型的容量、体积、价值、数量上。这一步想清楚代码反而不是大问题。2. 算法选型朴素拆分、二进制优化、单调队列一条条捋2.1 朴素拆分的直觉与性能瓶颈理解了模型之后最朴素的做法就是“拆”。某份工作最多能做 cnt 次干脆把它当成 cnt 个体积相同、价值相同的独立物品丢进 01 背包里去跑。逻辑上完全正确比如发传单最多干 2 次就拆成两个“发传单物品”每个耗时 3 天、价值 50 块每个都只能选一次。这种做法的复杂度是多少假设物品种类数为 n拆出来的总物品数是所有 cnt_i 之和如果所有 cnt_i 加起来是 M那么加上背包容量为 V总复杂度就是 O(n * maxCnt * V) 或者更准确地说是 O(M * V)。在小范围数据上能过一旦每种物品的 cnt 变大M 就会爆几十上百种物品、每种能选几千次乘上容量轻松去到几千万甚至上亿次运算超时跑不掉。我在初学背包时也是从这里起步的这道题如果范围给得宽裕也能拿分但你要是想在更高强度的题目里用同样的思路十有八九被 TLE 教做人。所以多重背包真正要掌握的是优化手段而第一个优化就是二进制拆分。2.2 二进制优化为什么按1、2、4拆就能覆盖所有情况二进制优化的思路很巧妙把 k 件相同的物品按 1、2、4、8……这样 2 的幂次拆成若干个“物品包”每个包对应一个体积和价值然后对这些包跑 01 背包。核心在于任意一个 0 到 k 之间的整数都能用这些 2 的幂次包组合出来。举个简单的例子。假设某种工作最多能干 10 次那么把它拆成 1、2、4、3 这四份。为什么最后一个是 3因为 1247如果继续拆 8124815 就超过 10 了所以剩下的 3 单独成一包。这样产生的包组合可以表示 0 到 10 之间任意一个次数想选 0 次什么都不选。想选 1 次取第一个包。想选 2 次取第二个包。想选 3 次取第一个包加第二个包。想选 4 次取第三个包。想选 5 次第一包加第三包。想选 6 次第二包加第三包。想选 7 次第一包加第二包加第三包。想选 8 次第四包加第一包加第二包加第三包拆出来的 312410 里的 8等价于拿 3、1、4 里的组合。想选 9 次第四包加第二包加第三包。想选 10 次四包全拿。这背后的数学原理是二进制表示法。1、2、4 已经可以组合出 0 到 7 的所有整数剩下的 3 是用来补足到 10 的高位部分。任何正整数都能通过这种“按位拆分余数封顶”的方式用 O(log k) 个包代替原来的 k 件物品。拆完以后的复杂度就从 O(V * sum(cnt)) 降到了 O(V * sum(log cnt))对于大多数题目来说足够快。NSUOJ 3188 这道题用二进制优化基本都能稳过。实际编码时拆分逻辑可以这样写对于第 i 种物品设当前剩余数量为 k从 1 开始按 2 的幂次拆每拆出一个数量 c就生成一个体积 c * cost、价值 c * val 的“包”然后把 k 减掉 c直到 k 小于 2 的当前幂次最后如果 k 还大于 0就把剩下的 k 作为一个包。2.3 更进一步的单调队列优化选看二进制优化已经足够应付大多数竞赛题但如果你想把多重背包吃得更透要知道还有单调队列优化这条路。它的思路是直接对多重背包的 DP 转移做优化按模体积的余数分组用单调队列维护滑动窗口最大值这样复杂度能做到 O(n * V)。NSUOJ 3188 这道题完全不需要用到单调队列二进制优化就够了。但如果你未来遇到容量 V 很大、数量 cnt 也很大、n 也不小的题目二进制优化可能也会卡在时间上到时候就需要掏出单调队列。这里先埋个伏笔不用急着掌握把二进制优化吃透你已经能解决 80% 的多重背包问题。做这类题我的经验是除非明确知道数据范围逼你必须上单调队列否则二进制优化是性价比最高的选择——代码短、好理解、不容易写错调起来也快。3. 完整实现与代码细节3.1 二进制优化的C参考代码直接给出一份可 AC 的参考实现代码风格偏向竞赛常用写法尽量精简但保留关键注释。#include bits/stdc.h using namespace std; const int MAXT 1000005; int dp[MAXT]; int Time, n; int main() { ios::sync_with_stdio(false); cin.tie(0); cin Time n; // 对每种物品做二进制拆分直接转成 01 背包 for (int i 0; i n; i) { int cost, val, cnt; cin cost val cnt; int k 1; while (cnt k) { int c k * cost; int v k * val; for (int j Time; j c; j--) { dp[j] max(dp[j], dp[j - c] v); } cnt - k; k 1; } // 处理剩余部分 if (cnt 0) { int c cnt * cost; int v cnt * val; for (int j Time; j c; j--) { dp[j] max(dp[j], dp[j - c] v); } } } cout dp[Time] endl; return 0; }这份代码把拆分和 01 背包放在一起做了没有先把包存下来再统一跑背包节省空间也缩短了代码量。注意看内层循环都是从 Time 往 c 的方向倒着遍历这是 01 背包的标准写法目的是保证每个包最多被用一次。如果你正着遍历同一个包可能被重复计算那就变成完全背包的语义了结果会错。3.2 几个容易写错的实现细节第一dp 数组的初始化和容量边界。所有 dp[j] 初始化为 0因为小P可以不干活收益至少是 0。dp[0] 天然是 0不需要额外处理。这里不需要设置负无穷因为每个工作都可以不做你永远不会面临“必须塞满容量”的情况。如果你把“恰好装满”和“不超过容量”搞混初始化方法就会出错。第二拆分时的边界条件。while 循环里判断是 cnt k 而不是 k 剩余量这个顺序不能写反。举个例子cnt 一开始是 10k 依次取 1、2、4当 k 到 8 时cnt 已经在前面减掉了 7剩余 3此时 3 8 不成立循环退出然后剩余 cnt3 单独组成一包。整体拆分结果就是 1、2、4、3。这个逻辑很容易在边界上把等号写丢建议写完以后用笔在纸上顺着跑一遍。第三数据类型的选择。这道题如果数据范围不大int 完全够用。但有些多重背包题目会把容量开到 1e6、价值累加到 1e9 以上那时候 int 就会溢出dp 数组要用 long long。NSUOJ 3188 用 int 没问题不过养成看数据范围的习惯永远是好事。我还见过有人在循环变量上偷懒把 Time 写成外层变量结果数组越界。这类题对数组大小的要求是 dp 的长度至少要比 Time 1 大开数组时宁多勿少。用 vector 动态开会更保险不过竞赛里直接开全局大数组更快因为全局变量默认清零。4. 实战踩坑这题最常见的4个错误4.1 把多重背包当贪心做这大概是新手最容易犯的错而且不是一个人两个人我当年也被这个思路带偏过。题面看起来很像“性价比排序”每种工作有时间和收入那就把每份工作的“时薪”算出来按时薪从高到低排序优先做时薪高的工作直到暑假时间用完。听起来完全合理但这是错的。因为选择是离散的不是连续可无限细分的。一份工作必须花整数天、赚整数钱同样 30 天时间选“高时薪但耗时长的”组合可能浪费掉剩余时间反而不如选“时薪稍低但能刚好填满时间”的组合。背包问题不满足贪心选择性质局部最优推不出全局最优多重背包也不例外。这道题让你用 DP 而不是排序就是在提醒你这个点。4.2 初始化写错导致答案全是0很多从“恰好装满背包”练过来的选手会把 dp 初始化成这样memset(dp, 0x80, sizeof dp); // 非常小的负数 dp[0] 0;这样写是处理“必须恰好用完时间”的题目用的。但小P的暑假工问题里时间没花完也是可以的你赚到钱不用把时间卡得死死的。如果你按“恰好装满”去初始化有些本来合法的方案会变成负无穷最后 dp[Time] 输出不出来正确答案。正确的做法是全部初始化为 0。只有当题目要求“正好装满容量时最大价值”才需要负无穷初始化。拿到题先看它说的是“最多能赚多少”还是“恰好把时间用完最多能赚多少”这两个说法差一个字代码差一行初始化但结果天差地别。4.3 二进制拆分时余数处理遗漏二进制拆分的经典坑就是最后剩下的 cnt 忘了处理。比如 cnt 等于 101、2、4 拆完之后剩下 3如果你只处理了 1、2、4那你就永远没法选 8、9、10 次答案自然偏低。还有另一种情况是拆分时把负数拆进去。如果 while 循环的条件写成 cnt k当 cnt 和 k 相等的时候循环会提前退出最后剩下的正好是 k单独处理时没问题但如果条件写错成 cnt kcnt k 时循环退出确实会把 cnt 完整保留不过这样也对。关键是每次拆分时都要严格保证 cnt 是剩余次数不能在循环里改坏它。我的建议是写一个辅助函数来拆分比如void split(int cost, int val, int cnt) { for (int k 1; cnt 0; k 1) { int take min(k, cnt); int c take * cost; int v take * val; for (int j Time; j c; j--) { dp[j] max(dp[j], dp[j - c] v); } cnt - take; } }这个写法更不容易漏掉余数也更好记。4.4 数组大小和容量边界没算明白这类题经常有人 TLE 或 RE原因不是算法错而是数组开小了。有些题目给的 Time 可能是 100000dp 只开到 100005下标从 0 到 Time 是 100001 个位置100005 确实够但要小心某些测点 Time 可能到 500000。开数组之前一定先看数据范围最大值。背包容量如果不确定还有一种稳妥做法是开 vectorvectorint dp(Time 1, 0);这样不会越界代价是稍微慢一点点但安全。竞赛题里我更喜欢全局数组因为快但你必须把最大容量吃准。5. 题目之外:多重背包模型的现实应用与延伸5.1 背包问题的现实场景别觉得背包问题只在 OJ 里出现这类“有限资源下选一组东西使收益最大”的模型在现实中到处都是。比如做电商库存管理你有固定预算背包容量多个商品物品种类每个商品有进货成本体积、预期利润价值、最多可采购数量数量上限问怎么分配预算让总利润最高。这就是个标准多重背包。再比如排班问题一个月有 30 天可排班几种不同类型的任务可以接每种任务耗时不同、报酬不同、一个月最多能接多少次问怎么排收益最高。同样逃不出这个模型。理解背包问题的本质其实是在训练一种“资源分配”的直觉什么约束是可变的、什么是不可突破的天花板、每种选择背后有什么代价。这种抽象能力写业务代码的时候照样用得上。5.2 从这道题出发的进阶路线如果你刚 AC 了 NSUOJ 3188恭喜你的背包之路刚开了个好头。我建议按这个顺序继续往下刷先回头把 01 背包和完全背包各找两道题巩固确保正序倒序遍历的区别牢牢刻在脑子里。再做几道多重背包的变式比如题目稍微改改让每种工作必须至少做一次或者加一个“每种工作第一次做有额外奖励”的条件这会逼你想清楚状态设计。最后再接触混合背包01 完全 多重混在一起、二维费用背包、分组背包。你会发现核心思路全都相通先判断物品属于哪种类型对不同类型的物品分别用不同的转移方式。多重背包的掌握程度可以用一句话检验你能否在五分钟内把一道题从“读题”抽象成“给每种物品的容量、价值、数量”并选对优化策略。能说明你已经不是背模板的选手了而是真的理解了背包问题的结构。再分享一个我自己的小习惯AC 之后别急着下一题把代码里的 while 拆分单独抽出来想一下如果改成递归写法或者用数组预存所有分解后的包有什么区别。多问自己几个“如果”比无脑刷十道题都管用。这道题虽然简单但它演示的“有限次选择如何降维成 01 背包”的思路会在你之后遇到的所有组合优化问题里反复出现。