尧图网站开发 
搞算法的人背包问题基本都躲不过去。刷题刷到动态规划十个里有七个是从背包入门的而在背包家族里完全背包和多重背包又是最容易让人绕晕的两个。明明都是“往背包里装东西”但一个无限拿、一个限量拿写法却完全不是一个路子。更麻烦的是多重背包本身就有好几种实现方式朴素三层循环、二进制拆分、单调队列优化每一层都能把复杂度再往下压一档。这篇文章就是一份实战笔记不讲那些花架子推导直接说清楚完全背包为什么能用一维数组加正序循环解决以及多重背包从 $O(N \cdot V \cdot C)$ 一路优化到 $O(N \cdot V)$ 的完整思路和模板代码。无论你是刚刷 DP 的新手还是准备笔试面试、打算法竞赛的老手这份笔记都能让你少走不少弯路。1. 先聊完全背包为什么它比多重背包简单很多人上来就啃多重背包结果被二进制拆分和单调队列劝退。我建议你先从完全背包入手因为完全背包的思路一旦吃透多重背包的高效写法反而更好理解——它本质上就是“限定了拿取次数”的完全背包。1.1 共同的底座状态定义与转移方程所有背包问题的老祖宗都是 01 背包每个物品只有一件要么拿、要么不拿。状态也很固定用dp[i][j]表示“只从前 i 种物品中选总容量不超过 j 时能获得的最大价值”。01 背包的转移是dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])到了完全背包每种物品数量无限于是转移变成了在“不拿当前物品”和“再拿一件当前物品”之间取最大值dp[i][j] max(dp[i-1][j], dp[i][j - w[i]] v[i])注意第二项这里取的是dp[i][j - w[i]]而不是dp[i-1][j - w[i]]。这个差异就是完全背包所有优化的源头因为数量无限所以当你腾出w[i]的空间之后依然允许你继续拿当前物品。这样i这一维就变得不那么重要了可以用一维滚动数组直接原地更新。而多重背包呢每种物品有数量上限c[i]它正好夹在 01 背包和完全背包中间c[i] 1时就是 01 背包c[i]趋向无穷大时就是完全背包。所以多重背包的朴素转移天然需要一个“拿几件”的枚举维度dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]) // 0 k c[i]这就是后面所有做法的起点。1.2 省掉枚举数量的关键正序遍历几乎每个学背包的人都被一个口诀折磨过01 背包倒序完全背包正序。但很多人只会背口诀不知道正序到底为什么有效。我换个方式讲。假设你在一家奶茶店买同一种饮品单价 10 元你手里有 50 元。如果你只有一张 10 元券那你最多买一杯这是 01 背包如果你有无限张 10 元券你可以一杯一杯地加到 50 元买五杯这是完全背包。用一维数组实现的时候正序遍历j会让dp[j - w[i]]在本轮已经被更新过。也就是说在你决定“要不要再买一杯”之前当前物品已经被算进前面的结果里了。于是买完第一杯后还能买第二杯再买第三杯……自然就实现了“无限取”。如果倒序遍历dp[j - w[i]]还是上一轮的状态里面不可能包含当前物品那就退化成 01 背包了。这个区别用代码看更直接// 01背包容量 j 从大到小 for (int i 1; i n; i) for (int j V; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]); // 完全背包容量 j 从小到大 for (int i 1; i n; i) for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]);差别只在一个循环方向但语义完全不同。理解了这一点完全背包就只剩一套模板了。1.3 完全背包的一维模板完整的完全背包代码极其简洁几乎不需要多解释const int INF 1e9; vectorint dp(V 1, 0); // 不要求装满时初始化为0 for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }如果你需要判断“是否恰好装满”初始化和结果判断要改一下vectorint dp(V 1, -INF); dp[0] 0; for (int i 1; i n; i) { for (int j w[i]; j V; j) { if (dp[j - w[i]] ! -INF) dp[j] max(dp[j], dp[j - w[i]] v[i]); } } // 最终答案dp[V]如果是 -INF说明无法恰好装满一个细节很多模板会把if (dp[j - w[i]] ! -INF)省掉直接用dp[j - w[i]] v[i]参与比较。这在-INF很大的时候没有问题但严谨起见还是建议保留判断避免负数溢出产生假结果。完全背包搞定了接下来我们回到重头戏多重背包。2. 多重背包的朴素做法三重循环能解决什么问题先说结论朴素做法虽然慢但它准确、好写、不容易出错是处理小规模数据的保底方案。而且它也是理解二进制拆分、单调队列优化的基础。2.1 朴素转移在01背包上多套一层数量枚举多重背包要求每种物品最多拿c[i]件所以最直接的写法就是在 01 背包的框架里对每件物品枚举拿k件for (int i 1; i n; i) { for (int j V; j 0; j--) { for (int k 1; k c[i] k * w[i] j; k) { dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]); } } }这里有一个容易搞错的点内层枚举数量时容量j为什么还是倒序因为我们在枚举“拿 k 件当前物品”的时候所有转移必须基于“上一轮处理完前 i-1 种物品的状态”不能在同一轮里反复叠加当前物品否则k的枚举就失去了意义可能让同一种物品超过c[i]件。倒序遍历保证了dp[j - k * w[i]]还是旧状态。复杂度是 $O(N \cdot V \cdot C_{max})$其中 $C_{max}$ 是物品数量的最大值。当V和数据量都不大时这已经够用了。比如n 100、V 1000、c[i] 100三层循环也就一千万次本地跑是毫秒级。2.2 剪枝与边界什么时候可以提前收手朴素写法里藏着一些不起眼但很实用的优化我挑两个最常用的。第一如果当前物品的数量上限乘以体积已经超过了背包容量那它实际上可以当成完全背包处理没必要一个一个枚举数量直接用完全背包的正序循环即可。这个剪枝在竞赛里非常常见因为完全背包的复杂度比多重背包的朴素写法低一整个维度。第二枚举k的时候k的上限是min(c[i], j / w[i])。这个 min 一定要写对只写k c[i]会白白多算无效次数甚至可能越界访问dp数组只写k * w[i] j又容易在c[i]很大时超时。两个条件缺一不可。朴素写法虽然能应付小数据但一旦V到了 1e4、1e5 级别三层循环直接卡死。这时候就必须上更高级的写法了。3. 多重背包的三种高效写法多重背包的优化思路其实只有两条线一是把数量压缩成若干个独立的 01 物品也就是二进制拆分二是利用同余类和滑动窗口把数量枚举直接优化掉也就是单调队列优化。另外还有一条捷径就是前面说的“当数量足够多时直接转完全背包”。3.1 借完全背包的剪枝当数量多到可以当无限处理这个技巧很简单但很容易被忽略。如果某种物品的c[i] * w[i] V说明把它数量拉满之后体积已经超过背包总容量了。那不管你有多少件实际可用的件数最多也就是V / w[i]完全足够。换句话说它跟无限件没有区别直接用完全背包处理if (c[i] * w[i] V) { for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]); }这个剪枝不仅能减少循环次数还避免了你对超大c[i]做二进制拆分时多产生一堆物品。我见过有人把c[i] 1e9的物品硬生生拆了几十个物品出来其实一个剪枝就省了所有事。3.2 二进制拆分把数量压缩成logC个01背包这是多重背包最经典的写法。核心思想是任意一个数c都可以用若干个 2 的幂次加上一个余数来表示这些拆出来的数作为一组“新物品”去跑一遍 01 背包就能等价地得到“拿 0 到 c 件原物品”的所有组合。举个例子假设一个物品最多拿 13 件我们把 13 拆成1, 2, 4, 61、2、4 这三个数可以组合出 0~7 的所有数字再加上 6就能组合出 6~13 的所有数字合起来正好覆盖 0~13。注意这里最后剩下的 6 13 - 1 - 2 - 4它不是下一个 2 的幂次而是直接把剩余的件数打包。实现时通常这样写int cnt 0; for (int i 1; i n; i) { int c c[i], k 1; while (k c) { w_new[cnt] w[i] * k; v_new[cnt] v[i] * k; c - k; k 1; } if (c 0) { w_new[cnt] w[i] * c; v_new[cnt] v[i] * c; } } // 对拆出来的 cnt 个物品跑一遍 01 背包 for (int i 1; i cnt; i) { for (int j V; j w_new[i]; j--) { dp[j] max(dp[j], dp[j - w_new[i]] v_new[i]); } }为什么拆出来的数量能表示 0~C 的所有选择你可以这样理解把二进制的每一位都当作一个开关比如 1、2、4 可以让“这个物品拿几件”这个数字的二进制每一位独立变化而最后的余数c负责补齐高位保证 0 到原始数量上限都能被组合出来。这样一种有c[i]件物品被拆成了 $\lfloor \log_2 c[i] \rfloor 1$ 个新物品总复杂度变成 $O(N \cdot \log C \cdot V)$比朴素写法高出一个量级。绝大多数题目用这个做法就足够秒杀了。3.3 单调队列优化O(N*V)的终极做法二进制拆分已经很快了但遇到n 1000, V 1e5这种数据logC的因子依然可能成为瓶颈。这时候你需要的是单调队列优化把复杂度真正压到 $O(N \cdot V)$。核心观察是多重背包的转移式dp[j] max(dp[j - k * w[i]] k * v[i]) (0 k c[i])中所有能转移到dp[j]的状态它们的下标对w[i]取余都是同一个余数。也就是说按照余数a把容量分成w[i]组每组内部的状态可以单独处理。每一组内j从a开始每次加上w[i]转移就变成在一个长度有限的窗口里找最大值——这正是单调队列的典型场景。代码模板如下我会在关键位置注释for (int i 1; i n; i) { int w w[i], v v[i], c c[i]; if (c * w V) { // 数量足够多等价于完全背包 for (int j w; j V; j) dp[j] max(dp[j], dp[j - w] v); continue; } for (int a 0; a w; a) { dequeint q; // 保存下标队首是当前窗口最大值 for (int j a; j V; j w) { // 窗口范围[j - c*w, j - w] while (!q.empty() q.front() j - c * w) q.pop_front(); if (!q.empty()) { dp[j] max(dp[j], dp[q.front()] (j - q.front()) / w * v); } // 把当前状态 j 插入队列前先维护单调性 int val dp[j] - j / w * v; while (!q.empty() dp[q.back()] - q.back() / w * v val) q.pop_back(); q.push_back(j); } } }这里有一个容易懵的点为什么队里要维护dp[j] - j / w * v而不是直接维护dp[j]因为从j转移到j时价值变化量是(j - j) / w * v这里面j部分是固定的拆开之后变成dp[j] max(dp[j] - j / w * v) j / w * v所以单调队列只需要维护括号内那一部分的单调递减队列即可。这也是整个优化的精髓把跟j有关的部分和跟j有关的部分完全分离。这段代码理解起来需要一点时间但一旦写熟了它就是多重背包的万能模板。实测在V 1e5、n 1000、c[i] 1e5的数据下单调队列解法能在几十毫秒内跑完而朴素写法基本是天文数字。4. 实际选型与避坑记录背包问题看起来套路固定但实际写代码时坑非常多。我在本地反复测试、排错的过程中整理了一张对照表和几个高频问题这里分享出来。4.1 复杂度、代码量与适用场景对照写法时间复杂度空间复杂度代码量适用场景朴素三层循环$O(N \cdot V \cdot C)$$O(V)$极短小数据、刷题练习完全背包剪枝$O(N \cdot V)$$O(V)$极短某类物品数量足以忽略上限二进制拆分$O(N \cdot V \cdot \log C)$$O(V N \log C)$中等大多数竞赛题、笔试场景单调队列优化$O(N \cdot V)$$O(V)$较长大 V、大数量、卡常题目选型建议很简单先写出朴素版本确认思路再按数据范围一步步升级。如果你在笔试现场时间紧张V在 1e4 以内且n不大二进制拆分通常已经够了如果评测机特别毒、数据范围顶满或者你正在训练 DP 优化那就直接上单调队列。4.2 我在本地反复踩过的坑第一个坑是循环顺序。多重背包朴素写法的j循环必须是倒序但单调队列优化里的j分组循环又必须是正序。两者混着写很容易把自己绕晕我建议每个模板都单独存一份不要靠记忆临场推导。第二个坑是二进制拆分的余数处理。前面例子中 13 拆成1, 2, 4, 6最后的 6 是剩余数量但如果写成1, 2, 4, 8加起来是 15超过 13会导致取 14 件、15 件这种非法方案。所以拆分时一定要先减掉已拆的部分最后的c 0单独处理一下。第三个坑是初始化。不要求恰好装满时dp数组初始化为0即可要求恰好装满时必须把dp[1..V]初始化为一个极小的负值只让dp[0] 0。我见过不少人因为初始化问题在“恰好装满”和“不超过容量”两种题目之间来回 RE 和 WA。第四个坑是单调队列的窗口边界。窗口下限是j - c * w不是j - c * w - 1也不是j - (c 1) * w。我之前因为差一错误导致某些物品能多取一件或少取一件本地小数据测不出来提交就挂。后来写了个for (int k 0; k c k * w j; k)这种暴力验证程序对着随机大数据一顿对拍才把所有边界问题暴露出来。4.3 常见问题速查表症状可能原因解决办法完全背包答案偏小容量循环写成了倒序改成正序遍历01背包答案偏大容量循环写成了正序改成倒序遍历多重背包重复取超限朴素枚举时容量倒序写错或二进制拆分组数超了确保j倒序检查拆分代码二进制拆分答案偏小最后剩下的余数没有单独生成物品加if (c 0)分支单调队列 RE数组越界或队列弹出条件写错检查j - c * w的边界deque 判空恰好装满结果全是 -INF初始化未设置负无穷按要求执行“恰好装满”初始化5. 这两种背包的组合题型与扩展你以为把完全背包和多重背包单独吃透就结束了竞赛里往往不会只考单一种类而是把 01 背包、完全背包、多重背包混在一起考。5.1 混合背包有限和无限混在一起怎么处理混合背包的题目里每种物品可能是“只能拿 1 件”“可以拿无限件”“最多拿 c 件”三种情况中的一种。处理思路其实很直接遍历每一件物品时判断它的类型分别用 01 背包、完全背包、多重背包的转移方式去更新同一个dp数组。for (int i 1; i n; i) { if (type[i] 0) { // 01背包倒序 for (int j V; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]); } else if (type[i] 1) { // 完全背包正序 for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]); } else { // 多重背包先剪枝再二进制拆分或单调队列 } }这样写虽然有一点点冗余但逻辑最清晰不容易在类型转换时出错。实际比赛中这也是大部分人采用的写法。5.2 状态定义的变化恰好装满与最大值很多题目看起来是背包实际上考的是状态定义的变化而不只是转移方程。比如“求方案总数”dp[j]就不表示最大价值而是“容量为 j 时有多少种选法”转移变成dp[j] dp[j - w[i]]再比如“求最大最小值混合”可能要把dp数组拆成两维来记录“最大价值”和“最少件数”。这些变体都是在完全背包和多重背包的骨架上做文章骨架熟了变体就只是套模板的问题。5.3 实战题单每个题型该练哪道题我整理了一个亲测有效的题单按难度递增排列练完基本能把这两种背包盘活题型推荐题目考点完全背包入门洛谷 P1616 疯狂的采药正序遍历、一维滚动完全背包方案数洛谷 P1832 AB Problem再升级方案数累加多重背包朴素洛谷 P1776 宝物筛选二进制拆分练习多重背包恰好装满HDU 2844 Coins判可行、二进制拆分单调队列优化POJ 1742 Coins / 洛谷 P3423卡常、滑动窗口优化做题顺序我建议这样先手写一遍完全背包再把朴素多重背包的代码跑通然后用二进制拆分重写一遍等这三步都顺畅了再啃单调队列。千万别一上来就背单调队列模板否则连出错都不知道错在哪一步。我自己就是在反复对拍中才慢慢建立起“背包直觉”的。有些东西光看别人代码是学不会的必须自己动手改一改、跑一跑、挂一挂才能把模板变成肌肉记忆。如果你现在刚开始接触这两种背包我的建议很直接先把完全背包的正序循环、01 背包的倒序循环、二进制拆分这三个基本功练到闭眼能写再去碰单调队列。等你真的在题里遇到V 1e5这种卡常数级别的数据再回头研究队列优化也不迟——那个时候你已经知道为什么需要它了理解起来会快得多。 
搞算法的人背包问题基本都躲不过去。刷题刷到动态规划十个里有七个是从背包入门的而在背包家族里完全背包和多重背包又是最容易让人绕晕的两个。明明都是“往背包里装东西”但一个无限拿、一个限量拿写法却完全不是一个路子。更麻烦的是多重背包本身就有好几种实现方式朴素三层循环、二进制拆分、单调队列优化每一层都能把复杂度再往下压一档。这篇文章就是一份实战笔记不讲那些花架子推导直接说清楚完全背包为什么能用一维数组加正序循环解决以及多重背包从 $O(N \cdot V \cdot C)$ 一路优化到 $O(N \cdot V)$ 的完整思路和模板代码。无论你是刚刷 DP 的新手还是准备笔试面试、打算法竞赛的老手这份笔记都能让你少走不少弯路。1. 先聊完全背包为什么它比多重背包简单很多人上来就啃多重背包结果被二进制拆分和单调队列劝退。我建议你先从完全背包入手因为完全背包的思路一旦吃透多重背包的高效写法反而更好理解——它本质上就是“限定了拿取次数”的完全背包。1.1 共同的底座状态定义与转移方程所有背包问题的老祖宗都是 01 背包每个物品只有一件要么拿、要么不拿。状态也很固定用dp[i][j]表示“只从前 i 种物品中选总容量不超过 j 时能获得的最大价值”。01 背包的转移是dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])到了完全背包每种物品数量无限于是转移变成了在“不拿当前物品”和“再拿一件当前物品”之间取最大值dp[i][j] max(dp[i-1][j], dp[i][j - w[i]] v[i])注意第二项这里取的是dp[i][j - w[i]]而不是dp[i-1][j - w[i]]。这个差异就是完全背包所有优化的源头因为数量无限所以当你腾出w[i]的空间之后依然允许你继续拿当前物品。这样i这一维就变得不那么重要了可以用一维滚动数组直接原地更新。而多重背包呢每种物品有数量上限c[i]它正好夹在 01 背包和完全背包中间c[i] 1时就是 01 背包c[i]趋向无穷大时就是完全背包。所以多重背包的朴素转移天然需要一个“拿几件”的枚举维度dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]) // 0 k c[i]这就是后面所有做法的起点。1.2 省掉枚举数量的关键正序遍历几乎每个学背包的人都被一个口诀折磨过01 背包倒序完全背包正序。但很多人只会背口诀不知道正序到底为什么有效。我换个方式讲。假设你在一家奶茶店买同一种饮品单价 10 元你手里有 50 元。如果你只有一张 10 元券那你最多买一杯这是 01 背包如果你有无限张 10 元券你可以一杯一杯地加到 50 元买五杯这是完全背包。用一维数组实现的时候正序遍历j会让dp[j - w[i]]在本轮已经被更新过。也就是说在你决定“要不要再买一杯”之前当前物品已经被算进前面的结果里了。于是买完第一杯后还能买第二杯再买第三杯……自然就实现了“无限取”。如果倒序遍历dp[j - w[i]]还是上一轮的状态里面不可能包含当前物品那就退化成 01 背包了。这个区别用代码看更直接// 01背包容量 j 从大到小 for (int i 1; i n; i) for (int j V; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]); // 完全背包容量 j 从小到大 for (int i 1; i n; i) for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]);差别只在一个循环方向但语义完全不同。理解了这一点完全背包就只剩一套模板了。1.3 完全背包的一维模板完整的完全背包代码极其简洁几乎不需要多解释const int INF 1e9; vectorint dp(V 1, 0); // 不要求装满时初始化为0 for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }如果你需要判断“是否恰好装满”初始化和结果判断要改一下vectorint dp(V 1, -INF); dp[0] 0; for (int i 1; i n; i) { for (int j w[i]; j V; j) { if (dp[j - w[i]] ! -INF) dp[j] max(dp[j], dp[j - w[i]] v[i]); } } // 最终答案dp[V]如果是 -INF说明无法恰好装满一个细节很多模板会把if (dp[j - w[i]] ! -INF)省掉直接用dp[j - w[i]] v[i]参与比较。这在-INF很大的时候没有问题但严谨起见还是建议保留判断避免负数溢出产生假结果。完全背包搞定了接下来我们回到重头戏多重背包。2. 多重背包的朴素做法三重循环能解决什么问题先说结论朴素做法虽然慢但它准确、好写、不容易出错是处理小规模数据的保底方案。而且它也是理解二进制拆分、单调队列优化的基础。2.1 朴素转移在01背包上多套一层数量枚举多重背包要求每种物品最多拿c[i]件所以最直接的写法就是在 01 背包的框架里对每件物品枚举拿k件for (int i 1; i n; i) { for (int j V; j 0; j--) { for (int k 1; k c[i] k * w[i] j; k) { dp[j] max(dp[j], dp[j - k * w[i]] k * v[i]); } } }这里有一个容易搞错的点内层枚举数量时容量j为什么还是倒序因为我们在枚举“拿 k 件当前物品”的时候所有转移必须基于“上一轮处理完前 i-1 种物品的状态”不能在同一轮里反复叠加当前物品否则k的枚举就失去了意义可能让同一种物品超过c[i]件。倒序遍历保证了dp[j - k * w[i]]还是旧状态。复杂度是 $O(N \cdot V \cdot C_{max})$其中 $C_{max}$ 是物品数量的最大值。当V和数据量都不大时这已经够用了。比如n 100、V 1000、c[i] 100三层循环也就一千万次本地跑是毫秒级。2.2 剪枝与边界什么时候可以提前收手朴素写法里藏着一些不起眼但很实用的优化我挑两个最常用的。第一如果当前物品的数量上限乘以体积已经超过了背包容量那它实际上可以当成完全背包处理没必要一个一个枚举数量直接用完全背包的正序循环即可。这个剪枝在竞赛里非常常见因为完全背包的复杂度比多重背包的朴素写法低一整个维度。第二枚举k的时候k的上限是min(c[i], j / w[i])。这个 min 一定要写对只写k c[i]会白白多算无效次数甚至可能越界访问dp数组只写k * w[i] j又容易在c[i]很大时超时。两个条件缺一不可。朴素写法虽然能应付小数据但一旦V到了 1e4、1e5 级别三层循环直接卡死。这时候就必须上更高级的写法了。3. 多重背包的三种高效写法多重背包的优化思路其实只有两条线一是把数量压缩成若干个独立的 01 物品也就是二进制拆分二是利用同余类和滑动窗口把数量枚举直接优化掉也就是单调队列优化。另外还有一条捷径就是前面说的“当数量足够多时直接转完全背包”。3.1 借完全背包的剪枝当数量多到可以当无限处理这个技巧很简单但很容易被忽略。如果某种物品的c[i] * w[i] V说明把它数量拉满之后体积已经超过背包总容量了。那不管你有多少件实际可用的件数最多也就是V / w[i]完全足够。换句话说它跟无限件没有区别直接用完全背包处理if (c[i] * w[i] V) { for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]); }这个剪枝不仅能减少循环次数还避免了你对超大c[i]做二进制拆分时多产生一堆物品。我见过有人把c[i] 1e9的物品硬生生拆了几十个物品出来其实一个剪枝就省了所有事。3.2 二进制拆分把数量压缩成logC个01背包这是多重背包最经典的写法。核心思想是任意一个数c都可以用若干个 2 的幂次加上一个余数来表示这些拆出来的数作为一组“新物品”去跑一遍 01 背包就能等价地得到“拿 0 到 c 件原物品”的所有组合。举个例子假设一个物品最多拿 13 件我们把 13 拆成1, 2, 4, 61、2、4 这三个数可以组合出 0~7 的所有数字再加上 6就能组合出 6~13 的所有数字合起来正好覆盖 0~13。注意这里最后剩下的 6 13 - 1 - 2 - 4它不是下一个 2 的幂次而是直接把剩余的件数打包。实现时通常这样写int cnt 0; for (int i 1; i n; i) { int c c[i], k 1; while (k c) { w_new[cnt] w[i] * k; v_new[cnt] v[i] * k; c - k; k 1; } if (c 0) { w_new[cnt] w[i] * c; v_new[cnt] v[i] * c; } } // 对拆出来的 cnt 个物品跑一遍 01 背包 for (int i 1; i cnt; i) { for (int j V; j w_new[i]; j--) { dp[j] max(dp[j], dp[j - w_new[i]] v_new[i]); } }为什么拆出来的数量能表示 0~C 的所有选择你可以这样理解把二进制的每一位都当作一个开关比如 1、2、4 可以让“这个物品拿几件”这个数字的二进制每一位独立变化而最后的余数c负责补齐高位保证 0 到原始数量上限都能被组合出来。这样一种有c[i]件物品被拆成了 $\lfloor \log_2 c[i] \rfloor 1$ 个新物品总复杂度变成 $O(N \cdot \log C \cdot V)$比朴素写法高出一个量级。绝大多数题目用这个做法就足够秒杀了。3.3 单调队列优化O(N*V)的终极做法二进制拆分已经很快了但遇到n 1000, V 1e5这种数据logC的因子依然可能成为瓶颈。这时候你需要的是单调队列优化把复杂度真正压到 $O(N \cdot V)$。核心观察是多重背包的转移式dp[j] max(dp[j - k * w[i]] k * v[i]) (0 k c[i])中所有能转移到dp[j]的状态它们的下标对w[i]取余都是同一个余数。也就是说按照余数a把容量分成w[i]组每组内部的状态可以单独处理。每一组内j从a开始每次加上w[i]转移就变成在一个长度有限的窗口里找最大值——这正是单调队列的典型场景。代码模板如下我会在关键位置注释for (int i 1; i n; i) { int w w[i], v v[i], c c[i]; if (c * w V) { // 数量足够多等价于完全背包 for (int j w; j V; j) dp[j] max(dp[j], dp[j - w] v); continue; } for (int a 0; a w; a) { dequeint q; // 保存下标队首是当前窗口最大值 for (int j a; j V; j w) { // 窗口范围[j - c*w, j - w] while (!q.empty() q.front() j - c * w) q.pop_front(); if (!q.empty()) { dp[j] max(dp[j], dp[q.front()] (j - q.front()) / w * v); } // 把当前状态 j 插入队列前先维护单调性 int val dp[j] - j / w * v; while (!q.empty() dp[q.back()] - q.back() / w * v val) q.pop_back(); q.push_back(j); } } }这里有一个容易懵的点为什么队里要维护dp[j] - j / w * v而不是直接维护dp[j]因为从j转移到j时价值变化量是(j - j) / w * v这里面j部分是固定的拆开之后变成dp[j] max(dp[j] - j / w * v) j / w * v所以单调队列只需要维护括号内那一部分的单调递减队列即可。这也是整个优化的精髓把跟j有关的部分和跟j有关的部分完全分离。这段代码理解起来需要一点时间但一旦写熟了它就是多重背包的万能模板。实测在V 1e5、n 1000、c[i] 1e5的数据下单调队列解法能在几十毫秒内跑完而朴素写法基本是天文数字。4. 实际选型与避坑记录背包问题看起来套路固定但实际写代码时坑非常多。我在本地反复测试、排错的过程中整理了一张对照表和几个高频问题这里分享出来。4.1 复杂度、代码量与适用场景对照写法时间复杂度空间复杂度代码量适用场景朴素三层循环$O(N \cdot V \cdot C)$$O(V)$极短小数据、刷题练习完全背包剪枝$O(N \cdot V)$$O(V)$极短某类物品数量足以忽略上限二进制拆分$O(N \cdot V \cdot \log C)$$O(V N \log C)$中等大多数竞赛题、笔试场景单调队列优化$O(N \cdot V)$$O(V)$较长大 V、大数量、卡常题目选型建议很简单先写出朴素版本确认思路再按数据范围一步步升级。如果你在笔试现场时间紧张V在 1e4 以内且n不大二进制拆分通常已经够了如果评测机特别毒、数据范围顶满或者你正在训练 DP 优化那就直接上单调队列。4.2 我在本地反复踩过的坑第一个坑是循环顺序。多重背包朴素写法的j循环必须是倒序但单调队列优化里的j分组循环又必须是正序。两者混着写很容易把自己绕晕我建议每个模板都单独存一份不要靠记忆临场推导。第二个坑是二进制拆分的余数处理。前面例子中 13 拆成1, 2, 4, 6最后的 6 是剩余数量但如果写成1, 2, 4, 8加起来是 15超过 13会导致取 14 件、15 件这种非法方案。所以拆分时一定要先减掉已拆的部分最后的c 0单独处理一下。第三个坑是初始化。不要求恰好装满时dp数组初始化为0即可要求恰好装满时必须把dp[1..V]初始化为一个极小的负值只让dp[0] 0。我见过不少人因为初始化问题在“恰好装满”和“不超过容量”两种题目之间来回 RE 和 WA。第四个坑是单调队列的窗口边界。窗口下限是j - c * w不是j - c * w - 1也不是j - (c 1) * w。我之前因为差一错误导致某些物品能多取一件或少取一件本地小数据测不出来提交就挂。后来写了个for (int k 0; k c k * w j; k)这种暴力验证程序对着随机大数据一顿对拍才把所有边界问题暴露出来。4.3 常见问题速查表症状可能原因解决办法完全背包答案偏小容量循环写成了倒序改成正序遍历01背包答案偏大容量循环写成了正序改成倒序遍历多重背包重复取超限朴素枚举时容量倒序写错或二进制拆分组数超了确保j倒序检查拆分代码二进制拆分答案偏小最后剩下的余数没有单独生成物品加if (c 0)分支单调队列 RE数组越界或队列弹出条件写错检查j - c * w的边界deque 判空恰好装满结果全是 -INF初始化未设置负无穷按要求执行“恰好装满”初始化5. 这两种背包的组合题型与扩展你以为把完全背包和多重背包单独吃透就结束了竞赛里往往不会只考单一种类而是把 01 背包、完全背包、多重背包混在一起考。5.1 混合背包有限和无限混在一起怎么处理混合背包的题目里每种物品可能是“只能拿 1 件”“可以拿无限件”“最多拿 c 件”三种情况中的一种。处理思路其实很直接遍历每一件物品时判断它的类型分别用 01 背包、完全背包、多重背包的转移方式去更新同一个dp数组。for (int i 1; i n; i) { if (type[i] 0) { // 01背包倒序 for (int j V; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]); } else if (type[i] 1) { // 完全背包正序 for (int j w[i]; j V; j) dp[j] max(dp[j], dp[j - w[i]] v[i]); } else { // 多重背包先剪枝再二进制拆分或单调队列 } }这样写虽然有一点点冗余但逻辑最清晰不容易在类型转换时出错。实际比赛中这也是大部分人采用的写法。5.2 状态定义的变化恰好装满与最大值很多题目看起来是背包实际上考的是状态定义的变化而不只是转移方程。比如“求方案总数”dp[j]就不表示最大价值而是“容量为 j 时有多少种选法”转移变成dp[j] dp[j - w[i]]再比如“求最大最小值混合”可能要把dp数组拆成两维来记录“最大价值”和“最少件数”。这些变体都是在完全背包和多重背包的骨架上做文章骨架熟了变体就只是套模板的问题。5.3 实战题单每个题型该练哪道题我整理了一个亲测有效的题单按难度递增排列练完基本能把这两种背包盘活题型推荐题目考点完全背包入门洛谷 P1616 疯狂的采药正序遍历、一维滚动完全背包方案数洛谷 P1832 AB Problem再升级方案数累加多重背包朴素洛谷 P1776 宝物筛选二进制拆分练习多重背包恰好装满HDU 2844 Coins判可行、二进制拆分单调队列优化POJ 1742 Coins / 洛谷 P3423卡常、滑动窗口优化做题顺序我建议这样先手写一遍完全背包再把朴素多重背包的代码跑通然后用二进制拆分重写一遍等这三步都顺畅了再啃单调队列。千万别一上来就背单调队列模板否则连出错都不知道错在哪一步。我自己就是在反复对拍中才慢慢建立起“背包直觉”的。有些东西光看别人代码是学不会的必须自己动手改一改、跑一跑、挂一挂才能把模板变成肌肉记忆。如果你现在刚开始接触这两种背包我的建议很直接先把完全背包的正序循环、01 背包的倒序循环、二进制拆分这三个基本功练到闭眼能写再去碰单调队列。等你真的在题里遇到V 1e5这种卡常数级别的数据再回头研究队列优化也不迟——那个时候你已经知道为什么需要它了理解起来会快得多。