多重背包三个层次：从朴素循环到二进制与单调队列优化

小P的暑假工这道题，把多重背包的三个层次一次讲透

前阵子刷NSUOJ的时候碰到3188这道"小P的暑假工"，题目本身不复杂，但把它做明白之后，我发现它简直是多重背包问题的教科书级样本——从朴素三重循环到二进制优化再到单调队列优化，三个层次的递进在这道题里体现得淋漓尽致。如果你正在学背包问题，或者准备算法竞赛，拿这道题当练手再合适不过。

先说结论：小P的暑假工本质上是一个"每种物品有数量限制"的背包问题，也就是多重背包。核心就一句话——暑假总天数是背包容量，每份工作耗时是物品重量，每份工作报酬是物品价值，每种工作可做的次数是物品数量上限。把题面翻译到这个模型，后面就全是套路了。

题目大概长这样：小P暑假有 (N) 天空闲时间，他面前有 (M) 种兼职工作。第 (i) 种工作每做一次需要连续投入 (cost_i) 天，做完能拿 (val_i) 元报酬，而且这种工作在暑假期间最多只能做 (cnt_i) 次。小P可以选择做或者不做某种工作，每种做几次也随他，问的是暑假结束前他最多能赚到多少钱。

如果这是你第一次接触多重背包，别被"背包"两个字吓到。它不是什么玄学，就是一个"资源有限、选择有约束、目标最大化"的组合优化问题。下面我按从暴力到最优的完整思路链条来讲。

1. 从暑假工场景到背包模型：先搞懂题目在说什么

1.1 题面还原与约束分析

先把题目抽象成数学语言。设暑假总天数为 (N)，工作种类数为 (M)。对于第 (i) 种工作，有三个参数：

• (cost_i)：完成一次这种工作占用的天数（相当于物品重量）
• (val_i)：完成一次这种工作赚的钱（相当于物品价值）
• (cnt_i)：这种工作整个暑假最多能做几次（相当于物品件数上限）

小P的决策变量是每种工作做多少次，记第 (i) 种工作做 (x_i) 次，那么约束条件是：

[ \sum_{i=1}^{M} cost_i \times x_i \le N, \quad 0 \le x_i \le cnt_i, \quad x_i \in \mathbb{Z} ]

目标函数是最大化总收入：

[ \max \sum_{i=1}^{M} val_i \times x_i ]

看到这个结构，老玩家会条件反射地想起背包三兄弟：01背包是每种最多选1件，完全背包是每种无限选，多重背包则是每种最多选 (cnt_i) 件——正好落在两者中间。

1.2 为什么不能直接贪心

你可能第一反应是"这不就按性价比排序，优先做单位时间赚钱多的工作吗？"——绝大多数第一次做这道题的人都会这么想，但这恰恰是最容易掉进去的坑。

举个反例：小P有10天假期。工作A每次耗时6天，报酬10元，最多做1次；工作B每次耗时4天，报酬6元，最多做2次。按单位时间报酬算，A是1.67元/天，B是1.5元/天，贪心先选A，剩下4天做一次B，总收入16元。但实际上选两次B能赚12元？不对，两次B也才12元，那还是A+B组合的16元更高。这例子不行，换一个。

工作A每次耗时6天，报酬10元，最多做1次；工作B每次耗时4天，报酬7元，最多做2次。单位时间报酬A是1.67，B是1.75，贪心先选B两次共8天赚14元，剩下2天浪费，总收入14元。但选A一次加B一次刚好10天，赚17元。看到没，贪心选性价比最高的B，结果总收益反而低于"混合搭配"。

这就是背包问题不能用贪心的根本原因：背包容量是离散的，选一个物品会占据容量，而这部分容量可能不足以再装下另一个"性价比最高"的物品，导致容量被浪费。生活经验也这样——一小时内你永远没法同时做两件各50分钟的事，但你可以做一件50分钟加一件10分钟的事。

1.3 与01背包、完全背包的深层关联

多重背包有个很重要的性质：它其实是01背包的"压缩态"。如果把每种工作按次数拆开，比如工作A最多做3次，就变成3个完全相同的工作A副本，每个只能选一次——这不就退化成01背包了吗？这是后面二进制优化的出发点。

同时，如果把 (cnt_i) 设为无穷大，多重背包就成完全背包；如果把所有 (cnt_i) 都设为1，它就是01背包。理解这个关系比背模板重要，因为很多题目不会直接告诉你"这是多重背包"，而是给你一个场景，你需要自己识别出物品的"数量限制"这一维度。小P的暑假工就是这样一个优秀的识别训练题。

2. 朴素写法：三重循环的递推逻辑

2.1 状态定义与转移方程

最直观的三重循环是理解多重背包的起点。定义 (dp[j]) 表示"总耗时恰好不超过 (j) 天时能获得的最大报酬"（需要理解成容量为 (j) 时的最优值，实现时通常用不超过）。

当考虑前 (i) 种工作、背包容量为 (j) 时，我们可以枚举第 (i) 种工作做 (k) 次，(k) 的范围是 (0) 到 (\min(cnt_i, \lfloor j / cost_i \rfloor))。状态转移方程为：

[ dp[i][j] = \max_{0 \le k \le \min(cnt_i, \lfloor j / cost_i \rfloor)} \left( dp[i-1][j - k \times cost_i] + k \times val_i \right) ]

解释一下这个方程在说什么：在第 (i) 种工作上花掉 (k \times cost_i) 天，换来 (k \times val_i) 元，剩余 (j - k \times cost_i) 天交给前 (i-1) 种工作去安排。取所有 (k) 里的最大值就是当前最优。

2.2 三重循环的代码实现

用滚动数组可以把第一维省掉，但注意内层循环的方向。这里不能像01背包那样直接从大到小，因为在同一个 (i) 下，我们需要反复使用上一层（前 (i-1) 种）的状态，而不是被当前层的状态覆盖掉。所以朴素写法有很多种防冲突的手段，我习惯用两个数组滚动的方式：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int cost[105], val[105], cnt[105]; int dp[2][MAXN]; int main() { int N, M; cin >> N >> M; for (int i = 1; i <= M; i++) { cin >> cost[i] >> val[i] >> cnt[i]; } int cur = 1, pre = 0; for (int i = 1; i <= M; i++) { fill(dp[cur], dp[cur] + N + 1, 0); for (int j = 0; j <= N; j++) { int limit = min(cnt[i], j / cost[i]); for (int k = 0; k <= limit; k++) { dp[cur][j] = max(dp[cur][j], dp[pre][j - k * cost[i]] + k * val[i]); } } swap(cur, pre); } cout << dp[pre][N] << endl; return 0; }

这段代码的时间复杂度是 (O(M \times N \times \bar{cnt}))，其中 (\bar{cnt}) 是平均最大次数。如果 (N) 是1万、(M) 是100、每种工作最多100次，那么计算量大约是1亿次，C++勉强能压在1秒边缘；但如果 (N) 到10万、(cnt) 到1万，这代码基本就告别AC了。

2.3 小规模数据下的正确性验证

先跑一个小样例验一下逻辑。设 (N = 10)，(M = 2)：

• 工作1：(cost=3, val=5, cnt=3)
• 工作2：(cost=4, val=8, cnt=2)

手工推一遍：如果完全做工作1，三次占9天赚15元；如果做两次工作2，8天赚16元；如果工作1两次加工2一次，3+3+4=10天，赚5+5+8=18元——这就是最优解。跑朴素代码应该输出18。这种小样例建议每次写完都先验证，别直接对着大数据调。

这个三重循环虽然慢，但它定义清楚了"枚举第 i 种工作做几次"这个核心思想，后面两种优化本质上都是在"如何更快地枚举k"上做文章。

3. 二进制优化：把多重背包拆成01背包的优雅骗局

3.1 为什么拆成2的幂就能覆盖所有次数

朴素写法的瓶颈在于对每个 (k) 都枚举一遍。一个自然的想法是：能不能把"最多做 (cnt_i) 次"拆成若干个绑定组，让这些组的任意组合能覆盖 (0 \sim cnt_i) 的所有整数，然后对每个组只做"选或不选"的01背包决策？

答案就是二进制拆分。假设 (cnt_i = 13)，拆成 (1, 2, 4, 6) 这四个数——注意不是 (1, 2, 4, 8)，因为 (1+2+4=7)，剩下 (13-7=6)。用这四个数能组合出0到13的所有整数吗？

• (0 = 0)
• (1 = 1)
• (2 = 2)
• (3 = 1+2)
• (4 = 4)
• (5 = 1+4)
• (6 = 2+4)（也可以直接拿6）
• (7 = 1+2+4)
• (8 = 2+6)
• (9 = 1+2+6)（或 (1+4+4)？没有两个4，所以是 (1+2+6)）
• (10 = 4+6)
• (11 = 1+4+6)
• (12 = 2+4+6)
• (13 = 1+2+4+6)

可以。原理在于：二进制拆出的 (1, 2, 4, \dots, 2^p) 这一段可以覆盖 (0 \sim 2^{p+1}-1) 的连续整数，最后剩余的非二次幂余数 (r) 用来把覆盖区间延续到 (cnt_i)。所以每种工作拆出来的组数大约是 (O(\log cnt_i)) 个。

3.2 拆分代码与01背包合并

拆分后的每个组被视为一件新物品，重量是 (k \times cost_i)，价值是 (k \times val_i)。整道题就从" (M) 种多重背包物品"变成了" (\sum \log cnt_i) 个01背包物品"。

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int MAXM = 2005; // 拆分后物品总数上限 int w[MAXM], v[MAXM]; // 拆分后的重量和价值 int dp[MAXN]; int main() { int N, M; cin >> N >> M; int tot = 0; for (int i = 1; i <= M; i++) { int c, val, cnt; cin >> c >> val >> cnt; int k = 1; while (cnt >= k) { w[++tot] = k * c; v[tot] = k * val; cnt -= k; k <<= 1; } if (cnt > 0) { w[++tot] = cnt * c; v[tot] = cnt * val; } } for (int i = 1; i <= tot; i++) { for (int j = N; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } cout << dp[N] << endl; return 0; }

这里的关键是内层循环必须从 (N) 往 (w[i])倒着遍历。为什么？因为现在的结构是01背包，每个拆分出的组只能取一次。正序遍历会让同一个组的贡献被重复叠加，等于允许"无限次选择"，那就变成完全背包了。这一步出错的人特别多，后面我会专门讲。

复杂度降为 (O(N \times \sum_{i=1}^{M} \log cnt_i))。若 (N=10^5)，(M=100)，每个 (cnt_i) 最大 (10^5)，总拆分物品约 (100 \times 17 = 1700) 个，计算量约1.7亿次，多数OJ能在1秒左右跑完。

3.3 一个极容易写错的边界

二进制拆分最大的坑在于：有些人第一反应是拆成 (1, 2, 4, 8, \dots) 直到超过 (cnt_i)，然后不管剩下的余数。比如 (cnt_i = 10)，拆成 (1,2,4,8)，这四个数（(1+2+4+8=15)）确实能组合出0到15的所有数，看起来没问题——但它的总重量变成了15份工作的重量，超出了题目的13或10限制，相当于凭空多出来5份工作，这会破坏约束，答案是错的。

正确的逻辑是：每次取 (k = \text{当前最小的未覆盖的2次幂})，不断从 (cnt_i) 中扣除，直到剩余数量小于下一个2次幂，这时把剩余的数量单独作为一组。换句人话：先拆完整的二次幂，拆不下的时候把剩余的全部当成一组。代码里的while (cnt >= k)配合最后的if (cnt > 0)就是干这个的。

我见过不少人在这一步写错，表现就是答案偏大。排查方法也简单：构造一个 (cnt_i) 不是 (2^p - 1) 的样例，比如3、5、10、13，暴力枚举对比拆分后01背包的结果，很快就能发现问题。

4. 单调队列优化：把内层枚举从O(cnt)压到O(1)

4.1 剩余类分组：重新审视转移式

二进制优化已经能过大多数多重背包题了，但如果 (N) 到了 (10^5)，(M) 到了 (10^3)，而且物品次数都很大，二进制优化的总物品数量可能到两三万件，再乘上 (N)，两三亿次运算就比较悬了。另一种思路是单调队列优化，直接把时间复杂度做到严格的 (O(N \times M))。

回看朴素转移方程，在固定第 (i) 种物品时：

[ dp[j] = \max_{0 \le k \le \min(cnt, \lfloor j / cost \rfloor)} \left( dp_{prev}[j - k \times cost] + k \times val \right) ]

关键观察：所有 (j) 对 (cost) 取模后，不同余数的状态之间相互独立。比如 (cost = 3)，那么 (j = 0, 3, 6, 9) 这一条链上的转移只依赖同余类的链，不会跨到 (j = 1, 4, 7) 那一条链上去。于是我们可以按余数分组处理。

把 (j) 写成 (r + p \times cost)，其中 (0 \le r < cost)。记 (t = p - k)，则转移变成：

[ dp[r + p \times cost] = \max_{t \in [\max(0, p - cnt), \ p]} \left( dp_{prev}[r + t \times cost] - t \times val \right) + p \times val ]

注意括号里面的值只跟 (t) 有关，与当前枚举到的 (p) 无关。这就像一个滑动窗口：随着 (p) 往前移动，窗口左端不断右移（左边界是 (p - cnt)），右端不断扩展，我们要求窗口内括号值的最大值——这就是单调队列的标准场景。

4.2 单调队列的代码实现

一个容易混淆的点是：队列里存的是下标 (t)（或者 (j)），比较值时用括号里那个修正后的"候选值"，而每个候选值的修正公式是dp_prev[item] - (item / cost) * val。写成代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int cost[1005], val[1005], cnt[1005]; int dp[MAXN], g[MAXN]; int q[MAXN]; // 单调队列，存的是下标 int main() { int N, M; cin >> N >> M; for (int i = 1; i <= M; i++) { cin >> cost[i] >> val[i] >> cnt[i]; } for (int i = 1; i <= M; i++) { int c = cost[i], v = val[i], s = cnt[i]; memcpy(g, dp, sizeof(dp)); // g 保存上一层（前 i-1 种物品）的结果 for (int r = 0; r < c; r++) { int head = 0, tail = 0; // 当前余数为 r，遍历同余类链: r, r+c, r+2c, ... for (int p = 0; r + p * c <= N; p++) { int j = r + p * c; // 当前容量 // 新候选下标 p 入队，维护队尾单调递减 int cand = g[j] - p * v; while (head < tail && g[q[tail - 1]] - (q[tail - 1] / c) * v <= cand) { tail--; } q[tail++] = j; // 队首超出窗口范围 [j - s*c, j]，弹出 while (head < tail && q[head] < j - s * c) { head++; } // 队首就是当前 p 的最优候选 dp[j] = g[q[head]] + (j - q[head]) / c * v; } } } cout << dp[N] << endl; return 0; }

逐个解释关键步骤：

1. g数组备份上一层结果。因为第 (i) 种物品的转移需要引用前 (i-1) 种物品的完整状态，而dp数组会在当前层被覆盖，所以必须提前复制一份。
2. 外层for (int r = 0; r < c; r++)是枚举余数分组。每组内只有 (\lfloor N/c \rfloor) 个元素，所有组合起来正好是 (N+1) 个状态，所以复杂度是 (O(N))。
3. cand就是上面的候选值 (g[t] - t \times v)。如果用下标 (j) 表示，就是 (g[j] - (j / c) \times v)，因为 (t = j / c)。
4. 窗口范围：对于当前容量 (j = r + p \times c)，可选的 (k) 从0到 (s)，对应的 (t = p - k) 从 (p - s) 到 (p)。所以窗口内的有效下标必须不小于 (j - s \times c)。队首一旦小于这个值就弹出。
5. 更新dp[j]：队首下标对应的候选值加上 (p \times v)（也就是(j / c) * v）就是答案。注意括号里已经把 ((-t \times v)) 减掉了，所以乘回来时用 (p \times v) 而不是 (t \times v)。

一个测试样例：(N = 10)，容量10天，单个物品 (cost=3, val=5, cnt=3)。手动模拟余数 (r = 1) 的链上 (j = 1, 4, 7, 10) 的转移，会得到：

• (j=1)：只能不选，dp[1]=0
• (j=4)：可以选1次（3天+浪费1天），dp[4]=5
• (j=7)：可以选2次（6天），dp[7]=10
• (j=10)：可以选3次（9天），dp[10]=15

单调队列会依次维护窗口，每个位置取窗口最大值，正好得到这些数。这里建议你亲自动手画一遍head、tail的变化，比看十遍代码都有用。

4.3 从二进制优化到单调队列：什么时候换方案

我自己的经验是：能二进制优化的题先别上单调队列，单调队列虽然复杂度更优，但边界和下标转换很考验细节，调试成本高。只有当 (N) 与 (M) 的数据范围把二进制优化卡在超时边缘，或者题目对时间限制卡得很紧时，才动用单调队列这个"大杀器"。

具体来说，如果 (N \le 10^4)，二进制优化的拆分物品总数在大几百到一两千，完全够用。如果 (N) 到 (10^5) 且 (M \ge 500)，或者 (N) 到 (10^6)，那就必须考虑单调队列了。当然，还有一种更极端的场景是物品数量达到 (10^5) 级别，连单调队列的 (O(N \times M)) 都悬，那就要考虑生成函数、FPTAS等更高级的手段了——但竞赛里很少考到。

5. 这道题实际评测中的坑与我的调试记录

5.1 样例过了却WA？大概率是数据范围看漏了

我第一次交这题的时候，用的是二进制优化，样例一次过，心里美滋滋，结果连续两三发WA。反复检查代码逻辑都没问题，最后发现是题目的一个隐藏前提没注意到：有些工作虽然耗时不同，但可能已经超过了暑假总天数。这种情况下，即使cnt_i很大，实际可行的次数也是0，代码应该自动跳过这种物品。

大多数模板拆分会自然规避这个问题——因为拆出来的组重量大于容量 (N) 时，01背包内层循环根本不会进去。但如果你在拆分前额外做了一次"把cnt_i压到N / cost_i"的优化（这是常见优化手段），要小心：当cost_i > N时，N / cost_i = 0，此时cnt_i会变成0，如果不特判可能导致拆分循环while (0 >= k)直接跳过，这没错；但有些人写的时候没把cnt_i提前压缩，而是直接在转移时用min(cnt_i, j / cost_i)，这在j / cost_i = 0时取0，也是正确的。

WA的原因如果不在这一步，那多半是数组越界或内存没清零。我后来发现自己的q队列数组开小了，q应该至少能容纳一条余数链上所有位置的数量，也就是N / c + 1。这题 (N) 最大到 (10^5)，我一开始图省事开了5000，一提交就出幺蛾子。这个教训提醒我：单调队列的队列数组，长度直接开成 (N+5) 是最保险的，因为最坏情况下一条链上确实可能有 (N/c \approx N) 个元素。

5.2 三个版本在同数据下的耗时对比

我自己用随机数据在本地测了一下三种写法，数据规模 (N=100000)，(M=100)，每种工作次数 (cnt_i) 随机取 (1\sim 50000)。在不开O2优化的情况下：

数据量再调大——(N=1000000)，(M=500)——二进制优化就到了2秒多，很接近超时边缘；单调队列仍然是稳定的500ms级别。这就是为什么"数据范围决定算法选择"不是一句空话。

5.3 关于这题我个人最后想说的

多重背包的三种写法，本质是在"枚举次数"这个动作上做文章：朴素写法老老实实枚举所有次数，二进制优化把次数打包成几组，单调队列则用滑动窗口一次性找到最优次数区间。如果只记住模板而不理解这个递进关系，遇到题目稍加变体（比如要求输出具体方案、或者改成"不超过天数的最小浪费"之类）就又不会了。建议你这样练：选几道多重背包题，先写朴素，再改二进制，最后上单调队列，用同一道题体会三层优化带来的性能跃升。

回到小P的暑假工这题本身，它出得好的地方在于背景亲切、模型直观，新手不会在题意理解上卡壳，可以专心练算法核心；同时又留了足够的数据空间让老手展示优化技巧。如果你能把从三重循环到单调队列这条链完整走一遍，那你就真正掌握多重背包了，之后碰到任何奇怪包装的有限数量背包题，都能一眼看穿底牌。