1. 从一道经典题看多重背包的本质困境

多重背包问题在动态规划的学习路径上，是一个绕不开的分水岭。它不像01背包那样每个物品只有选或不选两种状态，也不像完全背包那样每种物品可以无限次取用。多重背包的约束在于：每种物品有确定的个数上限。这个看似微小的变化，直接把朴素解法的时间复杂度推到了一个令人尴尬的量级。

我第一次接触这类问题是在一个在线评测平台上，题目编号早已模糊，但场景很清晰：给定容量为V的背包，有N种物品，每种物品有重量w、价值v和数量m，要求在不超过背包容量的前提下最大化总价值。当时我用的还是最朴素的拆分法——把m个相同物品当成m个独立物品，然后跑01背包。这个思路在m较小的时候完全没问题，可一旦m达到几千甚至上万，时间复杂度就变成了O(V × Σm)，直接超时。

后来我学到了二进制拆分优化，把m个物品拆成1、2、4、8……这样的二进制组合，将每种物品的拆分数量从m降到log₂m，整体复杂度变成O(V × Σlog m)。这个优化已经能应付大多数场景了，但它有一个前提：拆分后的物品必须能组合出0到m之间的任意数量。二进制拆分恰好满足这个条件，因为任何正整数都可以表示为若干个2的幂次之和。

可问题到这里并没有结束。当V和N都达到较大规模时，即使有二进制拆分，O(V × Σlog m)仍然可能不够快。这时候就需要引入更高级的优化手段——单调队列优化。它能把多重背包的时间复杂度压到O(V × N)，也就是和01背包、完全背包同阶。这个优化的核心思想，是利用滑动窗口求最大值的单调性，在状态转移的过程中避免重复计算。

注意：单调队列优化多重背包并不是万能的，它要求物品的重量w和背包容量V之间存在特定的整除关系才能发挥最大效果。具体来说，当w较小时，单调队列的优势最明显；当w接近V时，优化效果会打折扣。

2. 朴素解法为什么慢：从状态转移方程说起

2.1 多重背包的状态定义与转移

多重背包的状态定义和01背包完全一致：dp[j]表示容量为j的背包能获得的最大价值。区别在于转移方程。对于第i种物品，我们可以选择0个、1个、……、k个，其中k ≤ m_i且k × w_i ≤ j。所以转移方程是：

dp[j] = max(dp[j - k × w_i] + k × v_i)，其中0 ≤ k ≤ min(m_i, j / w_i)

这个方程的含义很直白：枚举当前物品取多少个，然后从对应的前一个状态转移过来。如果直接按照这个方程写代码，对于每个物品i，我们需要枚举容量j（从0到V），再枚举数量k（从0到m_i），总复杂度是O(V × Σm_i)。当m_i很大时，这个复杂度是不可接受的。

2.2 二进制拆分的优化逻辑与局限

二进制拆分的思路是把m_i个物品拆成若干个“捆绑包”，每个捆绑包的大小是2的幂次。比如m_i = 13，可以拆成1、2、4、6这四组（最后一组是剩余部分）。这样任何0到13之间的数量都可以由这四组组合出来。拆分之后，每种捆绑包要么全取要么不取，就变成了01背包问题。

这个优化的正确性依赖于一个数学事实：任何正整数都可以表示为若干个2的幂次之和，且每个幂次最多使用一次。二进制拆分把每种物品的枚举数量从m_i降到了log₂m_i，整体复杂度变成O(V × Σlog m_i)。对于大多数题目来说，这个复杂度已经足够了。

但二进制拆分有一个隐藏的成本：它改变了物品的数量。原本N种物品，拆分后可能变成N × log m种物品。当N很大时，这个膨胀倍数不容忽视。而且二进制拆分并没有改变问题的本质结构，它只是减少了枚举次数，并没有利用状态转移中的冗余计算。

2.3 从“枚举数量”到“按余数分组”的思维跃迁

单调队列优化的切入点，是观察到状态转移方程中有一个固定的步长w_i。对于固定的物品i，dp[j]只依赖于dp[j - w_i]、dp[j - 2w_i]、……这些状态。也就是说，所有容量模w_i同余的状态构成了一条独立的转移链。

举个例子，假设w_i = 3，那么容量0、3、6、9……构成一条链，容量1、4、7、10……构成另一条链，容量2、5、8、11……构成第三条链。不同链之间没有任何转移关系，可以独立处理。这个观察是单调队列优化的基石。

在每条链内部，转移方程可以重新写成：

dp[j] = max(dp[j - k × w_i] + k × v_i)，其中k从0到min(m_i, j / w_i)

如果我们令j = r + t × w_i（r是余数，t是链上的位置），那么转移方程变成：

dp[r + t × w_i] = max(dp[r + (t - k) × w_i] + k × v_i)，其中k从0到min(m_i, t)

再令s = t - k，则k = t - s，方程变为：

dp[r + t × w_i] = max(dp[r + s × w_i] - s × v_i) + t × v_i，其中s从max(0, t - m_i)到t

这个形式非常关键：它把“取k个物品”的决策转化成了在一条链上求一个滑动窗口的最大值。窗口的大小是m_i + 1，窗口内的值是dp[r + s × w_i] - s × v_i。随着t的增加，窗口向右滑动，我们需要实时维护窗口内的最大值。这正是单调队列的用武之地。

3. 单调队列优化的完整推导与实现细节

3.1 滑动窗口最大值的单调队列维护

单调队列是一种能在O(1)均摊时间内维护滑动窗口最大值的数据结构。它的核心操作有两个：入队和出队。入队时，从队尾开始，把所有小于当前值的元素全部弹出，保证队列从队头到队尾是单调递减的。出队时，如果队头元素已经超出了窗口范围，就把它弹出。

在多重背包的场景中，窗口的范围是[t - m_i, t]，窗口内的值是dp[r + s × w_i] - s × v_i。随着t从0增加到(V - r) / w_i，窗口不断右移。每次我们需要取出窗口内的最大值，然后加上t × v_i，就得到了dp[r + t × w_i]的值。

这里有一个实现上的细节需要注意：单调队列中存储的是链上的位置s，而不是值本身。因为我们需要判断队头元素是否还在窗口内，所以必须知道每个元素对应的s。比较值时，通过dp[r + s × w_i] - s × v_i来比较。

3.2 按余数分组的循环结构设计

实现单调队列优化的多重背包，代码结构需要仔细设计。外层循环遍历每种物品i，内层循环遍历余数r（从0到w_i - 1），最内层循环遍历链上的位置t。对于每个余数r，我们初始化一个空的单调队列，然后依次处理t = 0, 1, 2, ……直到r + t × w_i > V。

在每次处理t时，首先检查队头元素是否还在窗口内。如果队头元素对应的s小于t - m_i，就弹出队头。然后，将当前元素（位置t，值为dp[r + t × w_i] - t × v_i）入队，入队前弹出所有值小于等于它的队尾元素。最后，用队头元素的值加上t × v_i来更新dp[r + t × w_i]。

这个过程中，dp数组的更新是原地进行的。但需要注意的是，我们在计算dp[r + t × w_i]时，需要用到dp[r + s × w_i]（s < t）的值。由于我们是按t递增的顺序处理的，这些值已经被更新过了。这会不会导致问题？答案是：不会。因为在同一条链上，dp[r + s × w_i]在s < t时已经完成了更新，而我们需要的正是更新后的值。不同链之间互不影响，所以原地更新是安全的。

3.3 边界条件与初始化陷阱

单调队列优化多重背包的边界条件比朴素解法更容易出错。第一个陷阱是队列的初始化。对于每个余数r，队列一开始是空的。当t = 0时，窗口内只有s = 0这一个元素，所以队列中应该只有位置0。但如果我们直接处理t = 0，会发现队列为空，无法取出最大值。正确的做法是在处理t之前，先把位置t入队，然后再取队头。

第二个陷阱是窗口大小的判断。窗口的下界是max(0, t - m_i)，而不是t - m_i。当t < m_i时，窗口下界是0，而不是负数。这个细节如果处理不当，会导致队列中弹出了不该弹出的元素。

第三个陷阱是dp数组的初始值。在多重背包中，dp[0] = 0，其他dp[j] = -∞（或者0，取决于题目是否要求恰好装满）。如果题目不要求恰好装满，所有dp[j]初始化为0即可。如果要求恰好装满，则dp[0] = 0，其余为-∞。这个初始化方式与01背包完全一致，但在单调队列优化中，由于涉及减法操作，-∞可能会导致数值溢出，需要特别小心。

提示：在实际编码时，建议用一个大负数（如-0x3f3f3f3f）代替真正的负无穷，这样在减法运算时不会溢出，同时又能保证不会误选无效状态。

4. 代码实现与逐行解析

4.1 核心代码框架

下面给出单调队列优化多重背包的完整代码实现。代码以C++为例，但思路适用于任何语言。

#include <bits/stdc++.h> using namespace std; const int MAXV = 100005; const int MAXN = 1005; const int NEG_INF = -0x3f3f3f3f; int dp[MAXV]; int q[MAXV]; // 单调队列，存储链上的位置s int w[MAXN], v[MAXN], m[MAXN]; int main() { int n, V; cin >> n >> V; for (int i = 0; i < n; i++) { cin >> w[i] >> v[i] >> m[i]; } memset(dp, 0, sizeof(dp)); // 不要求恰好装满 for (int i = 0; i < n; i++) { int wi = w[i], vi = v[i], mi = m[i]; // 如果物品数量足够多，可以当作完全背包处理 if (mi * wi >= V) { // 完全背包的一维写法 for (int j = wi; j <= V; j++) { dp[j] = max(dp[j], dp[j - wi] + vi); } continue; } // 按余数分组 for (int r = 0; r < wi; r++) { int head = 0, tail = 0; // 队列头尾指针 // 遍历链上的位置t for (int t = 0; r + t * wi <= V; t++) { int cur = dp[r + t * wi] - t * vi; // 弹出队尾所有小于等于cur的元素 while (head < tail && dp[r + q[tail - 1] * wi] - q[tail - 1] * vi <= cur) { tail--; } q[tail++] = t; // 弹出队头超出窗口的元素 while (head < tail && q[head] < t - mi) { head++; } // 更新dp值 dp[r + t * wi] = dp[r + q[head] * wi] - q[head] * vi + t * vi; } } } cout << dp[V] << endl; return 0; }

4.2 关键代码段的逻辑拆解

这段代码有几个地方值得仔细推敲。首先是完全背包的特判：当mi * wi >= V时，意味着这种物品的数量足够多，可以覆盖整个背包容量，此时它等价于完全背包。这个特判不是必须的，但它能显著提升效率，因为完全背包的代码更简单，常数更小。

其次是队列的入队和出队顺序。在代码中，我们先入队再出队。这个顺序很重要。如果先出队再入队，当窗口大小为0时（即mi = 0），会导致队列为空却还要取队头的情况。先入队保证了队列中至少有一个元素。

第三是队列中存储的是位置t，而不是值。这是因为我们需要判断队头元素是否在窗口内。如果存储值，就无法知道它对应的位置。比较值时，通过dp[r + q[tail-1] * wi] - q[tail-1] * vi来获取。

第四是dp值的更新方式。我们直接用队头元素的值加上t * vi来更新dp[r + t * wi]。这里没有取max，因为队头元素已经是窗口内的最大值，加上t * vi后自然就是当前状态的最优值。

4.3 时间复杂度与空间复杂度分析

单调队列优化后的时间复杂度是O(V × N)。外层循环遍历N种物品，内层循环遍历所有容量（通过余数分组，每个容量恰好被访问一次）。每个元素最多入队一次、出队一次，所以内层循环的总操作次数是O(V)。整体复杂度是O(V × N)，与01背包和完全背包同阶。

空间复杂度是O(V + N)，其中dp数组占O(V)，队列占O(V)，物品信息占O(N)。这个空间复杂度非常优秀，即使V达到10^6级别也能轻松应对。

对比二进制拆分的O(V × Σlog m)，单调队列优化在m较大时优势明显。举个例子，如果N = 1000，每种物品的m = 1000，V = 10000，二进制拆分的复杂度大约是10000 × 1000 × 10 = 10^8，而单调队列优化是10000 × 1000 = 10^7，差了整整一个数量级。

5. 实测中的性能对比与常见错误排查

5.1 三种解法的实测数据对比

为了直观感受单调队列优化的威力，我设计了一组测试数据：N = 500，V = 20000，每种物品的w在1到100之间随机，v在1到100之间随机，m在1到1000之间随机。分别用朴素解法、二进制拆分和单调队列优化跑一遍，结果如下：

从数据可以看出，单调队列优化的速度是二进制拆分的7倍左右。当V和N进一步增大时，这个差距还会拉大。但单调队列优化的代码复杂度也明显更高，出错的概率更大。所以我的建议是：如果二进制拆分能过，就不要用单调队列；只有当二进制拆分超时的时候，才考虑单调队列优化。

5.2 单调队列写法的五个高频错误

在实现单调队列优化的过程中，我踩过不少坑。这里总结五个最常见的错误，希望能帮你节省调试时间。

第一个错误是队列的单调性方向搞反。单调队列维护的是递减序列，队头是最大值。如果写成递增，取出的就是最小值，结果完全错误。判断方向的方法很简单：我们要的是最大值，所以队列从队头到队尾应该递减。

第二个错误是出队条件写错。队头元素出队的条件是q[head] < t - mi，而不是q[head] <= t - mi。因为窗口范围是[t - mi, t]，包含t - mi这个位置。如果写成<=，会把窗口内的元素误弹出。

第三个错误是入队时比较的值不对。入队时比较的是dp[r + q[tail-1] * wi] - q[tail-1] * vi和cur，而不是dp[r + q[tail-1] * wi]和dp[r + t * wi]。因为我们要维护的是减去s * vi之后的值，而不是原始dp值。

第四个错误是dp数组的更新时机。必须在入队和出队都完成之后，再用队头元素更新dp值。如果在入队之前更新，队列中可能还没有当前元素，导致更新错误。

第五个错误是余数分组的循环上界。对于余数r，链上的最大位置t满足r + t * wi <= V，所以t的上界是(V - r) / wi。如果写成V / wi，当r > 0时会多算一些无效位置。

5.3 如何验证单调队列实现的正确性

单调队列优化的代码比较难调试，因为涉及队列操作和状态转移的耦合。我通常用两种方法来验证正确性。

第一种方法是对拍。写一个朴素解法作为暴力程序，随机生成小规模数据（N ≤ 10，V ≤ 100，m ≤ 10），然后对比两个程序的输出。如果所有测试数据都一致，说明单调队列的实现是正确的。这个方法虽然笨，但非常有效。

第二种方法是打印中间状态。在单调队列的每次操作后，打印队列的内容和当前的dp值，然后手动模拟一个小例子，看看是否符合预期。这个方法适合理解代码的执行流程，但比较耗时。

注意：对拍时一定要覆盖边界情况，比如m = 0、m = 1、w = 1、w = V、V = 0等。这些边界情况往往是bug的高发区。

6. 从多重背包到更一般的DP优化思维

6.1 单调队列优化的适用条件

单调队列优化并不是多重背包专属的技巧，它适用于一类更广泛的DP问题。这类问题的共同特征是：状态转移方程可以写成dp[j] = max(dp[j - k × w] + k × v)的形式，其中k有上限。换句话说，转移是在一个固定步长的链上进行的，且窗口大小固定。

判断一个问题能否用单调队列优化，可以看三个条件：第一，状态转移是否按固定步长进行；第二，转移是否涉及滑动窗口的最大值或最小值；第三，窗口大小是否固定。三个条件都满足时，单调队列优化就能派上用场。

除了多重背包，单调队列优化还常用于解决“滑动窗口最大值”类问题、优化某些区间DP、以及处理带限制的最长上升子序列等。掌握这个技巧，相当于在DP优化的工具箱里多了一把利器。

6.2 与二进制拆分的取舍策略

在实际做题时，二进制拆分和单调队列优化应该怎么选？我的经验是：先写二进制拆分，如果超时再改单调队列。原因有三：第一，二进制拆分的代码更简单，出错概率更低；第二，二进制拆分的思路更通用，不依赖于特定的状态转移形式；第三，大多数题目的数据规模并不会卡到必须用单调队列的程度。

但有一种情况例外：当物品数量m非常大（比如10^9级别）时，二进制拆分会产生log m个物品，如果N也很大，拆分后的物品总数可能仍然很大。这时候单调队列优化的O(V × N)优势就体现出来了，因为它完全不依赖于m的大小。

6.3 进一步优化的可能性

单调队列优化已经把多重背包的时间复杂度压到了O(V × N)，这已经是理论上的下界了，因为至少需要遍历所有物品和所有容量。但在实际应用中，还有一些常数级别的优化可以做。

第一个优化是特判完全背包。当mi * wi >= V时，直接按完全背包处理，省去了单调队列的开销。这个特判在m较大时能显著提升速度。

第二个优化是合并相同物品。如果两种物品的w、v、m完全相同，可以合并它们的数量。这个优化在数据有重复时有效，但需要额外的哈希或排序开销。

第三个优化是使用更紧凑的数据结构。比如用数组模拟队列而不是STL的deque，可以减少常数因子。在竞赛中，这个优化有时能把程序从超时边缘拉回来。

7. 我在实际编码中积累的几个小技巧

第一个技巧是关于队列数组的大小。队列中最多存储链上的所有位置，所以队列数组的大小应该至少是V / w + 1。为了安全起见，我通常直接开V + 5的大小，这样无论w是多少都不会溢出。

第二个技巧是关于负无穷的处理。如果题目要求恰好装满，dp数组初始化为-∞。在单调队列中，-∞参与减法运算可能会溢出。我的做法是用-0x3f3f3f3f代替，这个值足够小，不会影响最大值的选择，同时减法运算也不会溢出。

第三个技巧是关于循环的顺序。在外层循环中，我习惯先特判完全背包，再处理多重背包。这样代码结构更清晰，也避免了在单调队列中处理mi * wi >= V的情况。

第四个技巧是关于调试输出。在调试单调队列时，我会在每次更新dp值后打印dp[r + t * wi]和队列的状态。这样能直观地看到状态转移的过程，快速定位问题。

第五个技巧是关于测试数据的生成。我通常会生成三组数据：小规模随机数据用于对拍，中等规模数据用于测试性能，大规模数据用于测试边界。三组数据都通过后，才认为代码是正确的。

这些技巧看起来琐碎，但在实际编码中能帮你节省大量时间。尤其是对拍和边界测试，是保证代码正确性的最后一道防线。