最近刷 NSUOJ 的时候碰到了 3188 这道题题名叫“小P的暑假工”。第一眼看到这个名字以为是个模拟题或者贪心题毕竟暑假工安排听上去挺像排班表的。结果点进去读了一遍题背包问题而且不是普通的 01 背包也不是完全背包是典型的多重背包。这道题数据范围设置得挺有讲究如果你只会暴力拆分大概率是会超时的。但只要你把多重背包的二进制优化吃透了代码也就二十来行非常适合拿来当多重背包的入门训练题。这篇文章我就以 NSUOJ 3188 为例把从题目建模、状态定义、三种解法到最终的 AC 代码和踩坑记录全部捋一遍。不论你是刚学背包问题的新手还是准备复习多重背包的选手这篇应该都能给你一点实在的东西。1. 题目建模小P的暑假工到底在考什么1.1 从故事背景到背包模型先说一下题目大意。小P放暑假想打工赚钱他面前有若干种工作每种工作都有一个“做一次要花多少天”的耗时也有一个“做一次能赚多少钱”的收益而且每种工作不是想做多少次就做多少次数量是有限制的。小P暑假一共有 T 天问他在这些限制下最多能赚多少钱。题意听起来很生活化但剥掉故事外壳之后它就是一个标准的多重背包模型。我们把“工作的种类”看成物品的“种类”把“做一次这个工作需要的时间”看成这个物品的“体积”把“做一次赚的钱”看成物品的“价值”把“这个工作最多能做多少次”看成物品的“数量上限”最后把“暑假总天数 T”看成背包的“容量”。所以问题就变成了有 N 种物品第 i 种物品的体积是 w[i]价值是 v[i]数量上限是 c[i]现在有一个容量为 T 的背包问能装下的最大价值是多少。这里我强烈建议刚开始学背包的同学每做一道背包题都先动手把题目里的故事要素和背包模型里的要素做一次映射。我接触过不少选手做多了之后拿到题直接套模板结果题目一变就翻车根源就在于没有真正理解这个映射关系。1.2 为什么是多重背包而不是 01 背包或完全背包很多新手在判断背包类型的时候会犹豫这个工作能做多次那不就是完全背包吗答案是不一定。完全背包要求每种物品可以取无限次但题目明确说了每种工作有数量限制这就是“有限次数”和完全背包的“无限次数”有本质区别。我们可以用一个直白的类比01 背包是“一个物品选或不选”完全背包是“一个物品你可以拿无限个”多重背包则是“一个物品你可以拿若干个但最多不能超过某个数”。暑假工这个场景天然就是多重背包因为现实中一份工作不可能让你无限做下去要么岗位有限要么时间有限。还有一个判断技巧就是看数据范围。如果一道题数据量很大而且题目里有“最多可以做 c 次”“库存有限”“某种物品限购”这类关键词九成就是多重背包。反过来如果题目说的是“不限次数”“任意多个”那才是完全背包的范畴。2. 从暴力到优化多重背包的三种经典解法2.1 暴力拆解法正确但会超时的方案先讲最朴素的做法。既然第 i 种物品最多能拿 c[i] 个那我直接在状态转移的时候枚举拿几个不就行了我们定义 dp[j] 表示“总耗时为 j 天时能获得的最大收益”。第 i 种工作做 k 次需要耗时 k * w[i] 天收益是 k * v[i]那么状态转移就是dp[j] max(dp[j - k * w[i]] k * v[i])其中 0 k * w[i] j且 k c[i]写出来是三重循环外层枚举物品种类中层枚举背包容量内层枚举拿的数量for (int i 0; i N; i) { for (int j T; j 0; j--) { for (int k 0; k c[i] k * w[i] j; k) { dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]); } } }这种做法逻辑上没有任何问题答案一定是正确的。但它的时间复杂度是 O(N * T * C)如果 N、T、C 稍微大一点比如都到 1000那就是十亿次运算直接超时没商量。我第一次做多重背包的时候就是先写了暴力版本样例过了心里美滋滋结果一交TLE绿色变红色瞬间清醒。所以暴力拆解只能用来验算思路不能直接作为正式提交方案。2.2 二进制优化把多重背包拆成 01 背包既然暴力枚举数量不行那我们换个思路能不能把多重背包转换成我们已经很熟练的 01 背包直接拆肯定是拆不了的因为每种物品有 c[i] 个你拆成 c[i] 个独立的物品物品总数会非常大复杂度还是 O(N * T * C)。这时候就要用到二进制优化的核心思想一个数 c可以用若干个 2 的幂次组合出来。具体来说我们把数量 c 拆成几个部分1、2、4、8、……一直拆到不能再拆为止最后如果还剩一个余数 r就再把 r 单独作为一组。举个例子假设 c 13那么 13 1 2 4 6拆出来的组数只有 4 个比直接拆成 13 个物品少得多。为什么这样拆不会丢状态因为任何 0 到 13 之间的整数都能用 1、2、4、6 这四组数中的若干组拼出来。比如 5 1 47 1 69 1 2 6全部都能表示。也就是说我原来枚举 k 从 0 到 13 的所有取法用这 4 组物品做 01 背包同样能覆盖所有可能取的数量。代码实现也很简单int cnt c[i]; for (int k 1; cnt 0; k 1) { int take min(k, cnt); items.push_back({w[i] * take, v[i] * take}); cnt - take; }这段代码里的 take 就是当前这一组物品对应的“数量”把原物品复制 take 份合成一个新的物品。最后 items 里存的就是所有拆出来的新物品。拆完之后整个问题就变成了纯 01 背包再用一维滚动数组逆序遍历容量即可。二进制优化后每个物品被拆成了 log(c[i]) 个总物品数是所有 log(c[i]) 之和时间复杂度降到 O(N * T * logC)。在 N、T、C 都是 1000 的情况下一千万次左右完全够用。这里再强调一下为什么不是用十进制拆而是用二进制拆因为二进制拆分能够以 log 级别的最少组数覆盖 0 到 c 的所有整数这是信息论层面的最优方案之一。你如果拆成 1、2、3、4、5……那总组数还是 O(c)没有优化意义。2.3 进阶方案单调队列优化如果你对性能要求更高多重背包还有更优的解法那就是单调队列优化时间复杂度可以做到 O(N * T)。单调队列优化的核心思路是把容量 j 按照 j mod w[i] 分成若干组每一组内部用单调队列维护一个滑动窗口最大值。因为 dp[j] 只会从同一组的 dp[j - k * w[i]] 转移过来所以每一组是独立的可以用队列优化。不过说实话在绝大多数比赛里二进制优化已经足够应付多重背包了。单调队列优化理解起来门槛更高代码也更长属于“听过就行需要时再补”的知识点。我建议新手先掌握二进制优化把 3188 这题 AC然后再去研究单调队列学习曲线会更舒服。3. 完整 AC 代码与核心实现细节3.1 二进制优化版本的 AC 代码下面给出我提交通过的完整代码题目是多组输入所以外层套了一个 while(cin n T)。#include bits/stdc.h using namespace std; const int MAXT 1005; int dp[MAXT]; struct Item { int w, v; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, T; while (cin n T) { vectorItem items; for (int i 0; i n; i) { int w, v, c; cin w v c; int cnt c; for (int k 1; cnt 0; k 1) { int take min(k, cnt); items.push_back({w * take, v * take}); cnt - take; } } memset(dp, 0, sizeof(dp)); for (auto it : items) { for (int j T; j it.w; j--) { dp[j] max(dp[j], dp[j - it.w] it.v); } } cout dp[T] \n; } return 0; }提交结果是我预想中的 AC运行时间也很短。这题的 N、T、C 范围具体是多少我记不太清了但二进制优化过之后完全不需要担心超时问题。3.2 一维滚动数组为什么必须逆序遍历这里的细节很多人容易忽略拆完物品之后做的是 01 背包所以容量循环必须从大到小。原因在于一维数组 dp[j] 在更新时dp[j - w] 可能已经被同一轮循环更新过。如果从小到大遍历那么某个物品会被反复使用这就变成了完全背包。反过来从大到小遍历dp[j - w] 还是上一轮的旧值这个物品就只会被使用一次符合 01 背包的语义。我把这个总结成一句话逆序是 01 背包的标志顺序是完全背包的标志。看到滚动数组先问自己当前这个阶段是 01 背包还是完全背包再决定遍历方向。另外一个常见问题是dp 数组初始化成 0 还是负无穷这取决于题目问的是“不超过容量 T”还是“恰好装满容量 T”。3188 这道题问的是暑假 T 天内最多赚多少钱做不完 T 天也没关系所以是不超过初始化全 0 即可。如果换成“恰好用满 T 天”的变式就要把 dp[0] 初始化为 0其余初始化为负无穷否则你无法区分“凑不齐”和“凑齐了但价值为 0”这两种情况。4. 现场复盘几个差点让我 WA 的坑4.1 二进制拆分时循环变量别被自己改乱第一次写二进制拆分的时候我图省事写了这样一个循环for (int k 1; k c; k 1) { items.push_back({w * k, v * k}); }这个写法看着没什么问题但实际上它忽略了一个关键点如果 c 13那么 k 会依次取 1、2、4、8然后循环条件 k 13 还会再让 k 变成 16此时才跳出。看起来好像没错错在少处理了余数 6。13 被拆成了 1、2、4、8这四个数能组合出的最大数是 15超过 13但中间的 13 本身能表示吗1 4 8 13能表示。但这四个数组合起来会覆盖 13 到 15 的范围出现了超出实际数量的情况也就是你可能会让某件物品被取 13 件以上这就不合法了。所以正确做法必须引入 take 变量保证每一组拆分出来的数量之和恰好等于 cint cnt c; for (int k 1; cnt 0; k 1) { int take min(k, cnt); items.push_back({w * take, v * take}); cnt - take; }每次从 cnt 里减去已经拆掉的部分最后 cnt 一定是 0。这样拆完后所有组加起来正好是原数量 c不会多也不会少。4.2 多组输入容易忘记重置状态3188 这题是多组输入如果你用全局数组存 dp那么在每组数据开始之前一定要重置 dp 数组。我一开始没注意上一组数据的答案残留到了下一组结果第二组样例的输出直接比正确答案大了一截找了半天才发现是初始化问题。后来我习惯在每个 while 循环开头都写一句 memset(dp, 0, sizeof(dp))或者用 fill(dp, dp T 1, 0)再也不会因为这种低级错误浪费调试时间。另外用 vector 来存拆分后的物品每组数据开始前会自动清空这个设计在写多组数据的题时很省心。如果你开的是定长数组记得也要用一个计数器来记录当前物品个数不能直接用全局 n 去遍历。4.3 大数量下的溢出隐患这个题如果数量给得特别大比如 c 达到 1e9那么 w * c 可能会直接溢出 int。虽然 3188 的数据范围大概率没那么变态但养成用 long long 的习惯总没有坏处。我在做其他背包题时曾因为 int 溢出吃过亏那次是二维费用的多重背包所有物品加起来的价值和超过了 2^31结果答案直接变负数WA 得莫名其妙。从那以后只要涉及价值或数量的乘法运算我都会多加一层确认必要时直接用 long long。5. 从 3188 延伸出去多重背包还能怎么变5.1 加一个“恰好装满”的限定条件3188 是求不超过 T 天的最大收益但如果题目改成“小P必须正好干满 T 天”那处理方式就变了。做法是初始化 dp[0] 0其余 dp[j] -INF一个很小的负值然后转移逻辑不变。因为在转移过程中只有能恰好装满的容量 j 才会被更新成有效值凑不齐的状态会一直保持负无穷最后 dp[T] 如果是负无穷就说明无解不然就是恰好装满的最大收益。我建议你做完这道题后自己把初始化改一改多测试几组数据对比一下“不超过”和“恰好”两种问法在答案上的差异能加深对背包初始化的理解。5.2 混合背包物品数量有无限个也有有限个有时候题目会同时存在三种物品有的只能用一次有的可以用无限次有的最多只能用 c 次。这种就叫混合背包。处理思路也不复杂如果是 01 背包就按 01 背包做如果是完全背包就按完全背包做如果是多重背包就先二进制拆分再按 01 背包做。整体上只需在一个循环里判断类型分别处理即可。3188 里的多重背包部分其实就是混合背包中最需要动脑的一个环节。5.3 多重背包求方案数如果题目不求最大收益而是问“有多少种安排工作的方法能赚到某个目标金额”那就把 dp 数组的含义从“最大价值”改成“方案数”转移也改成加法。具体来说dp[j] dp[j - k * w[i]]初始化 dp[0] 1。注意方案数可能会非常大题目一般会给一个模数记得取模。多重背包求方案数的二进制优化思路和普通多重背包一模一样唯一的区别是 01 背包部分的加法和取模。6. 写在最后这道题带给我的经验NSUOJ 3188 这道题本身不算难但它把多重背包最核心的几个知识点都串起来了状态定义、类型判断、二进制优化、滚动数组遍历顺序、初始化细节。我觉得它非常适合拿来当多重背包的入门题刷完这一道再去碰别的多重背包题目会顺畅很多。我个人在给这道题写题解的时候最大的体会是背包问题的代码模板固然重要但比模板更重要的是“判断题型”和“确定转移方向”这两件事。很多选手看到题目就去套模板结果 01 背包的代码改了改就交上去遇到多重背包直接 WA。如果你能把题目里的故事准确映射成“每种物品有几个、体积多少、价值多少、背包容积多少”那这道题你已经做对了一半。最后再分享一个小技巧如果你不确定自己的二进制拆分有没有写对可以在本地输出一下 items 数组里每一组物品的{w, v}然后手动验算几组数据。比如原物品是 w 2, v 3, c 13你应该看到拆出来是 {2,3}、{4,6}、{8,12}、{12,18} 这四组最后一组余数 6 对应的就是 w * 6 和 v * 6。确认拆分没问题之后剩下的 01 背包部分基本不会出错。刷题这条路稳扎稳打比什么都重要。