做算法题做到背包问题这一块多重背包的朴素写法是个人都会写但数据范围稍微一上来就集体翻车。我在洛谷和 LeetCode 上反复碰到这类题一开始只会二进制拆分后来听说有人用“单调队列”能优化到 O(n*V)当时第一反应是“都拆成 01 背包了还能怎么优化”直到把状态转移方程拆开看才明白这里面的结构比想象中有意思得多。这篇笔记算是我把单调队列优化多重背包彻底啃透之后的学习记录从朴素 DP 的痛点讲起再到按余数分组的核心思想、单调队列的维护细节、完整代码实现最后附上我实际调试中踩过的几类坑。希望看完你也能自己推导出这套优化模板而不是死记代码。1. 多重背包问题的经典模型从新手写法到分析瓶颈1.1 问题定义与基本假设先明确问题本身有 n 种物品背包容量为 V每种物品有体积 w[i]、价值 v[i]、数量 c[i]。也就是说第 i 种物品最多能取 c[i] 个可以少取或者不取目标是让装入背包的物品总体积不超过 V同时总价值最大。这里和 01 背包、完全背包的区别就在“数量限制”上。01 背包每种物品只有一个完全背包每种物品有无限个多重背包落在中间有有限个但不止一个。正是这个“有限数量”的约束让状态转移方程里多了一层枚举个数的循环也引出了后面所有优化的动机。实际做题时数据范围通常长这样第一种是 n、V 都在 1000 以内c 也在 100 以内这种朴素写法直接过第二种是 n 在 1000 量级V 在 20000 左右c 也可能到 20000这时候暴力三层循环必然超时第三种更极端V 可能到 1e5 甚至更大那对算法的要求就更高了。我最早学多重背包的时候就是背了一个三层循环模板遇到需要用单调队列优化的题目时完全摸不着头脑因为根本不知道优化点在哪。1.2 朴素 DP 的状态设计与复杂度用 dp[j] 表示容量为 j 时的最大价值。对于当前物品 i假设体积为 w、价值为 v、数量为 c状态转移可以写成dp[j] max(dp[j], dp[j - k * w] k * v)其中 k 的取值范围是 1 到 c并且要求 k * w j。这个式子的含义非常直白当前容量 j 可以从“上一个物品阶段”的容量 j - k*w 转移过来然后放 k 个当前物品。如果完整写三层循环复杂度是 O(n * V * max(c))。n 是物品种类数V 是背包容量max(c) 是所有物品中最大的数量限制。这个复杂度在数据范围较小时没问题但 c 一大就崩了。我印象很深的一次是在模板题里n 1000V 20000每种物品数量 c 也是 20000三层循环直接跑了十几秒还出不来结果这才意识到必须优化。1.3 两个主流的优化方向针对多重背包业界最常见的两个优化方向是二进制拆分和单调队列。二进制拆分的思路很巧妙把数量 c 拆成若干个 2 的幂次组比如 c 13 时可以拆成 1、2、4、6 四组注意最后一组不是 8而是剩余部分每一组看作一个 01 背包物品。这样原来要枚举 k 次变成枚举约 log(c) 个组复杂度降到 O(n * V * log(c))。这个方案好理解、好写是我入门阶段用的主力。单调队列优化则是另一条路它不改变枚举次数而是把内层对 k 的枚举用滑动窗口最大值来批量处理总复杂度可以做到 O(n * V)。从理论上讲这是渐进意义下更优的做法。二进制优化在很多场景下已经够用但一旦 n * V 本身就很大再乘上 log(c) 就可能卡常这时候单调队列就体现出真正的价值了。2. 单调队列优化的核心思想按余数分组2.1 从状态转移方程里发现“同余”结构想要理解单调队列优化关键一步是盯住状态转移方程看结构。为了方便省略当前物品的下标 i记上一轮状态为 old本轮要算出的新状态为 dp。对于当前物品体积是 w价值是 v数量是 c。转移式是dp[j] max( old[j - kw] kv )其中 0 k c且 k*w j注意这里我特意把 k 0 也包含进去了含义是“一个当前物品都不取”也就是直接从 old[j] 继承过来。这看起来只是个小细节但对后面的窗口范围判断非常重要。现在把 j 拆开。令 d j % w那么 j 一定可以写成 j d xw 的形式其中 x 是整数。观察一下 old[j - kw] kv 这个式子j - kw d (x - k)*w它和 j 在模 w 意义下同余余数都是 d。这意味着什么如果两个容量 j1 和 j2 的余数 d 不同它们之间永远不会通过当前这个物品发生转移。余数相同的那些容量才可能互相转移。于是我们可以把 0 到 V 的所有容量按照对 w 取余的结果分成 w 组第 d 组d, dw, d2w, d3w, ...不同组之间完全独立可以分别处理。这就是“按余数分组”的核心思想。2.2 每组内部如何写转移式固定一个余数 d把这一组里的容量写成序列形式。令 x 0, 1, 2, ..., mx其中 mx (V - d) / w那么对应的容量就是 d x*w。原来的转移式中令 y x - k也就是说 k x - y。当 k 从 0 取到 c 时y 的取值就是从 x 往下数 c 个即 y 在区间 [x - c, x] 内。于是转移式变成dp[d xw] max( old[d yw] (x - y)*v )其中 y ∈ [max(0, x-c), x]到这一步很多人会卡住因为看起来还是要在区间内枚举 y并没有变简单。但如果把式子稍微整理一下dp[d xw] xv max( old[d yw] - yv )注意了方括号里 max 的部分是 old[d yw] - yv它只和 y 有关和 x 没有任何关系。也就是说对于固定的 x我只需要在合法的 y 区间 [max(0, x-c), x] 内找到 old[d yw] - yv 的最大值然后再加上 x*v 就是答案。这个合法区间很特别当 x 从 0 变成 1、2、3... 时区间 [x-c, x] 也跟着向右移动每次右移一位。这正是典型的滑动窗口问题。2.3 窗口长度到底是 c 还是 c1这里有一个特别容易出错的细节窗口长度应该是 c1不是 c。因为 y 的范围是从 x-c 到 x包含两端。y x 对应 k 0表示一个当前物品都不取y x-c 对应 k c表示正好取了 c 个当前物品。这两个边界都是合法的。如果你把窗口长度写成 c就会漏掉最左边的那个边界位置导致答案偏小。我第一次写的时候就是这里犯了错样例全过一提交就 WA最后把 dp 数组的中间量打印出来才发现在每个分组里取到的最大值都比暴力结果小一点点。后来我把窗口长度检查了一遍改成 x - q[head] c 时才弹出队首答案立刻对了。3. 单调队列基础滑动窗口最大值是怎么回事3.1 先从独立的小问题说起在回到多重背包之前先单独理解单调队列这个工具。假设有一个数组 a[0..n-1]窗口大小为 k我想求每个位置 i 对应的窗口 [i-k1, i] 内的最大值。最朴素的做法是对每个 i 都扫描窗口内 k 个元素复杂度 O(n*k)。当 n 和 k 都很大时这个复杂度没法接受。单调队列的做法是维护一个双端队列队列里存的是数组下标同时保证这些下标对应的值从队首到队尾是严格递减的。这样队首永远是当前窗口最大值。具体操作分三步每次窗口右移时先处理新元素 a[i]把队尾所有值小于等于 a[i] 的下标弹出然后把 i 放到队尾。检查队首是否已经滑出窗口如果弹出。此时队首元素就是当前窗口最大值的下标。这里的“弹出队尾所有小于等于新元素的下标”是关键。为什么可以这么做因为旧元素既比新元素老值又不比新元素大它在未来任何窗口内都不可能成为最大值了。这个淘汰逻辑保证了队列里的元素始终是单调递减的。3.2 每个元素只会入队出队一次均摊 O(1)单调队列最有价值的地方在于虽然每个窗口内可能有多个元素但每个数组元素最多入队一次、出队一次所以总复杂度是 O(n)均摊到每个位置就是 O(1) 的更新。这也是为什么它能在很多 DP 优化问题里直接把一层循环去掉。我最初学的时候总是担心“弹出队尾之后窗口最大值会不会丢失”实际上不会。因为被弹出的元素一定不如当前新元素“年轻且大”在同一个窗口内新元素完全可以替代它。单调队列本质上是维护了一个候选集合集合里每个元素都比后面的元素更有可能成为未来窗口的最大值。3.3 手写数组模拟双端队列的写法竞赛环境下我一般不用 STL 的 std::deque原因很简单性能不如手写数组而且调试时不如数组直观。手写队列的常用姿势是int q[MAXN], head 0, tail 0; // [head, tail) 是队列有效区间 // 入队q[tail] idx; // 弹出队尾tail--; // 弹出队首head; // 队列判空head tail这里的 head 指向队首tail 指向队尾的下一个位置。把队列长度限制在 MAXN 以内使用数组下标访问所有操作都是 O(1)而且可以方便地在队列里存任意信息比 deque 可控得多。3.4 队里存下标还是存值为什么很多初学单调队列的人会问队列里直接存“值”不就行了吗为什么非要存下标答案很简单因为光知道值不知道这个元素在哪一个位置就没法判断它是否已经滑出窗口。在多重背包的优化里这个问题更明显。我们需要判断当前 x 和队首下标的差值是否超过 c这必须依赖下标。如果你只存 dp 值窗口过期判断就做不了了。所以队列里存的一定是下标对应我们每组里的 y需要比较大小的时候再用下标去取 old 数组里的值做计算。4. 单调队列优化多重背包完整推导与代码实现4.1 把递推式改造成滑动窗口模型综合前面的分析现在整理成可实现的算法。对于每个物品假设体积为 w、价值为 v、数量为 c先备份上一轮状态到 old 数组。枚举余数 d从 0 到 w-1其中 d V。在余数 d 的分组内x 从 0 递增到 mx (V - d) / w。维护一个关于 y 的单调队列窗口范围是 [x - c, x]队列中的元素按 old[d yw] - yv 的值的递减排列。对于每个 xdp[d xw] xv 队首对应的 old[d q[head]*w] - q[head]*v。整个算法的核心就在第 4 步随着 x 每次加 1窗口右移一位正好是单调队列最擅长的场景。4.2 为什么必须复制 old 数组不能原地更新这是新手最容易踩的大坑。在多维背包优化中01 背包和完全背包都可以用滚动数组原地更新只是遍历顺序不同。但单调队列优化的多重背包不能在一个 dp 数组上原地更新必须单独保存 old。原因在于同一个余数分组内当 x 增大时我会用它前面那些 y 位置的 old 值来更新当前 dp[d xw]。如果 dp 数组已经被本轮更新过那么队列中保存的 old[d yw] 可能已经不是上一轮的值了导致比较和窗口最大值全部出错。所以每处理一个新物品第一步一定是把上一轮的 dp 完整拷到 old 里。空间复杂度 O(V)完全可接受。4.3 C 完整实现模板下面给出一份可以直接用的 C 模板。这份代码我在很多题目里跑过稳定性和常数都比较理想。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, V; cin n V; vectorint dp(V 1, 0), old(V 1, 0); vectorint q(V 1); // 单调队列存 y 下标 for (int i 0; i n; i) { int w, v, c; cin w v c; if (w V) continue; // 装不下直接跳过 old dp; // 关键保存上一轮状态 // 按余数 d 分组 for (int d 0; d w d V; d) { int head 0, tail 0; // x 是当前容量在分组内的编号容量 d x * w for (int x 0; d x * w V; x) { // 当前 y x 的候选值old[d x*w] - x*v int cur old[d x * w] - x * v; // 维持队列单调递减 while (head tail old[d q[tail - 1] * w] - q[tail - 1] * v cur) { --tail; } q[tail] x; // 剔除过期队首窗口范围 [x-c, x] while (head tail x - q[head] c) { head; } // 队首即窗口内最大值 dp[d x * w] old[d q[head] * w] - q[head] * v x * v; } } } cout dp[V] \n; return 0; }模板里有几个小细节需要解释第一old dp 这一步用到了 vector 的拷贝赋值每次物品都整体拷贝一遍。如果你担心性能可以用静态数组配合 memcpy不过 vector 赋值在现代 C 编译器下已经足够快一般题目没问题。第二d 的循环条件是 d w d V。为什么要有 d V因为如果 d 本身已经大于 V那么 d x*w 一定大于 V这一组根本没有有效位置循环纯属白跑还可能越界。第三q 数组的大小开 V1 就够。因为每个分组内 x 的最大值不会超过 Vw 最小是 1所有分组加起来也只会入队 V1 次左右。4.4 Python 版本实现参考Python 写这个优化逻辑一样但要小心性能。最直接的写法def multiple_knapsack(n, V, items): dp [0] * (V 1) for w, v, c in items: if w V: continue old dp[:] for d in range(w): if d V: break q [] head 0 for x in range((V - d) // w 1): idx d x * w cur old[idx] - x * v while len(q) head and old[d q[-1] * w] - q[-1] * v cur: q.pop() q.append(x) if len(q) head and x - q[head] c: head 1 best old[d q[head] * w] - q[head] * v x * v dp[idx] best return dp[V]这里用 head 指针模拟队列的弹出操作避免频繁 list.pop(0)。当 head 增长到一定大小时可以顺手清理 q 的前半部分不过对于一般题目的数据范围不清理也影响不大。Python 的常数比较大这道题如果是极限数据建议还是用 C 跑。4.5 先入队再弹队首的顺序问题关于入队和弹出过期元素的顺序我有一个偏好的写法先把当前 x 入队再剔除过期的队首。这样做的好处是逻辑统一。因为当前 x 一定在窗口 [x-c, x] 内入队后队列里所有元素都在 x 右侧边界内接下来只要把那些 x - q[head] c 的旧元素弹出剩下的就都在合法窗口内。如果你先弹过期元素再入队本质上也可以但要注意窗口左边界在更新前是 [x-1-c, x-1]入队当前 x 后变成 [x-c, x]两者其实等价。只是我写代码时容易搞混所以固定成先入队再弹队首减少出错概率。5. 复杂度分析与正确性证明5.1 时间复杂度为什么是 O(n*V)这个优化最吸引人的地方就是复杂度。对每个物品外层余数 d 从 0 到 w-1内层 x 从 0 到当前分组最大编号。把所有这些 (d, x) 组合排列起来仔细观察会发现每个组合 (d, x) 都对应一个容量值 d xw而且这个值恰好遍历了 0 到 V 之间的所有整数一遍。也就是说处理一个物品时总共只访问了 V1 个位置。每个位置入队一次、出队最多一次所有操作都是 O(1)。所以一个物品的复杂度是 O(V)n 个物品合计 O(nV)空间复杂度 O(V)。这个结论和 01 背包、完全背包的复杂度量级是一样的但比朴素多重背包的 O(nVc) 和二进制优化的 O(nVlog(c)) 都要低。5.2 正确性证明思路如果要给队友讲清楚为什么这是对的可以按三个层次说。第一层转移等价。原始转移 dp[j] max(old[j - kw] kv), 0 k c经过 j d xw 和 y x - k 的变量代换等价于 dp[dxw] xv max(old[dyw] - y*v), y ∈ [max(0, x-c), x]。这里没有做任何省略变量代换是等价的。第二层窗口正确。随着 x 递增合法区间 [max(0, x-c), x] 的左右端点都在单调右移。单调队列恰好维护了这样一个动态窗口内的最大值且因为每个元素只入队出队一次能保证每次取到的都是当前窗口最大值。第三层滚动数组语义正确。old 数组保存的是“只考虑前 i-1 种物品”时的最优值dp 数组本轮更新后变成“考虑前 i 种物品”的最优值。归纳到所有 n 种物品处理完dp[V] 就是最终答案。5.3 和二进制优化的选择建议很多人会问既然单调队列优化复杂度更低是不是以后都写单调队列就行了我的看法是分场景。二进制优化写起来快不容易出错代码短适合在时间限制比较宽松或数据范围中等的时候使用。单调队列优化常数不小数组拷贝、分组循环、队列维护这些操作叠加起来可能和二进制优化在实际运行时间上差距并不悬殊。但只要数据范围逼近极限比如 n 1000、V 20000二进制优化要再乘一个 log(c) 的因子这时候单调队列优化的优势就非常明显了。我自己一般先看数据范围V * n * max(c) 是否可接受不能接受就优先单调队列如果题目本身是模板题只是为了练习两种都写上顺便对拍一下。两道代码都能过心里就有底了。6. 实战调试心得与常见问题速查6.1 用一个小样例验证正确性先给一个可以手算的样例方便你验证自己的模板3 10 2 3 3 3 4 2 4 5 2三种物品容量 10。第一种物品体积 2、价值 3、最多 3 个第二种体积 3、价值 4、最多 2 个第三种体积 4、价值 5、最多 2 个。手算一下最优解可以选 2 个第一种物品体积 4价值 6加 2 个第二种物品体积 6价值 8总体积正好 10总价值 14。也可以选 3 个第一种物品体积 6价值 9加 1 个第三种物品体积 4价值 5总体积也是 10总价值 14。所以答案是 14。用上面的 C 模板跑这个样例输出应该是 14。如果输出不对优先检查是不是窗口长度写成了 c或者是不是没有使用 old 数组。6.2 边界数据测试清单模板写完我习惯用下面这些边界数据自测只有一种物品容量足够装很多个验证数量限制是否生效。某件物品数量为 0这种情况虽然题目很少出现但代码应该能正确跳过。某件物品体积大于 V应该直接跳过不能进入分组循环。V 为 0所有 dp 值都应该是 0。所有物品数量都很大大到每组窗口根本不会触发过期验证单调队列仍能工作。c 特别大大到 c*w 超过 V此时窗口左边界应该收敛到 0而不是出现负数下标。这些测试都跑过一遍基本可以确信模板没有低级错误。6.3 我在调试中踩过的几个经典大坑第一个坑是忘了备份 old 数组。这个是最大的坑症状是结果比正确值小不少而且很难靠肉眼看出来。调试方法很简单写一个暴力三重循环的版本随机生成小数据两个程序对拍。如果暴力结果和优化结果不一致十有八九是 old 数组的问题。第二个坑是队列清空时机。每处理一个新的余数 d都必须重新把 head 和 tail 置为 0。如果忘了重置队列里残留上一组的数据会严重干扰当前组的窗口判断。我犯过这个错现象是只有最后一组结果正确前面的分组全部错乱。第三个坑是数组长度。q 数组长度至少是 V1。有些时候你觉得分组内 x 不会很大开小了结果在边界情况就崩了。建议统一开到 V5保证不会越界。第四个坑是 int 溢出。价值累加和 xv 可能超过 int 范围尤其当 v 很大、x 也很大时。竞赛题里如果价值上限是 1e9容量上限是 1e5那么 xv 可能到 1e14必须用 long long。建议直接全部用 long long避免改来改去。6.4 调试技巧打印每个分组的队列变化如果你在调试时实在找不出问题我推荐一个笨方法在循环里把每个 d 分组、每个 x 的 head、tail、队列内容、最终 dp 值全部打印出来然后和暴力版本的中间过程对比。这个方法看起来繁琐但效果立竿见影。比如窗口长度写错的问题打印之后你会看到队首位置过早被弹出导致窗口内元素变少old 数组没备份的问题打印后你会看到本轮新值混进了 old 计算里。定位到具体某一步修复就快了。6.5 单调队列优化在其他 DP 问题里的扩展学完这个优化你会发现它的套路不止能用在多重背包上。凡是转移形如 dp[i] max(dp[j] cost(i, j))且 j 的取值范围随着 i 增大而单调右移都可以考虑单调队列。常见的还有滑动窗口最值、一些连续子序列问题、部分状态压缩 DP 的优化等。关键在于抓住“区间右端点单调移动”这个特征。多重背包里x 每加一窗口左端和右端都同步右移才让单调队列成为可能。遇到新的 DP 题时可以先观察转移方程能不能整理成“某一段区间最大值 当前项”的形式如果能就该往单调队列方向想了。写代码这件事看十遍不如自己敲一遍。尤其单调队列这种数据结构细节藏在边界和顺序里。建议你拿到模板后自己动手推导一遍转移方程再照着实现最后用暴力程序对拍几组数据。等你真正把“为什么窗口长度是 c1”“为什么必须用 old 数组”“为什么队首就是最大值”这几个问题都能脱口而出时这个优化才算真正属于你了。