很多人学动态规划背包问题算是最经典的入门关卡。但说实话01背包和完全背包很多人背一背状态转移就过了真正让人头皮发麻的是多重背包——每种物品有数量限制不是只有一件也不是无限拿。网上讲多重背包的文章不少但多是直接丢个优化结论看完代码还是不知道为什么。这次我把多重背包的几种主流写法从头到尾拆一遍顺带把完全背包的思路也整理清楚希望能帮你把这几类背包真正打通。先说清楚一个容易混淆的点完全背包不是多重背包的“无限数量版”那么简单两者在状态转移方向、优化思路上都有本质区别。但反过来多重背包在某些条件下可以借用完全背包的写法。这些内容我都会在下面展开。1. 问题的定位多重背包、完全背包和01背包的关系1.1 从01背包到多重背包一件物品的“限量供应”先回顾01背包的状态转移这是整个背包家族的地基$$dp[j] \max(dp[j], ; dp[j - w[i]] v[i])$$含义很简单容量为$j$的背包要么不拿第$i$件物品要么拿一件并腾出$w[i]$的空间。因为每件物品只有一件所以容量必须倒序遍历避免同一件物品被重复使用。完全背包的区别在于“每件物品可以拿无限件”于是状态转移变成了正序遍历$$dp[j] \max(dp[j], ; dp[j - w[i]] v[i])$$转移公式看起来一模一样唯一的差别是容量循环方向。但正是这个方向差异导致完全背包的朴树复杂度只有$O(NV)$比多重背包的朴素写法快一个数量级。至于为什么后面我会单独展开。多重背包的问题设定是第$i$种物品有$c[i]$件每件重量$w[i]$、价值$v[i]$。它既不是01背包那种“每样一件”也不是完全背包那种“无限供应”而是中间状态有上限但上限大于1。朴素想法很直接把第$i$种物品拆成$c[i]$个独立的01背包物品然后跑一遍01背包。比如某件物品有5件就当成5个独立物品每个只能选一次。这样问题就退化成了01背包。缺点是复杂度太高复杂度为$O(NVC)$$C$是单种物品的数量上限。一旦$N$、$V$、$C$三个维度都到几千基本就等着超时了。1.2 为什么朴素写法在数据一大时就过不了我最初学多重背包时第一版代码长这样for (int i 1; i n; i) { int w, v, c; cin w v c; // 倒序枚举容量 for (int j V; j 0; --j) { // 枚举第 i 种物品选 k 件 for (int k 0; k c k * w j; k) { dp[j] max(dp[j], dp[j - k * w] k * v); } } }这个写法思路没错但你看三重循环外层是物品种类中层是容量内层是件数。粗略算一下$N100$$V1000$$C100$这就是$10^7$量级勉强能跑。但如果数据范围变成$N100$$V10000$$C10000$复杂度瞬间到$10^{10}$任何OJ都扛不住。所以多重背包的核心难题不是“怎么定义状态”而是“怎么把$C$这个维度消掉”。这也是下面所有优化的共同目标。2. 二进制优化把“数量”压成“二进制块”2.1 二进制拆分的原理用组合代替枚举二进制优化的出发点是一个很朴素的问题给你$c$件相同的物品真的需要枚举$0$到$c$的每一个数量吗不需要。因为我们不需要知道“选$k$件”的所有细节只需要知道“能否凑出某个数量”以及“凑出这个数量能带来多少价值”。而任意一个$0$到$c$之间的整数都可以用若干个$2$的幂次组合表示。具体拆分规则是把$c$拆成$1, 2, 4, 8, \dots, 2^m$以及末尾剩下的$r$$r 2^{m1}$。举个例子$c 13$$$13 1 2 4 6$$这里$1, 2, 4$是连续的二幂次最后剩下$6$。你可以验证一下从$0$到$13$的任意数量都能由$1, 2, 4, 6$这个集合中的若干个数相加得到。比如$7 1 6$$11 1 4 6$$13 1 2 4 6$。这就是二进制优化的数学基础。为什么不用$1, 2, 4, 8$呢因为$1 2 4 8 15 13$凑出的组合会超过实际数量导致选了“不存在的物品”。所以最后一个块必须是余数。拆分完以后每个块看成一个独立的01背包物品块的大小是$k \times w$价值是$k \times v$。原来枚举$c$次的复杂度现在只需要枚举$\log_2 c$个块。2.2 拆分的代码实现和边界细节下面这段是我在实际中一直用的拆分写法for (int i 1; i n; i) { int w, v, c; cin w v c; int k 1; while (k c) { // 把大小为 k 的块作为一个新物品 goods.push_back({k * w, k * v}); c - k; k 1; // k * 2 } if (c 0) { goods.push_back({c * w, c * v}); } } for (auto [ww, vv] : goods) { for (int j V; j ww; --j) { dp[j] max(dp[j], dp[j - ww] vv); } }这里有三个特别容易踩坑的地方我逐一说明。第一个坑是循环里的c一直在被削减。很多人忘了c - k导致k虽然翻倍了但原始数量没有被正确扣除拆分出来的块大小总和超过原数量。每次循环把k加进goods后必须同步从c里减掉k这是拆分的核心逻辑。第二个坑是最后剩下的那个零头不能丢。比如$c10$拆完$1, 2, 4$后剩下的$3$还有个块如果漏掉它总数量只有$1 2 4 7$凑不出$8, 9, 10$这些数量。这个错误很隐蔽因为大多数测试数据里$c$恰好是二幂次减一的时候不会暴露一旦$c$是普通数字结果就错得莫名其妙。第三个坑是拆出来的件数$k$乘上重量$w$后可能超过容量$V$在01背包的容量循环里直接被跳过这是正确的不会影响结果但会造成一点性能浪费。如果想要更严谨可以在拆分时加上判断如果k * w V说明这个块不可能放进背包可以不加入goods。二进制优化后的复杂度是$O(NV \log C)$。虽然看起来还带着$\log C$但实际运行中比朴素写法快了几个数量级。$N100$, $V10000$, $C10000$的数据朴素写法到$10^9$以上二进制优化直接降到$10^7$左右这就是能过和不能过的差距。3. 单调队列优化把多重背包压到O(NV)的原理与实现3.1 从转移方程式推导单调队列的用法二进制优化很好但它是多重背包的终点吗不是。实际上多重背包存在$O(NV)$的最优解法这就是单调队列优化也叫滑动窗口优化。我知道很多人听到“单调队列”就觉得头大但其实它的推导过程是有迹可循的。把多重背包的状态转移写成通式$$dp[j] \max_{0 \le k \le c,; k \cdot w \le j} (dp[j - k \cdot w] k \cdot v)$$现在做一步关键变形。固定余数$r j \bmod w$把容量$j$写成$$j r t \cdot w$$其中$t j / w$向下取整。代入转移方程式$$dp[r t \cdot w] \max_{0 \le k \le \min(c, t)} (dp[r (t - k) \cdot w] k \cdot v)$$令$t - k u$则$u$的取值范围是$[t - c, t]$于是$$dp[r t \cdot w] t \cdot v \max_{t - c \le u \le t} (dp[r u \cdot w] - u \cdot v)$$观察这个式子括号里的部分只跟$u$有关跟$t$无关。所以对于同一个余数$r$当$t$从$0$递增到最大值时括号里的候选值形成一个序列我们只需要在长度为$c$的滑动窗口内找最大值。这正好是单调队列的经典应用场景。过程可以形象地理解成把所有容量按余数分成$w$类每一类内部沿着“每加一个$w$就看一格”的方向滑动窗口每次队首就是当前窗口的最大值。3.2 滚动数组下的旧值保护与完整实现这里有一个非常容易忽略的细节也是我当时第一次写单调队列优化时卡了很久的原因dp数组在滚动更新而计算当前物品时用到的数据必须是上一轮的结果不能是已经被当前物品更新过的数据。如果直接用dp数组既当输入又当输出会发生什么处理第一个余数类时dp[r1 t*w]被更新了处理第二个余数类时如果它的某个容量引用了第一个余数类的旧值拿到的是新值这就破坏了DP的“阶段性”。所以稳妥的做法是先把dp拷贝到old数组计算时从old取数更新到dpfor (int i 1; i n; i) { int w, v, c; cin w v c; if (c * w V) { // 当总重量超过背包容量等同于完全背包 for (int j w; j V; j) { dp[j] max(dp[j], dp[j - w] v); } continue; } // 保存上一轮的值 memcpy(old, dp, sizeof(old)); for (int r 0; r w; r) { // 队列存的是 u 的值即 r u * w 中的 u int head 0, tail 0; // 注意每个余数类里面t 从 0 开始递增 for (int t r; t V; t w, cnt) { // cnt 当前是第几个块也就是 t/w 向下取整 } } }上面的代码还缺一个关键部分就是cnt和队列的具体维护。我补一个更完整的版本用数组模拟队列队列里存的是下标ufor (int i 1; i n; i) { int w, v, c; cin w v c; if (c * w V) { for (int j w; j V; j) { dp[j] max(dp[j], dp[j - w] v); } continue; } memcpy(old, dp, sizeof(old)); for (int r 0; r w; r) { int head 0, tail 0; // q 存的是 u也就是商 int q[N]; int cnt 0; for (int t r; t V; t w, cnt) { // 把当前 u cnt 加入队列 int curVal old[t] - cnt * v; while (head tail q[tail - 1] cnt - c) { // 这一行其实是多余的判断窗口淘汰在下面处理 } // 队尾出队如果队尾的候选值不大于当前值则队尾永远不可能成为最优 while (head tail old[r q[tail - 1] * w] - q[tail - 1] * v curVal) { --tail; } q[tail] cnt; // 队头淘汰u cnt - c 的超出了窗口范围 while (head tail q[head] cnt - c) { head; } // 用队头更新 dp[t] dp[t] old[r q[head] * w] (cnt - q[head]) * v; } } }这里队列里存的是$u$每个$u$对应的实际容量是$r u \cdot w$。每次处理新的$t$即新的$cnt$先把$cnt$作为候选加入队列再淘汰过期下标最后从队头取值。注意两个while循环的顺序问题。我写的时候习惯“先入队再淘汰”但严格来说先淘汰再入队也可以。区别在于如果新加入的候选本身就是当前窗口内最新的值入队前需要保证队列的单调性而窗口淘汰是为了不让过期值留在队头。顺序上“先入队再淘汰”有一个好处即使新值入队后马上被淘汰也不影响结果因为淘汰逻辑依赖的是cnt - c不会误删当前值。不过初学者最好固定一种写法不要每次临时变。3.3 一个可运行的对照测试为了验证单调队列优化的正确性我拿一个具体例子手算过假设$N2$$V10$物品1$w3$, $v5$, $c2$物品2$w4$, $v7$, $c3$用朴素写法和单调队列优化分别跑最优组合是物品1选2件占6容量价值10物品2选1件占4容量价值7总容量正好10总价值17。我在本地用这个用例测过三种写法结果一致。如果你也写了这三种写法建议先用这种小例子验证再上大数据测性能能省很多调试时间。4. 完全背包的正序枚举写法与“转化”思路辨析4.1 完全背包的正序循环到底在做什么完全背包的状态转移方程和01背包长得一样但容量遍历方向完全相反。01背包必须倒序因为正序会导致同一件物品被重复选择完全背包恰恰利用了这个“缺陷”。看一个极端例子背包容量$V5$一件物品重量$w2$价值$v3$无限件。正序遍历$j2$$dp[2] \max(dp[2], dp[0]3) 3$$j3$$dp[3] \max(dp[3], dp[1]3) 3$$j4$$dp[4] \max(dp[4], dp[2]3) 6$当$j4$时dp[2]已经在当前轮被更新成了3所以dp[4]更新为6相当于选了两件。这就是“正序允许重复选择”的直观体现。这段推导值得在纸上画一遍。很多资料直接告诉你“完全背包正序01背包倒序”没讲本质。当你真正理解了这个方向差异的根源以后遇到“每种物品有次数上界且上界很大”的问题时一眼就能判断能不能套完全背包的思路。4.2 完全背包与其他背包的互相转化与误区完全背包本身不需要二进制优化这一点经常被初学者搞混。因为完全背包的朴素写法复杂度已经是$O(NV)$如果把一个物品拆成多个块再跑01背包复杂度反而变成了$O(NV \log(V/w))$更差了。二进制优化是针对“有限件数”设计的无限件数直接正序跑就行。但反过来多重背包在某些情况下可以“冒充”完全背包。判断条件很直接如果物品的总重量$c \cdot w \ge V$意味着即使把所有件数都塞进容量为$V$的背包也塞不完。这时“数量上限”约束实际上不生效它退化成了完全背包。我在第3节代码里用的就是这个判断if (c * w V) { // 当作完全背包处理 }这个优化在单调队列写法里尤其有用能省掉整个分余数类的过程。还有一类问题是从完全背包延伸的变种比如最小花费求装满背包恰好需要的最少物品数方案数求装满背包有多少种不同的组合方式价值随数量变化第$k$次选某件物品时价值不同这些变种的思路根子还是在“正序枚举”和“容量循环方向”上。做题时先把问题归类到背包模型再决定方向比硬套模板靠谱得多。5. 数据范围成套测试与实战踩坑记录5.1 不同数据范围下应该选哪种写法我整理了一份选择表方便你在实际做题时快速决策数据规模推荐写法时间复杂度$N \le 100$$V \le 1000$$C \le 100$朴素三重循环$O(NVC)$$N \le 100$$V \le 10000$$C \le 10^4$二进制优化$O(NV\log C)$$N \le 100$$V \le 10000$$C \le 10^5$且总数据规模紧卡时限单调队列$O(NV)$$c \cdot w \ge V$完全背包正序思路$O(NV)$这里注意即使理论上单调队列最优实际做题时我也会先考虑二进制优化。原因很简单——二进制优化代码短、调试容易、出错概率低。只有数据范围明确要求必须$O(NV)$或者单调队列能明显降低常数时才用。5.2 实测中容易翻车的细节清单这些坑是我在多次练习和帮别人review代码时真实遇到的每一条都能让程序在某个测试点上挂掉初始化问题如果题目要求“恰好装满”dp[0] 0其他容量初始化为负数极大值比如-0x3f3f3f3f。如果不要求恰好装满全部初始化为0。这两种初始化的结果完全不同选错了边界数据肯定错。容量循环方向多重背包的二进制优化本质上是在跑01背包容量必须倒序。我曾经把二进制优化后的goods当成完全背包做正序循环结果每一种拆出来的块都被选了无数次答案彻底错乱。每次写完都自查一遍这段代码代表的背包模型是什么循环方向对不对单调队列的窗口大小窗口大小是$c$不是$c-1$也不是$c1$。因为最多选$c$件所以窗口里最多有$c1$个候选值从0件到c件但“最多选c件”和“窗口大小为c”在代码里对应的是q[head] cnt - c这个淘汰条件。我建议把这个推导再走一遍如果$u cnt - c$说明$(t - u) c$即选的件数超过了上限。理解了这一点写淘汰条件就不会差一。单调队列中拷贝旧数组的必要性我在3.2节反复强调的滚动数组下不备份old同一个余数类的更新会污染其他余数类。个别优化写法不需要备份但那需要非常谨慎地控制访问顺序对新手不友好不如老老实实memcpy一份。memcpy的性能开销可以接受毕竟一次拷贝是$O(V)$在整个算法里占比很小。5.3 从多重背包到背包体系的整体思考学完多重背包的三种写法再回头看01背包和完全背包能发现一个清晰的递进关系01背包是“每件一个”的特例完全背包是“无限供应”的特例多重背包则位于两者之间。从朴素枚举到二进制优化再到单调队列优化的本质都是减少枚举的冗余度。这种“先写朴素版本验证正确性再逐步优化复杂度”的思路不止适用于背包问题也适用于其他DP问题比如区间DP、状压DP、树形DP。我现在拿到一道DP题习惯先确认状态定义和转移方向再手推几组小样例确认无误后才写优化版本。优化不是炫技而是在朴素版本正确的基础上做减法。这个习惯帮我避免了很多“优化半天结果基础逻辑就是错的”的尴尬。最后再分享一个排错技巧如果单调队列版本的答案和朴素版对不上别急着怀疑单调队列的窗口逻辑先把dp数组每一步的值打出来和朴素版逐项对比。通常很快就能定位是某个余数类处理错了还是窗口淘汰边界写错了。对比几次之后你会发现这类问题的规律性很强熟练了反而不容易出错。