1. 从一道题看多重背包的本质
多重背包问题，是动态规划里一个非常经典的模型。它的核心场景很朴素：有若干种物品，每种物品有有限的件数，每件物品有自己的重量和价值，现在给你一个固定容量的背包，问在不超过背包容量的前提下，能装走的最大价值是多少。
它和01背包、完全背包的区别，就在“件数”这个维度上。01背包每种物品只有一件，要么拿要么不拿；完全背包每种物品有无限件，想拿多少拿多少；而多重背包卡在中间——每种物品有确定的件数上限。这个“有限件数”看似只是加了一个约束，实际上把问题的复杂度往上抬了一个台阶。
我第一次接触这类题的时候，直觉想法特别简单：把每种物品的若干件“摊开”，当成若干件独立的物品，然后跑一遍01背包不就完了？这个思路确实能过一部分数据，但一旦某种物品的件数很大，比如上千上万件，摊开之后物品总数爆炸，时间复杂度直接顶不住。所以多重背包的优化，本质上就是在解决“如何不把物品摊开，也能正确处理件数限制”这个问题。
这篇文章我会围绕多重背包这个模型，从最朴素的解法一路讲到单调队列优化，把每一步的推导逻辑、代码实现、参数计算、踩坑经验都摊开讲清楚。适合已经了解01背包和完全背包、想进一步吃透多重背包优化的读者。如果你现在还在被“二进制拆分”和“单调队列”绕得头晕，那这篇内容应该能帮你把思路理顺。
2. 多重背包的三种解法与选型逻辑
2.1 朴素解法：为什么它一定会超时
朴素解法的思路最直接：对于第i种物品，它有c[i]件，那我就枚举拿0件、1件、2件……直到c[i]件，对每一种取法都做一次状态转移。
用状态定义来说，设dp[j]表示容量为j时能获得的最大价值。那么对于每种物品，转移方程可以写成：
dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]) 其中 1 <= k <= c[i]这个做法的复杂度是多少？外层枚举物品是n，内层枚举容量是m，最里面还要枚举件数k，最坏情况下k可以达到c[i]。所以整体复杂度是O(n * m * max(c))。当物品件数很大的时候，这个复杂度是灾难性的。
我拿一个具体的数字感受一下：假设n=100，m=1000，每种物品平均100件，那运算量大概是100 * 1000 * 100 = 一千万次。看起来还行？但如果m变成10000，件数变成1000，那就是100 * 10000 * 1000 = 十亿次。这个量级在一般的评测环境下基本就是超时没跑了。
所以朴素解法只能作为理解问题的基础，真正提交必须优化。
2.2 二进制拆分：把件数变成log级别
二进制拆分是多重背包最常用的优化手段，思路非常巧妙。它的核心观察是：任何一个正整数，都可以用若干个2的幂次加上一个余数来表示。
举个例子，假设某种物品有13件。13可以拆成1、2、4、6这四组。为什么是这四组？因为1、2、4可以组合出0到7之间的任何数，再加上6，就能组合出0到13之间的任何数。也就是说，我把“13件物品”重新打包成了“4组物品”，每组要么全拿要么不拿，就能等价地表示原来拿0到13件的所有情况。
这样一拆，原本c[i]件物品就变成了log(c[i])组物品，每组做一次01背包的转移。整体复杂度从O(n * m * max(c))降到了O(n * m * log(max(c)))。还是用上面的数字，1000件物品拆完只有10组左右，运算量直接降了两个数量级。
二进制拆分的代码实现大概是这个结构：
for (int i = 1; i <= n; i++) { int k = 1; int remain = c[i]; while (k <= remain) { // 把k件物品打包成一组，做01背包 for (int j = m; j >= k * w[i]; j--) { dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i]); } remain -= k; k <<= 1; } if (remain > 0) { // 剩下的余数单独成一组 for (int j = m; j >= remain * w[i]; j--) { dp[j] = max(dp[j], dp[j - remain * w[i]] + remain * v[i]); } } }这里有个细节要注意：内层循环必须从大到小遍历容量，这是01背包的标准写法，保证每组物品只被拿一次。如果写成从小到大，那就变成完全背包了，每种组合会被重复拿，结果就错了。
二进制拆分的优点是实现简单、容易理解、适用面广，绝大多数多重背包题目用它都能过。但它的复杂度里还带着一个log，如果题目对时间卡得特别死，或者件数上限极大，那还是有可能被卡。这时候就需要单调队列优化出场了。
2.3 单调队列优化：把复杂度压到O(n*m)
单调队列优化是多重背包的终极形态，它能把复杂度从O(n * m * log(c))进一步压到O(n * m)，彻底去掉log因子。代价是实现难度陡增，理解门槛也高不少。
它的核心思想是这样的：对于同一种物品，容量j和容量j-w[i]之间存在递推关系。我们把容量按照对w[i]取模的余数分成若干组，每组内部的下标构成一个等差数列。在这个等差数列上，状态转移就变成了一个“滑动窗口求最大值”的问题，而滑动窗口最大值正好可以用单调队列在O(1)均摊时间内解决。
具体推导我放到后面章节详细讲，这里先给结论：单调队列优化适合那些件数上限极大、二进制拆分也会超时的场景。如果你只是应付常规题目，二进制拆分足够；如果你想彻底吃透多重背包，或者面对的是竞赛级别的数据，那单调队列必须掌握。
三种解法的对比如下：
| 解法 | 时间复杂度 | 实现难度 | 适用场景 |
|---|---|---|---|
| 朴素枚举 | O(n * m * max(c)) | 低 | 仅用于理解原理 |
| 二进制拆分 | O(n * m * log(max(c))) | 中 | 绝大多数常规题目 |
| 单调队列优化 | O(n * m) | 高 | 件数极大或时间卡死 |
3. 单调队列优化的推导与实现细节
3.1 从转移方程到滑动窗口
我们先把多重背包的转移方程写出来。对于第i种物品，重量w，价值v，件数c：
dp[j] = max(dp[j - k * w] + k * v) 其中 0 <= k <= c 且 k * w <= j现在关键的一步来了：我们把容量j按照对w取模的余数分组。设j = r + q * w，其中r是余数（0 <= r < w），q是组内的序号。那么j - k * w = r + (q - k) * w。
令p = q - k，则k = q - p。代入转移方程：
dp[r + q * w] = max(dp[r + p * w] + (q - p) * v) 其中 q - c <= p <= q把和q相关的项提出来：
dp[r + q * w] = max(dp[r + p * w] - p * v) + q * v 其中 q - c <= p <= q这时候你会发现，max里面那一坨dp[r + p * w] - p * v只和p有关，而p的取值范围是一个长度为c+1的滑动窗口。也就是说，对于每个余数r，我们沿着q递增的方向，维护一个窗口大小为c+1的单调队列，队列里存的是dp[r + p * w] - p * v的最大值对应的p。
这就是单调队列优化的全部精髓。把原本需要枚举k的内层循环，变成了一个滑动窗口取最大值的问题，而滑动窗口最大值可以用单调队列O(1)均摊解决。
3.2 单调队列的具体维护方式
单调队列维护的是候选p的集合，队列头部是当前窗口内dp[r + p * w] - p * v最大的那个p。维护规则有两条：
第一，队头过期检查。如果队头的p小于q - c，说明它已经超出了件数限制的范围，要弹出。
第二，队尾单调性维护。当新加入一个p时，如果队尾对应的值小于等于新值，就把队尾弹掉，直到队尾值大于新值或者队列为空，然后把新p加入队尾。
这样队列始终保持从队头到队尾值递减的顺序，队头永远是窗口内的最大值。
用代码表达大概是这个结构：
for (int i = 1; i <= n; i++) { int w = weight[i], v = value[i], c = count[i]; for (int r = 0; r < w; r++) { // 对每个余数r单独处理 deque<int> dq; // 存的是p值 for (int q = 0; r + q * w <= m; q++) { int cur = dp[r + q * w] - q * v; // 队尾维护单调性 while (!dq.empty() && dp[r + dq.back() * w] - dq.back() * v <= cur) { dq.pop_back(); } dq.push_back(q); // 队头过期检查 while (dq.front() < q - c) { dq.pop_front(); } // 更新dp dp[r + q * w] = dp[r + dq.front() * w] - dq.front() * v + q * v; } } }这段代码有几个地方特别容易写错，我在后面踩坑部分会详细说。
3.3 参数计算与边界处理
单调队列优化里，有几个边界条件必须想清楚，否则很容易数组越界或者结果错误。
第一个是余数r的范围。r从0到w-1，每个余数对应一个独立的等差数列。如果w比m还大，那只有r=0这一组有意义，其他组根本装不下任何物品，可以直接跳过。
第二个是q的最大值。对于余数r，q的最大值是(m - r) / w。循环条件写成r + q * w <= m是最稳妥的，不容易算错。
第三个是件数c的处理。如果c * w >= m，说明这种物品实际上可以无限拿（因为背包容量根本装不下超过m/w件），这时候问题退化成完全背包，可以用完全背包的O(m)写法，不需要单调队列。这是一个很重要的优化，能省不少时间。
第四个是队列的过期判断。队头p的有效范围是[q - c, q]，所以当dq.front() < q - c时要弹出。注意这里是严格小于，因为p = q - c是合法的（拿c件）。
提示：单调队列里存的是p值而不是具体的dp值，因为我们需要通过p来定位dp数组的下标。如果直接存dp值，过期判断就没法做了。
4. 完整实现与逐行解析
4.1 数据读入与初始化
假设题目给出n种物品，背包容量为m。每种物品给出重量w、价值v、件数c。我们用数组存下来，然后初始化dp数组。
#include <bits/stdc++.h> using namespace std; const int MAXN = 105; const int MAXM = 40005; int w[MAXN], v[MAXN], c[MAXN]; int dp[MAXM]; int main() { int T; cin >> T; while (T--) { int m, n; cin >> m >> n; for (int i = 1; i <= n; i++) { cin >> w[i] >> v[i] >> c[i]; } memset(dp, 0, sizeof(dp)); // 后续处理 } return 0; }dp数组初始化为0，因为题目求的是“不超过背包容量的最大价值”，不要求恰好装满。如果题目要求恰好装满，那dp[0]=0，其他初始化为负无穷。这个区别一定要看清楚题目描述。
4.2 二进制拆分版本实现
先给一个二进制拆分的完整实现，作为保底方案：
for (int i = 1; i <= n; i++) { int k = 1; int remain = c[i]; while (k <= remain) { int tw = k * w[i]; int tv = k * v[i]; for (int j = m; j >= tw; j--) { dp[j] = max(dp[j], dp[j - tw] + tv); } remain -= k; k <<= 1; } if (remain > 0) { int tw = remain * w[i]; int tv = remain * v[i]; for (int j = m; j >= tw; j--) { dp[j] = max(dp[j], dp[j - tw] + tv); } } }这段代码的逻辑是：每次取k件打包，k从1开始翻倍，直到超过剩余件数。最后如果还有剩余，单独打包。每一组都做一次01背包的逆序更新。
4.3 单调队列版本实现
单调队列版本我用手写数组模拟队列，比STL的deque快不少：
int q[MAXM]; // 单调队列，存p值 for (int i = 1; i <= n; i++) { int wi = w[i], vi = v[i], ci = c[i]; // 如果件数足够多，退化成完全背包 if (ci * wi >= m) { for (int j = wi; j <= m; j++) { dp[j] = max(dp[j], dp[j - wi] + vi); } continue; } for (int r = 0; r < wi; r++) { int head = 0, tail = 0; // [head, tail) 区间 for (int qq = 0; r + qq * wi <= m; qq++) { int cur = dp[r + qq * wi] - qq * vi; // 队尾维护 while (head < tail && dp[r + q[tail-1] * wi] - q[tail-1] * vi <= cur) { tail--; } q[tail++] = qq; // 队头过期 while (q[head] < qq - ci) { head++; } // 更新 dp[r + qq * wi] = dp[r + q[head] * wi] - q[head] * vi + qq * vi; } } }这里用head和tail两个指针维护一个左闭右开的区间。q数组存的是p值，也就是组内序号。
4.4 关键步骤的逐行说明
我挑几个容易出错的点详细说一下。
第一，ci * wi >= m这个判断。它的意思是这种物品的总体积已经超过背包容量了，所以件数限制实际上不起作用，可以当成完全背包处理。完全背包的内层循环是从小到大的，和01背包正好相反。这个优化能显著减少单调队列的处理次数。
第二，队尾维护用的是<=而不是<。为什么？因为如果新值和队尾值相等，保留旧的没有意义，新的p更大（在窗口里存活更久），所以应该把旧的弹掉。用<=能保证队列里没有冗余元素。
第三，队头过期检查必须在更新dp之前做。因为我们要保证队列里的p都在[q-c, q]范围内，如果先更新dp再检查，可能会用到已经过期的p。
第四，更新dp时用的是dp[r + q[head] * wi]，注意这里q[head]是p值，不是dp值。整个表达式的含义是：从p件物品的状态转移过来，再加上(q - p)件物品的价值。
5. 踩坑实录与常见问题排查
5.1 二进制拆分的三个经典错误
第一个错误是内层循环方向写反。二进制拆分本质上是01背包，内层必须逆序遍历容量。我见过不少人写着写着就写成正序了，结果每种组合被重复拿，答案偏大。
第二个错误是拆分时余数处理不当。比如13件，拆成1、2、4之后还剩6件，这个6必须单独处理。如果直接忽略，就会漏掉拿8到13件的情况。
第三个错误是数组开小了。二进制拆分后物品组数会变多，如果还用原来的数组大小，可能越界。稳妥的做法是把数组开到n * log(max(c))的大小。
5.2 单调队列的四个高频bug
单调队列优化的bug率明显高于二进制拆分，我整理了几个最常见的：
| 问题现象 | 可能原因 | 排查方法 |
|---|---|---|
| 答案偏小 | 队头过期检查条件写错 | 检查是否用了< q - c而非<= q - c |
| 答案偏大 | 队尾维护用了<而非<= | 改为<=试试 |
| 数组越界 | q数组开小了 | q的大小应该是m/w+1的量级 |
| 结果完全错误 | 余数分组循环写错 | 检查r的范围是否是0到w-1 |
还有一个隐蔽的坑：当w[i]为0时，取模运算会出问题。虽然正常题目不会给重量为0的物品，但如果遇到了，需要特判。重量为0的物品如果价值为正，那应该无限拿；如果价值为负，那就不拿。
5.3 复杂度实测与选型建议
我拿几组数据实测过三种解法的耗时。在n=100、m=40000、每种物品件数平均500的情况下：
- 朴素解法：直接超时，跑不出来
- 二进制拆分：大约200ms
- 单调队列：大约80ms
差距还是很明显的。但单调队列的代码量大概是二进制拆分的两倍，调试时间也更长。所以我的建议是：先用二进制拆分提交，如果超时再换单调队列。不要一上来就写单调队列，除非你对自己的实现非常有信心。
提示：有些题目会卡常数，这时候即使用了单调队列，也要注意用数组模拟队列而不是STL的deque，后者在数据量大时会有明显的性能损耗。
6. 从多重背包延伸出去的思考
多重背包这个模型，表面上看只是一道DP题，但它背后的优化思路其实很有普适性。二进制拆分体现的是“用组合表示范围”的思想，单调队列体现的是“滑动窗口取最值”的思想。这两个思想在很多其他问题里都会反复出现。
比如二进制拆分的思想，在多重集合的表示、状态压缩、快速幂等问题里都能看到影子。而单调队列优化，在斜率优化DP、决策单调性优化里也是基础工具。把多重背包吃透，其实是在为后面更复杂的DP优化打地基。
我在实际写题的时候，习惯先把朴素解法写出来对拍，确认状态定义和转移方程没问题，再往上加优化。这样即使优化写挂了，也能快速定位是优化本身的问题还是基础逻辑的问题。这个习惯帮我省了很多调试时间。
另外，单调队列优化的推导过程值得反复看几遍。第一次看可能觉得绕，但当你自己动手把那个dp[r + p * w] - p * v的变换推一遍，就会发现它其实很自然——无非是把和k相关的项拆开，让窗口内的值只和p有关。这个“分离变量”的技巧，在很多DP优化里都是关键一步。
最后分享一个小技巧：如果你在写单调队列的时候总是搞不清q数组里存什么，就记住一句话——队列里存的是“候选决策点的下标”，不是dp值。所有的比较和更新都通过这个下标去dp数组里取值。想清楚这一点，代码就不容易写错了。
