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。对于固定的物品idp[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_ir是余数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 1000V 10000二进制拆分的复杂度大约是10000 × 1000 × 10 10^8而单调队列优化是10000 × 1000 10^7差了整整一个数量级。5. 实测中的性能对比与常见错误排查5.1 三种解法的实测数据对比为了直观感受单调队列优化的威力我设计了一组测试数据N 500V 20000每种物品的w在1到100之间随机v在1到100之间随机m在1到1000之间随机。分别用朴素解法、二进制拆分和单调队列优化跑一遍结果如下解法时间复杂度实测耗时ms适用场景朴素枚举O(V × Σm)超时10000m极小时可用二进制拆分O(V × Σlog m)约320大多数场景单调队列优化O(V × N)约45V和N都较大时从数据可以看出单调队列优化的速度是二进制拆分的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 ≤ 10V ≤ 100m ≤ 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]和队列的状态。这样能直观地看到状态转移的过程快速定位问题。第五个技巧是关于测试数据的生成。我通常会生成三组数据小规模随机数据用于对拍中等规模数据用于测试性能大规模数据用于测试边界。三组数据都通过后才认为代码是正确的。这些技巧看起来琐碎但在实际编码中能帮你节省大量时间。尤其是对拍和边界测试是保证代码正确性的最后一道防线。