尧图网站开发 
背包问题几乎是每个学动态规划的人绕不开的一道坎。01背包、完全背包、多重背包难度层层加码很多人都是靠死记模板混过去的。我自己刚开始学多重背包的时候也干过蠢事因为完全背包用正序循环就把多重背包也直接正序刷了一遍结果答案大得离谱当时还以为是数据错了。后来才明白多重背包最难的地方从来不是状态转移方程本身而是如何在数量限制的约束下把复杂度压下去。这篇文章就把我自己用过的几种多重背包写法从头到尾捋一遍顺便把完全背包为什么能正序循环这件事说透。先交代一下场景设定。题目一般长这样有 n 种物品每种物品有体积 v[i]、价值 w[i]、数量上限 c[i]背包容量为 V求能装下的最大总价值。多重背包和完全背包最大的区别就在这个 c[i]——完全背包里每种物品想拿多少个拿多少个多重背包拿了超过 c[i] 个就算非法。这个限制看着不起眼却直接把时间复杂度从 O(NV) 抬到了 O(NV·C)逼得我们不得不想优化手段。1. 从朴素做法开始多重背包的暴力美学1.1 问题定义与状态设计不管是哪种背包状态设计都是老一套dp[j] 表示容量为 j 的背包能获得的最大价值。数组开一维就够了滚动更新的时候注意顺序问题就行。对于多重背包最直接的想法就是把每种物品拆成“拿 0 个、拿 1 个、拿 2 个……拿 c[i] 个”这 c[i]1 种选择然后暴力枚举。这里有个细节容易忽略我们枚举的是“第 i 种物品拿几个”而不是“是否拿第 i 种物品”。一旦你把它当成 01 背包来做就会发现状态定义变了味道。所以我个人建议新手先写二维的朴素版本把状态转移看清楚再压缩成一维。二维的写法是这样的dp[i][j] 表示前 i 种物品、容量为 j 时的最大价值。转移的时候枚举第 i 种物品拿 k 个k 的范围是 0 到 c[i]同时要满足 k * v[i] j。转移方程写出来非常规整dp[i][j] max(dp[i-1][j], dp[i-1][j - kv[i]] kw[i])其中 1 k c[i] 且 k*v[i] j这个方程其实是在说我不拿第 i 种物品直接从 i-1 转移或者我拿 k 个第 i 种物品那前面的 i-1 种物品只能占 j - k*v[i] 的容量。看起来很和谐但一旦写成一维滚动数组坑就来了——如果你像 01 背包那样逆序枚举 j再在内层枚举 k那没问题如果你正序枚举 j就会导致同一轮循环里重复使用第 i 种物品相当于突破了 c[i] 的限制。这一点下文还会反复强调。1.2 三重循环写法与复杂度一维的朴素写法在竞赛里很常见代码长这样// c[i]: 数量, v[i]: 体积, w[i]: 价值, V: 背包容量 for (int i 1; i n; i) { for (int j V; j 0; j--) { // 容量逆序参照01背包 for (int k 1; k c[i] k * v[i] j; k) { dp[j] max(dp[j], dp[j - k * v[i]] k * w[i]); } } }为什么这里的 j 要逆序因为一维数组里 dp[j-kv[i]] 如果在本轮被更新过就代表第 i 种物品已经被取过一次那 k 再往上加就相当于多次取用同一种物品。逆序枚举可以保证本轮更新 dp[j] 用到的 dp[j-kv[i]] 还是上一轮 i-1 的状态这样第 i 种物品在每一轮里最多只被“引入”一次。我当年写这个三层循环的时候经常把 k 的起点写成 0那样其实也不需要因为 dp[j] 本身就是不取第 i 种物品的情况k0 是多余的。复杂度也很直观外层 n 种物品中层容量 V内层最多 c[i] 个数量。整体是 O(n * V * max(c[i]))如果每个 c[i] 都是 10^5 量级那直接爆炸。所以朴素写法只适合小数据比如 V 1000、c[i] 100 之类的题目。1.3 什么时候我需要用朴素写法有些朋友会觉得朴素写法这么土还不如直接学二进制优化。但我的经验是朴素写法至少有两个不可替代的价值。第一它是调试的基准。你写二进制优化、写单调队列优化的时候答案对不对拿什么做对照拿朴素写法做暴力对拍是最稳的。我自己写这种复杂 DP 的时候一定会保留一份暴力版本用来随机数据对拍。没有它优化版写错了你都不知道错在哪。第二有些题目的数据范围很小根本不需要优化。比如 n 20、V 100、c[i] 10这种数据你上单调队列反而浪费时间朴素写法几毫秒就跑完了。做题的第一步永远是看数据范围而不是背模板。很多新手一上来就套最难的写法不仅代码长还容易出 bug最后得不偿失。2. 完全背包思路正序循环背后的玄机2.1 为什么完全背包要正序遍历完全背包的多重背包最大的区别是每种物品的数量不限。所以它的状态转移方程比多重背包更简单直接用 01 背包改一个符号就行。我直接给结论01 背包的容量循环是逆序完全背包的容量循环是正序。就这一个差别代码从 01 背包改成完全背包只需要把 for (int j V; j v[i]; j--) 改成 for (int j v[i]; j V; j)。道理也不复杂。正序循环意味着 dp[j - v[i]] 在本轮已经被更新过了。这个 dp[j - v[i]] 可能是已经取了一次第 i 种物品之后的状态于是你再取一次就相当于允许同一件物品被取无限次。逆序循环刚好相反它保证 dp[j - v[i]] 还是上一轮的状态也就是第 i 种物品还没被用过的状态所以只能取一次这就是 01 背包。如果你用二维数组观察这个过程会更清楚。完全背包的二维转移其实是dp[i][j] max(dp[i-1][j], dp[i][j - v[i]] w[i])注意第二项是 dp[i][j-v[i]]不是 dp[i-1][j-v[i]]。这个小小的下标差异就是正序循环的由来。在一维滚动数组里正序循环跑完第 i 轮时dp[j-v[i]] 已经是第 i 轮更新过的值等价于 dp[i][j-v[i]]。2.2 从二维视角看正序循环的合理性我见过很多人把完全背包的正序循环当成一个死记硬背的结论这样记很容易忘而且换个场景就不会用了。所以这里花一点时间把二维转移推导一下。设 f[i][j] 表示前 i 种物品、容量为 j 的最大价值。因为第 i 种物品可以拿任意多次所以要么不拿第 i 种物品要么先拿一个第 i 种物品剩下的容量 j - v[i] 继续由前 i 种物品来填注意是前 i 种不是前 i-1 种。写成方程就是f[i][j] max(f[i-1][j], f[i][j - v[i]] w[i])这个方程和 01 背包的 f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i]) 一比区别就非常明显了。01 背包里第二项用的是 f[i-1]因为它不允许重复取完全背包里第二项用的是 f[i]相当于“我还能继续取自己”。所以在一维数组里正序循环就是在模拟“f[i]”的滚动更新逆序循环模拟的是“f[i-1]”。这个理解太重要了它不只是为了写完全背包后面你学多重背包的单调队列优化、学完全背包求方案数、学混合背包全都用得着。2.3 完全背包的常见拓展完全背包最经典的应用是零钱兑换类问题比如 LeetCode 322 和 518。322 是求最少硬币数518 是求组合数。这两道题虽然披着“硬币”的壳本质就是完全背包。有个很容易搞混的点求组合数和求排列数时循环的顺序不一样。求组合数不考虑顺序一般用“先遍历物品、再遍历容量”的正序循环求排列数需要考虑顺序要“先遍历容量、再遍历物品”。当年我在 518 上踩过坑一开始写成了先容量后物品结果答案多出来一堆重复排列。这个点可以单独写一篇文章但核心思路就是谁在外层循环谁就控制了“决策的先后顺序”。完全背包另一个常用技巧是“最小化 / 最大化”的时候初始化细节。求最小值时 dp 数组要初始化成一个大数dp[0]0求最大值时初始化成 0 或者负无穷具体看题目要求。这些琐碎的初始化问题反而是背包题里最容易被判错的点。3. 二进制优化把多重背包变成 0-1 背包3.1 拆分的数学依据多重背包朴素做法慢就慢在内层枚举数量 k最坏要枚举到 c[i]。如果我们能把这 c[i] 个物品拆成几坨每一坨都当成一个独立的 01 背包物品那就完全可以用 01 背包的框架来做。问题是怎么拆才能保证“任意 0 到 c[i] 个”都能由拆出来的几坨组合出来答案是拆成 1、2、4、8……这样 2 的幂次直到剩下的数不能再拆为止。比如 c[i] 13就拆成 1、2、4、6。注意最后一项是 6不是 8因为 1248 15 已经超过 13 了。这四坨可以组合出 0 到 13 的任意整数吗可以。1、2、4 能组合出 0 到 7加上 6 就能组合出 6 到 13两者取并集正好覆盖 0 到 13。数学上更好看的写法是设 c[i] 的二进制表示找到最大的 k使得 1 2 4 ... 2^(k-1) c[i]剩下 c[i] - (2^k - 1) 作为最后一个数。拆完之后每种物品被拆成了 O(log c[i]) 个新物品总物品数从 n 变成约 n * log(max(c[i]))然后直接跑 01 背包复杂度变成 O(V * n * log(maxC))。对于 V10^5、n100、maxC10^5 这种数据已经能跑过了。3.2 代码实现细节二进制拆分的代码有一个非常容易翻车的点很多人直接用 while (k c[i]) 去拆拆完发现剩余的部分没有处理导致 c[i] 不能被完全覆盖。正确的做法是每拆一个 1、2、4……就从 c[i] 里减掉同时把 k 左移一位直到 c[i] - k 0最后把剩余的 c[i] 作为最后一个新物品。我习惯把每种物品拆出来的新物品放到两个 vector 里然后统一跑 01 背包。代码参考如下vectorint nv, nw; for (int i 1; i n; i) { int cnt c[i]; for (int k 1; k cnt; k 1) { nv.push_back(k * v[i]); nw.push_back(k * w[i]); cnt - k; } if (cnt 0) { nv.push_back(cnt * v[i]); nw.push_back(cnt * w[i]); } } // 跑 01 背包 for (int i 0; i (int)nv.size(); i) { for (int j V; j nv[i]; j--) { dp[j] max(dp[j], dp[j - nv[i]] nw[i]); } }这里 k 1 是把 k 翻倍循环条件是 k cnt注意是更新后的 cnt。我见过有人写成 for (int k 1; k c[i]; k * 2)然后忘记改 c[i]结果拆出来的新物品数量完全不对——虽然样例能过但数据一大就 WA。这就是为什么我一直建议写二进制拆分的时候别动原来的数组用局部变量 cnt 代替。3.3 二进制优化的边界与坑第一个坑是拆分后物品数量可能超过 int 范围虽然一般不会但 n 达到 100、c[i] 达到 10^9 时新物品数量大约是 n * 30也就是 3000 个再乘容量 V10^5也有 3 亿次运算勉强能过但很悬。这时候就得考虑单调队列优化了。第二个坑是“二进制拆分后还能不能直接当 01 背包跑”。答案是可以但前提是 01 背包的容量循环要逆序。如果你写成正序就退化成完全背包的效果每种新物品都能被取多次答案会偏大。第三个坑是体积为 0 的情况。如果某个物品体积 v[i] 0那么不管数量限制是多少它都可以被无限拿而 01 背包的逆序遍历这种体积 0 的物品时dp[j] max(dp[j], dp[j] w[i])永远取不到最大值会死循环或者结果不对。这种边界题虽然少见但我确确实实被坑过一次。遇到 v[i] 0 的题目要先特判如果 w[i] 0不拿如果 w[i] 0答案直接加上 c[i] * w[i]因为体积为 0 且价值为正当然是全拿。4. 单调队列优化O(NV) 的终局解法4.1 为什么朴素写法会产生 O(NV·C) 的复杂度如果数据范围再大一点比如 V 10^5、c[i] 10^5、n 100二进制优化的 log 因子虽然能接受但 3 亿次操作在竞赛里还是有点悬。能不能把多重背包的复杂度压到和完全背包一个级别先看一维度朴素转移长什么样dp[j] max(dp[j], dp[j - kv[i]] kw[i])k 从 0 到 min(c[i], j/v[i])这里的 k 每次加 1就是一个线性扫描。如果我们能把这个扫描优化掉复杂度就能降下来。观察转移方程dp[j - kv[i]] kw[i] 这个式子可以重写成dp[j - kv[i]] kw[i] (dp[j - kv[i]] - (j - kv[i])/v[i] * w[i]) j/v[i] * w[i]这里假设 j 能被 v[i] 整除或者更准确地说我们要按 j 除以 v[i] 的余数分组因为它们之间互不影响。4.2 按余数分组与滑动窗口把所有容量 j 按照 j mod v[i] 的余数 r 分组每组内部的 j 都可以写成 r t * v[i] 的形式。在同一组内转移方程就变成了dp[r t*v[i]] max_{k}( dp[r (t-k)v[i]] kw[i] )令 s t - k那 k 的取值范围是 0 到 min(c[i], t)所以 s 的取值范围就是 max(0, t - c[i]) 到 t。上面的式子等价于dp[r tv[i]] t * w[i] max_{s}( dp[r sv[i]] - s*w[i] )其中 s 的范围是 [max(0, t-c[i]), t]。这一步非常关键括号里的值 dp[r sv[i]] - sw[i] 只跟 s 有关跟 t 没有直接关系。也就是说同一个余数分组内我们维护一个关于 s 的滑动窗口最大值窗口长度是 c[i]1。每增大一个 t窗口右端加一个新值左端把超过 c[i] 个的旧值移出去。这正是单调队列的经典应用场景。用单调队列维护这个窗口最大值每组内每个 t 只进出队列一次整题复杂度就从 O(NV·C) 降到了 O(NV)。这才是多重背包的终极解法。4.3 代码实现与关键细节我自己常用的单调队列写法是先复制一份上一轮的 dp 到 g 数组然后在 g 的基础上更新。为什么要复制因为更新过程中 dp[j] 会被覆盖而单调队列里可能还存着旧值如果直接用 dp 本身窗口内的值会被当前轮污染。复制一份虽然空间翻倍但思路清晰很多。模板如下for (int i 1; i n; i) { memcpy(g, dp, sizeof(g)); for (int r 0; r v[i]; r) { // 按余数分组 int q[MAXV], head 0, tail -1; for (int t 0; r t * v[i] V; t) { int idx r t * v[i]; // 维护单调递减value 越大越优 int val g[idx] - t * w[i]; while (head tail g[q[tail]] - (q[tail] - r) / v[i] * w[i] val) tail--; q[tail] idx; // 移除窗口外的元素数量超过 c[i] while (head tail (idx - q[head]) / v[i] c[i]) head; // 用队首更新 dp dp[idx] g[q[head]] (idx - q[head]) / v[i] * w[i]; } } }有几个细节值得单独讲。队首弹出条件 (idx - q[head]) / v[i] c[i]含义是当前物品取的数量超过了限制。这里用的是除法而不是乘法因为 idx 和 q[head] 都是同余的差值一定是 v[i] 的整数倍除法结果刚好就是数量差。另一个易错点是 val 的计算。有人会写成 g[idx] - (idx - r)/v[i] * w[i]其实和 g[idx] - t*w[i] 一个意思因为 t (idx-r)/v[i]。我写上面代码时特意用了 t 来算可读性更好。单调队列优化的代码比二进制优化难写很多所以我通常先写暴力版或二进制版对拍确认答案正确之后再换单调队列版去跑大数据。不然一上来写个单调队列WA 了都不知道是思路错还是实现错。5. 几种写法的横向对比与选择策略5.1 复杂度与适用场景我把这几种写法拉了一个表方便大家直接对照这也是我平时决定用哪种方法的依据。写法时间复杂度空间复杂度代码难度适用场景朴素三重循环O(n * V * maxC)O(V)极低小数据、暴力对拍二进制优化O(V * n * log maxC)O(V n log maxC)较低大多数量级在 10^4~10^6 的题单调队列优化O(n * V)O(V)较高大数据、竞赛时间紧从这张表能看出三种写法的适用场景完全不一样。如果你参加算法竞赛我建议至少熟练掌握前两种第三种能写出来最好写不出来也可以靠第二种苟过很多题。但如果你是想深入理解 DP 的本质单调队列这个思路非常值得学因为它把“滑动窗口最大值”这个工具和背包问题结合到了一起以后做其他 DP 优化题也会用到。5.2 实际刷题中的选择经验我的个人经验是拿到题目先看数据范围不要一上来就背模板。如果 V * sum(c[i]) 小于 10^7 左右直接朴素三重循环稳。如果 V 在 10^5 左右、c[i] 在 10^3~10^5二进制优化基本能过代码短容错高。如果 V 在 10^6 左右或者时间限制非常紧上单调队列。另外注意一个细节二进制优化是要预处理新物品数组其实也是要额外空间的。如果题目空间卡得很死V 又到 10^6建议直接用单调队列因为空间只有 O(V)而二进制优化可能要把新物品数组开到 n log maxC 量级虽然通常才几千但万一 n 也大就要小心了。5.3 我踩过的坑与建议最后分享几个真实踩过的坑都是代码层面的细节。第一个是初始化。多重背包求最大值的时候dp 数组初始化为 0 通常是正确的因为容量不够的时候可以不装任何东西。但如果涉及“恰好装满”的问题dp[0]0其他 dp 要初始化成负无穷。我用朴素写法对拍单调队列优化的时候就发生过因为初始化不同导致两版结果不一致的情况后来统一改成负无穷才通过。第二个是数组长度。单调队列的 q 数组要开到 V1很多人图省事开个 v[i]1然后队列下标就越界了。其实 q 存的是一组内的容量值也就是同余分组里的索引最多出现 V/v[i] 个但保险起见直接开 MAXV。第三个是 memcpy 的时机。必须在每轮物品开始前把 dp 复制到 g而不是在每组循环前复制。因为每组更新用的都是上一轮完整状态如果你在每组更新前才复制那下一组可能会用到被上一组更新过的 dp状态就串了。这个问题特别隐蔽我第一次写的时候就踩了调了半个多小时才反应过来。第四个也是我最想说的一点如果一道题要求“方案数”而不是“最大价值”多重背包的二进制优化会失效。因为二进制拆分后的物品在方案数问题里会被当成不同的物品导致计数重复。比如 HDU 2844 这种题可以二分答案判可行性但你要是直接套方案数 DP 就出事了。问我怎么知道的我当年就错在这。现在的我写多重背包基本都是先判断数据范围然后要么二进制优化要么单调队列很少用朴素三层循环。但每次写复杂 DP 的时候仍然会花一分钟写个暴力版做对拍。这个习惯帮我省了太多查错的时间也让我对每道题的状态定义保持清醒。你如果刚开始学别急着追求最优解把朴素写法吃透把完全背包的正序循环想明白后面的一切就会顺很多。 
背包问题几乎是每个学动态规划的人绕不开的一道坎。01背包、完全背包、多重背包难度层层加码很多人都是靠死记模板混过去的。我自己刚开始学多重背包的时候也干过蠢事因为完全背包用正序循环就把多重背包也直接正序刷了一遍结果答案大得离谱当时还以为是数据错了。后来才明白多重背包最难的地方从来不是状态转移方程本身而是如何在数量限制的约束下把复杂度压下去。这篇文章就把我自己用过的几种多重背包写法从头到尾捋一遍顺便把完全背包为什么能正序循环这件事说透。先交代一下场景设定。题目一般长这样有 n 种物品每种物品有体积 v[i]、价值 w[i]、数量上限 c[i]背包容量为 V求能装下的最大总价值。多重背包和完全背包最大的区别就在这个 c[i]——完全背包里每种物品想拿多少个拿多少个多重背包拿了超过 c[i] 个就算非法。这个限制看着不起眼却直接把时间复杂度从 O(NV) 抬到了 O(NV·C)逼得我们不得不想优化手段。1. 从朴素做法开始多重背包的暴力美学1.1 问题定义与状态设计不管是哪种背包状态设计都是老一套dp[j] 表示容量为 j 的背包能获得的最大价值。数组开一维就够了滚动更新的时候注意顺序问题就行。对于多重背包最直接的想法就是把每种物品拆成“拿 0 个、拿 1 个、拿 2 个……拿 c[i] 个”这 c[i]1 种选择然后暴力枚举。这里有个细节容易忽略我们枚举的是“第 i 种物品拿几个”而不是“是否拿第 i 种物品”。一旦你把它当成 01 背包来做就会发现状态定义变了味道。所以我个人建议新手先写二维的朴素版本把状态转移看清楚再压缩成一维。二维的写法是这样的dp[i][j] 表示前 i 种物品、容量为 j 时的最大价值。转移的时候枚举第 i 种物品拿 k 个k 的范围是 0 到 c[i]同时要满足 k * v[i] j。转移方程写出来非常规整dp[i][j] max(dp[i-1][j], dp[i-1][j - kv[i]] kw[i])其中 1 k c[i] 且 k*v[i] j这个方程其实是在说我不拿第 i 种物品直接从 i-1 转移或者我拿 k 个第 i 种物品那前面的 i-1 种物品只能占 j - k*v[i] 的容量。看起来很和谐但一旦写成一维滚动数组坑就来了——如果你像 01 背包那样逆序枚举 j再在内层枚举 k那没问题如果你正序枚举 j就会导致同一轮循环里重复使用第 i 种物品相当于突破了 c[i] 的限制。这一点下文还会反复强调。1.2 三重循环写法与复杂度一维的朴素写法在竞赛里很常见代码长这样// c[i]: 数量, v[i]: 体积, w[i]: 价值, V: 背包容量 for (int i 1; i n; i) { for (int j V; j 0; j--) { // 容量逆序参照01背包 for (int k 1; k c[i] k * v[i] j; k) { dp[j] max(dp[j], dp[j - k * v[i]] k * w[i]); } } }为什么这里的 j 要逆序因为一维数组里 dp[j-kv[i]] 如果在本轮被更新过就代表第 i 种物品已经被取过一次那 k 再往上加就相当于多次取用同一种物品。逆序枚举可以保证本轮更新 dp[j] 用到的 dp[j-kv[i]] 还是上一轮 i-1 的状态这样第 i 种物品在每一轮里最多只被“引入”一次。我当年写这个三层循环的时候经常把 k 的起点写成 0那样其实也不需要因为 dp[j] 本身就是不取第 i 种物品的情况k0 是多余的。复杂度也很直观外层 n 种物品中层容量 V内层最多 c[i] 个数量。整体是 O(n * V * max(c[i]))如果每个 c[i] 都是 10^5 量级那直接爆炸。所以朴素写法只适合小数据比如 V 1000、c[i] 100 之类的题目。1.3 什么时候我需要用朴素写法有些朋友会觉得朴素写法这么土还不如直接学二进制优化。但我的经验是朴素写法至少有两个不可替代的价值。第一它是调试的基准。你写二进制优化、写单调队列优化的时候答案对不对拿什么做对照拿朴素写法做暴力对拍是最稳的。我自己写这种复杂 DP 的时候一定会保留一份暴力版本用来随机数据对拍。没有它优化版写错了你都不知道错在哪。第二有些题目的数据范围很小根本不需要优化。比如 n 20、V 100、c[i] 10这种数据你上单调队列反而浪费时间朴素写法几毫秒就跑完了。做题的第一步永远是看数据范围而不是背模板。很多新手一上来就套最难的写法不仅代码长还容易出 bug最后得不偿失。2. 完全背包思路正序循环背后的玄机2.1 为什么完全背包要正序遍历完全背包的多重背包最大的区别是每种物品的数量不限。所以它的状态转移方程比多重背包更简单直接用 01 背包改一个符号就行。我直接给结论01 背包的容量循环是逆序完全背包的容量循环是正序。就这一个差别代码从 01 背包改成完全背包只需要把 for (int j V; j v[i]; j--) 改成 for (int j v[i]; j V; j)。道理也不复杂。正序循环意味着 dp[j - v[i]] 在本轮已经被更新过了。这个 dp[j - v[i]] 可能是已经取了一次第 i 种物品之后的状态于是你再取一次就相当于允许同一件物品被取无限次。逆序循环刚好相反它保证 dp[j - v[i]] 还是上一轮的状态也就是第 i 种物品还没被用过的状态所以只能取一次这就是 01 背包。如果你用二维数组观察这个过程会更清楚。完全背包的二维转移其实是dp[i][j] max(dp[i-1][j], dp[i][j - v[i]] w[i])注意第二项是 dp[i][j-v[i]]不是 dp[i-1][j-v[i]]。这个小小的下标差异就是正序循环的由来。在一维滚动数组里正序循环跑完第 i 轮时dp[j-v[i]] 已经是第 i 轮更新过的值等价于 dp[i][j-v[i]]。2.2 从二维视角看正序循环的合理性我见过很多人把完全背包的正序循环当成一个死记硬背的结论这样记很容易忘而且换个场景就不会用了。所以这里花一点时间把二维转移推导一下。设 f[i][j] 表示前 i 种物品、容量为 j 的最大价值。因为第 i 种物品可以拿任意多次所以要么不拿第 i 种物品要么先拿一个第 i 种物品剩下的容量 j - v[i] 继续由前 i 种物品来填注意是前 i 种不是前 i-1 种。写成方程就是f[i][j] max(f[i-1][j], f[i][j - v[i]] w[i])这个方程和 01 背包的 f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i]) 一比区别就非常明显了。01 背包里第二项用的是 f[i-1]因为它不允许重复取完全背包里第二项用的是 f[i]相当于“我还能继续取自己”。所以在一维数组里正序循环就是在模拟“f[i]”的滚动更新逆序循环模拟的是“f[i-1]”。这个理解太重要了它不只是为了写完全背包后面你学多重背包的单调队列优化、学完全背包求方案数、学混合背包全都用得着。2.3 完全背包的常见拓展完全背包最经典的应用是零钱兑换类问题比如 LeetCode 322 和 518。322 是求最少硬币数518 是求组合数。这两道题虽然披着“硬币”的壳本质就是完全背包。有个很容易搞混的点求组合数和求排列数时循环的顺序不一样。求组合数不考虑顺序一般用“先遍历物品、再遍历容量”的正序循环求排列数需要考虑顺序要“先遍历容量、再遍历物品”。当年我在 518 上踩过坑一开始写成了先容量后物品结果答案多出来一堆重复排列。这个点可以单独写一篇文章但核心思路就是谁在外层循环谁就控制了“决策的先后顺序”。完全背包另一个常用技巧是“最小化 / 最大化”的时候初始化细节。求最小值时 dp 数组要初始化成一个大数dp[0]0求最大值时初始化成 0 或者负无穷具体看题目要求。这些琐碎的初始化问题反而是背包题里最容易被判错的点。3. 二进制优化把多重背包变成 0-1 背包3.1 拆分的数学依据多重背包朴素做法慢就慢在内层枚举数量 k最坏要枚举到 c[i]。如果我们能把这 c[i] 个物品拆成几坨每一坨都当成一个独立的 01 背包物品那就完全可以用 01 背包的框架来做。问题是怎么拆才能保证“任意 0 到 c[i] 个”都能由拆出来的几坨组合出来答案是拆成 1、2、4、8……这样 2 的幂次直到剩下的数不能再拆为止。比如 c[i] 13就拆成 1、2、4、6。注意最后一项是 6不是 8因为 1248 15 已经超过 13 了。这四坨可以组合出 0 到 13 的任意整数吗可以。1、2、4 能组合出 0 到 7加上 6 就能组合出 6 到 13两者取并集正好覆盖 0 到 13。数学上更好看的写法是设 c[i] 的二进制表示找到最大的 k使得 1 2 4 ... 2^(k-1) c[i]剩下 c[i] - (2^k - 1) 作为最后一个数。拆完之后每种物品被拆成了 O(log c[i]) 个新物品总物品数从 n 变成约 n * log(max(c[i]))然后直接跑 01 背包复杂度变成 O(V * n * log(maxC))。对于 V10^5、n100、maxC10^5 这种数据已经能跑过了。3.2 代码实现细节二进制拆分的代码有一个非常容易翻车的点很多人直接用 while (k c[i]) 去拆拆完发现剩余的部分没有处理导致 c[i] 不能被完全覆盖。正确的做法是每拆一个 1、2、4……就从 c[i] 里减掉同时把 k 左移一位直到 c[i] - k 0最后把剩余的 c[i] 作为最后一个新物品。我习惯把每种物品拆出来的新物品放到两个 vector 里然后统一跑 01 背包。代码参考如下vectorint nv, nw; for (int i 1; i n; i) { int cnt c[i]; for (int k 1; k cnt; k 1) { nv.push_back(k * v[i]); nw.push_back(k * w[i]); cnt - k; } if (cnt 0) { nv.push_back(cnt * v[i]); nw.push_back(cnt * w[i]); } } // 跑 01 背包 for (int i 0; i (int)nv.size(); i) { for (int j V; j nv[i]; j--) { dp[j] max(dp[j], dp[j - nv[i]] nw[i]); } }这里 k 1 是把 k 翻倍循环条件是 k cnt注意是更新后的 cnt。我见过有人写成 for (int k 1; k c[i]; k * 2)然后忘记改 c[i]结果拆出来的新物品数量完全不对——虽然样例能过但数据一大就 WA。这就是为什么我一直建议写二进制拆分的时候别动原来的数组用局部变量 cnt 代替。3.3 二进制优化的边界与坑第一个坑是拆分后物品数量可能超过 int 范围虽然一般不会但 n 达到 100、c[i] 达到 10^9 时新物品数量大约是 n * 30也就是 3000 个再乘容量 V10^5也有 3 亿次运算勉强能过但很悬。这时候就得考虑单调队列优化了。第二个坑是“二进制拆分后还能不能直接当 01 背包跑”。答案是可以但前提是 01 背包的容量循环要逆序。如果你写成正序就退化成完全背包的效果每种新物品都能被取多次答案会偏大。第三个坑是体积为 0 的情况。如果某个物品体积 v[i] 0那么不管数量限制是多少它都可以被无限拿而 01 背包的逆序遍历这种体积 0 的物品时dp[j] max(dp[j], dp[j] w[i])永远取不到最大值会死循环或者结果不对。这种边界题虽然少见但我确确实实被坑过一次。遇到 v[i] 0 的题目要先特判如果 w[i] 0不拿如果 w[i] 0答案直接加上 c[i] * w[i]因为体积为 0 且价值为正当然是全拿。4. 单调队列优化O(NV) 的终局解法4.1 为什么朴素写法会产生 O(NV·C) 的复杂度如果数据范围再大一点比如 V 10^5、c[i] 10^5、n 100二进制优化的 log 因子虽然能接受但 3 亿次操作在竞赛里还是有点悬。能不能把多重背包的复杂度压到和完全背包一个级别先看一维度朴素转移长什么样dp[j] max(dp[j], dp[j - kv[i]] kw[i])k 从 0 到 min(c[i], j/v[i])这里的 k 每次加 1就是一个线性扫描。如果我们能把这个扫描优化掉复杂度就能降下来。观察转移方程dp[j - kv[i]] kw[i] 这个式子可以重写成dp[j - kv[i]] kw[i] (dp[j - kv[i]] - (j - kv[i])/v[i] * w[i]) j/v[i] * w[i]这里假设 j 能被 v[i] 整除或者更准确地说我们要按 j 除以 v[i] 的余数分组因为它们之间互不影响。4.2 按余数分组与滑动窗口把所有容量 j 按照 j mod v[i] 的余数 r 分组每组内部的 j 都可以写成 r t * v[i] 的形式。在同一组内转移方程就变成了dp[r t*v[i]] max_{k}( dp[r (t-k)v[i]] kw[i] )令 s t - k那 k 的取值范围是 0 到 min(c[i], t)所以 s 的取值范围就是 max(0, t - c[i]) 到 t。上面的式子等价于dp[r tv[i]] t * w[i] max_{s}( dp[r sv[i]] - s*w[i] )其中 s 的范围是 [max(0, t-c[i]), t]。这一步非常关键括号里的值 dp[r sv[i]] - sw[i] 只跟 s 有关跟 t 没有直接关系。也就是说同一个余数分组内我们维护一个关于 s 的滑动窗口最大值窗口长度是 c[i]1。每增大一个 t窗口右端加一个新值左端把超过 c[i] 个的旧值移出去。这正是单调队列的经典应用场景。用单调队列维护这个窗口最大值每组内每个 t 只进出队列一次整题复杂度就从 O(NV·C) 降到了 O(NV)。这才是多重背包的终极解法。4.3 代码实现与关键细节我自己常用的单调队列写法是先复制一份上一轮的 dp 到 g 数组然后在 g 的基础上更新。为什么要复制因为更新过程中 dp[j] 会被覆盖而单调队列里可能还存着旧值如果直接用 dp 本身窗口内的值会被当前轮污染。复制一份虽然空间翻倍但思路清晰很多。模板如下for (int i 1; i n; i) { memcpy(g, dp, sizeof(g)); for (int r 0; r v[i]; r) { // 按余数分组 int q[MAXV], head 0, tail -1; for (int t 0; r t * v[i] V; t) { int idx r t * v[i]; // 维护单调递减value 越大越优 int val g[idx] - t * w[i]; while (head tail g[q[tail]] - (q[tail] - r) / v[i] * w[i] val) tail--; q[tail] idx; // 移除窗口外的元素数量超过 c[i] while (head tail (idx - q[head]) / v[i] c[i]) head; // 用队首更新 dp dp[idx] g[q[head]] (idx - q[head]) / v[i] * w[i]; } } }有几个细节值得单独讲。队首弹出条件 (idx - q[head]) / v[i] c[i]含义是当前物品取的数量超过了限制。这里用的是除法而不是乘法因为 idx 和 q[head] 都是同余的差值一定是 v[i] 的整数倍除法结果刚好就是数量差。另一个易错点是 val 的计算。有人会写成 g[idx] - (idx - r)/v[i] * w[i]其实和 g[idx] - t*w[i] 一个意思因为 t (idx-r)/v[i]。我写上面代码时特意用了 t 来算可读性更好。单调队列优化的代码比二进制优化难写很多所以我通常先写暴力版或二进制版对拍确认答案正确之后再换单调队列版去跑大数据。不然一上来写个单调队列WA 了都不知道是思路错还是实现错。5. 几种写法的横向对比与选择策略5.1 复杂度与适用场景我把这几种写法拉了一个表方便大家直接对照这也是我平时决定用哪种方法的依据。写法时间复杂度空间复杂度代码难度适用场景朴素三重循环O(n * V * maxC)O(V)极低小数据、暴力对拍二进制优化O(V * n * log maxC)O(V n log maxC)较低大多数量级在 10^4~10^6 的题单调队列优化O(n * V)O(V)较高大数据、竞赛时间紧从这张表能看出三种写法的适用场景完全不一样。如果你参加算法竞赛我建议至少熟练掌握前两种第三种能写出来最好写不出来也可以靠第二种苟过很多题。但如果你是想深入理解 DP 的本质单调队列这个思路非常值得学因为它把“滑动窗口最大值”这个工具和背包问题结合到了一起以后做其他 DP 优化题也会用到。5.2 实际刷题中的选择经验我的个人经验是拿到题目先看数据范围不要一上来就背模板。如果 V * sum(c[i]) 小于 10^7 左右直接朴素三重循环稳。如果 V 在 10^5 左右、c[i] 在 10^3~10^5二进制优化基本能过代码短容错高。如果 V 在 10^6 左右或者时间限制非常紧上单调队列。另外注意一个细节二进制优化是要预处理新物品数组其实也是要额外空间的。如果题目空间卡得很死V 又到 10^6建议直接用单调队列因为空间只有 O(V)而二进制优化可能要把新物品数组开到 n log maxC 量级虽然通常才几千但万一 n 也大就要小心了。5.3 我踩过的坑与建议最后分享几个真实踩过的坑都是代码层面的细节。第一个是初始化。多重背包求最大值的时候dp 数组初始化为 0 通常是正确的因为容量不够的时候可以不装任何东西。但如果涉及“恰好装满”的问题dp[0]0其他 dp 要初始化成负无穷。我用朴素写法对拍单调队列优化的时候就发生过因为初始化不同导致两版结果不一致的情况后来统一改成负无穷才通过。第二个是数组长度。单调队列的 q 数组要开到 V1很多人图省事开个 v[i]1然后队列下标就越界了。其实 q 存的是一组内的容量值也就是同余分组里的索引最多出现 V/v[i] 个但保险起见直接开 MAXV。第三个是 memcpy 的时机。必须在每轮物品开始前把 dp 复制到 g而不是在每组循环前复制。因为每组更新用的都是上一轮完整状态如果你在每组更新前才复制那下一组可能会用到被上一组更新过的 dp状态就串了。这个问题特别隐蔽我第一次写的时候就踩了调了半个多小时才反应过来。第四个也是我最想说的一点如果一道题要求“方案数”而不是“最大价值”多重背包的二进制优化会失效。因为二进制拆分后的物品在方案数问题里会被当成不同的物品导致计数重复。比如 HDU 2844 这种题可以二分答案判可行性但你要是直接套方案数 DP 就出事了。问我怎么知道的我当年就错在这。现在的我写多重背包基本都是先判断数据范围然后要么二进制优化要么单调队列很少用朴素三层循环。但每次写复杂 DP 的时候仍然会花一分钟写个暴力版做对拍。这个习惯帮我省了太多查错的时间也让我对每道题的状态定义保持清醒。你如果刚开始学别急着追求最优解把朴素写法吃透把完全背包的正序循环想明白后面的一切就会顺很多。