背包问题几乎是每个算法学习者绕不过去的一道坎。无论是校招笔试、竞赛训练还是日常刷题背包问题都以极高的频率出现而且它的变种之多足以让新手感到头晕为什么 01 背包要倒着遍历容量为什么完全背包正着遍历就可以了分组背包和多重背包怎么统一成一套模板方案数、具体方案、字典序最小方案……这些都怎么扩展到现有代码上这篇文章不是从零开始讲背包问题的基本原理而是直接给出一套可复用的模板体系把 01 背包、完全背包、多重背包、混合背包、分组背包、二维费用背包、方案记录与计数全部串在一起帮你在面对新题时能一眼识别题型快速套用模板而不是每次从头推一遍状态转移方程。先说我个人用了很久的代码习惯背包问题统一使用一维滚动数组为主模板容量循环正序还是逆序根据背包类型决定初值根据题目求 max、min 还是计数来定。这套思路的好处是上手快、代码短、思路清晰后面所有变种都是在此基础上做小手术。1. 为什么建议用一维滚动数组做模板基底先看最经典的 01 背包定义有 N 件物品每件有重量 w[i] 和价值 v[i]背包容量为 C问能装入的最大价值。二维状态转移方程是标准的dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这个方程的意思是面对第 i 件物品要么不拿价值维持在前 i-1 件、容量 j 的状态要么拿那就要腾出 w[i] 的容量所以看 dp[i-1][j-w[i]] 再加上当前物品价值。观察依赖关系可以发现第 i 层只依赖第 i-1 层更早的状态根本用不到。这就意味着我们可以把第一维压缩掉只用一个一维数组 dp[j] 表示容量为 j 时能获得的最大价值。关键在于更新顺序必须逆序遍历 j从 C 往 w[i] 方向更新。为什么必须逆序因为正序遍历会让 dp[j-w[i]] 已经是本层更新过的值也就是同一件物品被重复放入。你想象这样一个场景一个容量 3 的背包一件物品重量 1、价值 2正序遍历 j1、2、3 时dp[1] 先变成 2等更新 dp[2] 时dp[1] 已经是 2于是 dp[2] 变成 4——你只用一件物品就凑出了 4 的价值显然不对。逆序遍历时更新 dp[2] 用的 dp[1] 还是上一层的值 0这样 dp[2] 才是正确的 2。模板如下for (int i 1; i N; i) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这套逻辑在任何语言里都一样Python 版只是写法略有不同for i in range(1, N 1): for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])实际做题时我习惯在输入时从下标 1 开始存物品这样状态转移里 dp[j-w[i]] 不会出现负数下标问题而且语义清晰——第 0 件物品表示没有物品此时 dp 全为 0。2. 01背包的三种普通题目变体与init细节很多资料把 01 背包的代码给出来就完了但实际题目里坑点全在初始化上。同样是 01 背包求的是最大价值和恰好装满背包的最大价值代码几乎一样d区别只在一句话。如果是求不超过容量 C 的最大价值那么初始时 dp[0…C] 全部为 0 就正确因为容量用不完也是合法的。如果是求恰好装满时最大价值那么必须把 dp[0] 设为 0而 dp[1…C] 设为负无穷通常用 -INF比如 -1e9。这样做的原理很直观只有容量 0 是合法初始状态什么都没装且正好装 0是成立的容量为 j 的恰好装满状态目前不存在所以用负无穷表示不可达。当某个状态真的能从 dp[0] 转移过来时它才会变成有效值。同理如果求的是最小价值或最少物品数初始时 dp[1…C] 要设正无穷INF比如 0x3f3f3f3fdp[0] 为 0。这三类初始化是背包题里最容易丢分的地方我把它们整理成一个常用参考表问题类型dp 初值一维转移方式备注不超过容量的最大价值dp[0…C] 0max最常见恰好装满的最大价值dp[0] 0, dp[1…C] -INFmax答案可能为负注意特判恰好装满的最小代价dp[0] 0, dp[1…C] INFmin用于硬币找最少数量方案总数恰好装满容量dp[0] 0, dp[1…C] INFmin与最小代价类似方案数计数组合/排列dp[0] 1, 其余 0加法见本文第 6 章使用负无穷或正无穷初始化的主要风险在于如果 INF 选得太大加法转移时可能溢出。我用的是 int 范围习惯设 0x3f3f3f3f约 1e9两个 INF 相加也不会爆 int 的边界2e9 以内所以这是安全的选择。3. 完全背包模板只差一个反转但原理完全不同完全背包和 01 背包的区别在于物品数量无限——每件物品可以拿任意多次。状态转移方程写出来是这样dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])注意第二个转移是从 dp[i] 来的意思是第 i 件物品还可以继续拿而不是回到 dp[i-1]。这个差别直接决定了代码实现把 01 背包容量循环从逆序改成正序就得到了完全背包模板。正序更新的效果我们在前文已经看到了——同一件物品会被重复计入而这恰好就是完全背包所需要的特性。这算是我个人觉得背包问题里最有意思的地方一个 bug 特性换一个场景就成了正确逻辑。for (int i 1; i N; i) { for (int j w[i]; j C; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }完全背包有个经典的优化点在循环物品前可以先删掉那些既重又低价值的物品。不过这个优化只适用于物品数量不多的场景并且需要先按重量和价值做一轮过滤如果物品数量本身是 1e5 级别那优先考虑用单调队列优化。如果题目条件允许用暴力方法先筛一遍可以参考下面的思路把物品按重量排序如果存在一件物品重量小于等于某物品且价值大于等于它那么那件又重又便宜的物品永远不可能被选入最优解可以直接丢掉。4. 多重背包二进制拆分是最实用的模板化处理多重背包的状态是每件物品有限定次数 c[i] 次可用。最直接的思路是把每件物品拆成 c[i] 个01背包物品总物品数变成 sum(c[i]) 再跑 01 背包。这个思路在小数据下没问题一旦 c[i] 超过 1e4复杂度瞬间爆炸O(N * C * avg(c)) 直接超时。二进制拆分的思路很巧妙任意一个正整数 k都可以用若干 2 的幂次之和表示。比如 13 1 2 4 6最后一个 6 是剩余部分。于是把 c[i] 件物品拆成约 log(c[i]) 组每组权重分别是 w[i]*1、w[i]*2、w[i]*4……每组只能选一次01 背包就能组合出 1 到 c[i] 之间任意数量该物品的选取方案。拆分的核心代码vectorpairint, int goods; // 存 {重量, 价值} for (int i 1; i N; i) { for (int k 1; k c[i]; k 1) { int cnt min(k, c[i]); goods.push_back({w[i] * cnt, v[i] * cnt}); c[i] - cnt; } if (c[i] 0) { goods.push_back({w[i] * c[i], v[i] * c[i]}); } } // 之后对 goods 跑一遍 01 背包比如一件物品可用 13 次会拆成 1、2、4、6 四组。1 到 13 之间的任何一个数字都能由这四组里的若干组加出来不信可以自己验证 51471611416。这样复杂度从 O(NCmax(c)) 降到 O(NClog(max(c)))大部分题目都能过。如果遇到 c[i] 和 C 都很大的情况比如都是 1e5 级别那得多重背包的单调队列优化那个属于进阶内容这篇文章先不展开。5. 从模板到变形混合背包、分组背包、多维费用背包5.1 混合三种背包的通用写法混合背包不是第四个新类型而是把 01 背包、完全背包、多重背包混在同一道题里有的物品只能拿一次有的能拿无限次有的只能拿有限次。常规解法是分类讨论碰到 01 就用逆序碰到完全就正序碰到多重就二进制拆完继续。但如果想统一模板另一种思路是全部转成有限次来处理——把完全背包的物品次数设成 C/w[i]1最多能拿的数量然后对每件物品做二进制拆分。这样混合题就统一成了若干 01 物品代码量反而更小。5.2 分组背包的模板分组背包是另一个高频变种每个组内有多件物品但每组最多选一件。状态定义不变循环顺序变成了三层for (int g 1; g G; g) { // 枚举组 for (int j C; j 0; j--) { // 枚举容量逆序保证每组只选一件 for (int k 0; k group[g].size(); k) { int w group[g][k].w, v group[g][k].v; if (j w) { dp[j] max(dp[j], dp[j - w] v); } } } }关键点在于容量循环要放在组内物品循环的外面。如果先枚举物品再枚举容量就会出现同一组内多件物品被同时选中的问题。顺序一旦写错结果就是同组物品互相组合必须特别注意。另外容量循环是从 C 到 0 而不是 C 到 1因为组内物品可能自身重量为 0需要更新 dp[0] 本身相关的转移。5.3 二维费用背包当题目引入两个限制条件比如重量和体积或者重量和件数状态就从一维变成二维for (int i 1; i N; i) { for (int j C; j w[i]; j--) { for (int k D; k cost[i]; k--) { dp[j][k] max(dp[j][k], dp[j - w[i]][k - cost[i]] v[i]); } } }这里体积的遍历也是逆序理由与一维逆序完全相同就是防止同一件物品被用两次。二维费用背包只要写熟了这个模板后续再升三维、四维也只是加循环的事本质思想不变。6. 背包问题求方案与求方案数从 d背p 回溯的完整套路背包题一个很常见的进阶要求是不仅要算出最优价值还得输出具体选了哪些物品。这个需求在面试中尤其常见因为它考查的是对 dp 过程可逆理解的能力。做法先跑完 dp然后从 dp[N][C] 倒着往回判断。如果用二维数组做判断方式很简单——如果 dp[i][j] dp[i-1][j]说明第 i 件物品没被选如果 dp[i][j] dp[i-1][j-w[i]]v[i]说明被选了。若两种都成立说明存在多种方案具体输出哪种看题目要求。// 用二维数组存完整dp便于回溯 bool selected[N 1] {false}; int j C; for (int i N; i 1; i--) { if (j w[i] dp[i][j] dp[i - 1][j - w[i]] v[i]) { selected[i] true; j - w[i]; } }如果是用一维滚动数组跑的 dp回溯就麻烦一些因为每一层覆盖掉了上一层的记录。这时候要么改用二维数组要么额外开一个记录数组保存每个状态在容量 j 下最后放入的物品编号。我的习惯是明确要输出方案的题直接上二维 dp内存虽然多一点但省去了回溯阶段的很多脑力消耗。若题目要求输出字典序最小的方案需要把物品顺序反转后重新编号处理这个属于再进阶的小技巧做题遇到时单独留意。求方案数的题则是另一种套路dp 状态含义变成 dp[j] 表示装满容量为 j 的方案总数初始 dp[0] 1转移用累加。01 背包求方案数每个物品只能选一次dp[0] 1; for (int i 1; i N; i) { for (int j C; j w[i]; j--) { dp[j] dp[j - w[i]]; } }完全背包求方案数排列数 vs 组合数组合数外层物品、内层容量每种物品的使用顺序无关是组合语义排列数外层容量、内层物品同一组物品不同顺序算不同方案是排列语义举例说明硬币找零问题中用 1 分和 2 分硬币凑出 3 分组合数答案是 212 和 21 视为同一种排列数答案是 312、21、111。这两种写法只差一个循环嵌套顺序但语义截然不同做题时务必先看题目说的是方案数还是不同组合方式。7. 我在套模板时踩过的坑和判断题型的心法我先把最容易踩的坑列出来这些全部来源于实战不是教科书里的建议。第一个坑把求最大价值和求方案数的 dp 初值搞混。一个用 dp 全 0 max一个用 dp[0] 1 累加。两种状态定义完全不同不能复用一套代码。我最开始写背包问题时习惯性地在求方案数的题里把 dp[0] 也设成 0结果样例能过提交就错。方案数 dp[0] 1 的含义是空集正好装满空背包这是一种方案。第二个坑多重背包二进制拆分时剩余数量没有正确处理。看前面那段模板代码每次拆完后 c[i] 在递减最后还会有一个 if (c[i] 0) 把剩余部分全部塞进去。如果漏掉最后这个 if拆分组就无法表示超过 2 的幂次和的数量导致正确性出问题。第三个坑分组背包的枚举顺序错误。很多人容易把物品循环放在容量循环里面这样直接变成组内所有物品相互叠加等于把每组限制放宽成了无限选。这个问题一旦出现很难靠样例发现因为在特定数据下结果恰好正确纯看运气。第四个坑完全背包用单调队列但没想清容量循环方向。单调队列优化的完全背包核心是用滑动窗口维护 j % w[i] 同余类上的最优值内层循环要从 0 到 w[i]-1 枚举余数再对每个同余类做单调队列。这个优化很强大但代码量大如果不是强需求我一般先用二进制拆分和正序循环复杂度不够再上队列。第五个坑把 INF 设置成 INT_MAX导致 dp[j] v 溢出变负。在求最小价值的背包题中这个坑非常隐蔽。用 0x3f3f3f3f 而非 INT_MAX就是因为两个 INF 相加还在 int 可表示范围内不会溢出成负数。再来聊聊怎么快速判断题型。我自己的经验是从三个信号入手第一物品能不能重复选。能重复选优先想完全背包不能是 01 背包部分能部分不能是混合背包。第二分组限制还是件数限制。物品按组给出且每组互斥就是分组背包给了每件物品的具体可用次数就是多重背包。第三问的是最值还是方案。最值走 max/min方案走累加输出具体方案走二维 dp 回溯。遇到一道新题先用这三问给自己定位再套模板效率远高于对着题目硬想状态转移方程。最后分享两个日常刷题的小习惯一是每次跑完背包模板自主在本地打印一遍 dp 数组来核对逻辑而不是只看 accept 与否二是把常用的五六种背包模板存成代码片段但在正式笔试时依然手动默写一遍确保自己真的理解每一步的作用。模板是拿来缩短思维路径的不是让你背代码应付面试的——毕竟面试官很可能追问一句你这段为什么这么写到那时候真正理解原理的人答得自然只会背模板的人大概率当场卡壳。
