背包问题在算法圈的出镜率高得有点离谱。不管是打ACM、刷LeetCode还是准备大厂笔试背包问题经常以“动态规划入门题”的身份出现结果一上来就把不少人劝退。其实背包问题的变体看着多核心就那两行状态转移。01背包、完全背包、多重背包、分组背包说到底都是在同一个框架里打转。折腾了这么多年我发现自己每次写背包题用的模板几乎没变过。今天就把这套模板整理出来顺带把每个公式背后的原因、以及各种容易踩的坑一次性说清楚。如果你是刚开始学动态规划的萌新或者刷了不少题但背包老写不对的老手这篇都能帮你把背包问题理成一套能直接抄作业的东西。1. 背包问题的整体脉络与模板设计思路1.1 背包问题到底在考什么背包问题的本质是一个“有限资源下的组合选择优化”问题。给你一个容量为V的背包和若干种物品每种物品有重量w、价值v、可用的数量c问在不超过背包容量的前提下能拿到的最大总价值是多少。这个模型听起来很具体但换个马甲就变成了很多现实问题手里预算有限怎么搭配商品组合收益最高项目有固定工时怎么分配任务让产出最大化服务器有内存上限怎么给不同容器分配资源。所以面试官和出题人都特别喜欢拿它当动态规划的入门题因为它简单到能一眼看出状态又复杂到能把循环顺序、初始化的细节都考进去。学习背包问题最关键的一步是先把问题抽象成三个要素物品、体积/费用、价值/收益。物品可能只有一种属性也可能有体积和重量两个属性数量可能为1可能无限也可能有限。题目问的可能是最大价值、最小花费也可能是方案总数。当你把一道题翻译成这三个要素它到底是哪种背包基本就清楚了。1.2 为什么需要一套模板我见过很多同学刷背包题每道题都现场推状态转移推一次错一次。不是推导能力不行而是背包的细节太多一维数组为什么要倒序初始化用0还是负无穷方案数要不要取模这些问题在考场高压下特别容易记混。准备一套模板本质上是把“从零推导”变成“按类型填空”。看到题目先分类然后选择对应的模板把数据填进去再处理边界条件。模板不是用来死记硬背的而是用来做“思考跳板”的。有了模板你可以把精力放在题目的特殊限制上而不是在基础转移上反复纠结。我自己的习惯是维护一个“背包模板文件”里面包含01背包、完全背包、多重背包、分组背包的代码以及每个代码的注释说明什么时候用正序、什么时候用倒序、dp数组初始值应该是什么。比赛前翻一遍心里就有底了。这篇文章也会按这个思路把模板和背后的原因一起给你。1.3 常见背包类型与模板的横向关系先看一张表把四类最常考的背包问题摆在一起心里有个整体认知。这些模型之间并不是孤立的它们可以互相转化尤其是多重背包二进制拆分之后就直接变成01背包。背包类型物品数量约束内层容量循环时间复杂度一句话记忆01背包每件最多选1次倒序O(nV)倒序防重复完全背包每件可选无限次正序O(nV)正序允许重复多重背包第i件最多c[i]次二进制拆分后再倒序O(nV log c)拆成01分组背包每组最多选1个先组再倒序容量再物品O(组数*V*组内大小)组内互斥从表格里可以看到01背包是绝对的地基。完全背包只是01背包把倒序改成正序多重背包通过二进制拆分变成若干个01背包分组背包则是在01背包外面多了一层“组”的循环。所以接下来先从01背包讲透后面所有扩展都会轻松很多。2. 01背包一切背包问题的地基2.1 状态定义与转移方程推导01背包的定义再强调一次有n件物品每件重量为w[i]、价值为v[i]每件最多取一次背包容量为V求能装下的最大价值。我们用dp[i][j] 表示“只考虑前i件物品背包容量不超过j时能获得的最大价值”。这里有个小细节j表示“容量不超过j”而不是“恰好等于j”这是我们后面初始化问题的关键。对于第i件物品决策只有两个不选它那么状态就是dp[i-1][j]选它前提是j w[i]那么剩余容量j-w[i]要用来装前i-1件物品价值为dp[i-1][j-w[i]] v[i]。取两者较大值dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])当j w[i]时否则dp[i][j] dp[i-1][j]。这个转移方程可以说是整个背包问题家族的“总纲”。它本质上是一个多阶段决策每处理一件物品就是对“选”和“不选”两个分支做一次取优。你可以把dp数组想象成一张表格行是物品编号列是容量表格里的每个格子都记录当前这个状态下的最优解。这样想的话很多变体其实都是在往这张表格里填不同规则。2.2 一维数组优化的倒序原理二维dp虽然直观但空间复杂度是O(nV)当n和V都在1000以上时需要1e6个状态勉强可以但如果n是1e5V是1e5就是1e10直接爆内存。所以竞赛里几乎都用一维滚动数组。一维数组dp[j]直接表示“容量为j时的最大价值”。外层循环枚举第i件物品内层循环必须从V向w[i]递减。关键点来了为什么必须倒序因为dp[j-w[i]]在一维数组中既可能是上一轮的结果也可能是本轮已经被更新过的结果。如果正序更新当你计算dp[j]时dp[j-w[i]]可能已经被当前物品更新过了也就是说当前物品被使用了不止一次这就变成了完全背包。而倒序可以保证在计算dp[j]时dp[j-w[i]]还没有被本轮更新它存储的仍然是“只考虑前i-1件物品”时的最优值所以每个物品最多被选一次。用生活化的例子说你往背包里装东西倒序相当于每件物品只拿一次正序相当于同一件物品可以反复拿。算法没有魔法顺序决定了物品的使用次数。2.3 01背包标准模板下面给出最常用的C模板。数组下标从1开始存物品重量存在w[1..n]价值存在v[1..n]容量为V。#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXV 1005; int w[MAXN], v[MAXN]; int dp[MAXV]; int main() { int n, V; cin n V; for (int i 1; i n; i) { cin w[i] v[i]; } // 求“不超过容量V”的最大价值dp数组全部初始化为0即可 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]); } } cout dp[V] endl; return 0; }Python版本也一并给出来刷LeetCode或者面试手写时更常用n, V map(int, input().split()) w [0] * (n 1) v [0] * (n 1) for i in range(1, n 1): w[i], v[i] map(int, input().split()) dp [0] * (V 1) for i in range(1, n 1): for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) print(dp[V])注意两个边界内层循环从V到w[i]小于w[i]的容量不用更新因为放不下第i件物品dp[j]自动保留上一轮结果。在Python里range(V, w[i] - 1, -1)是倒序遍历的正确写法步长-1时结束位置要减1这个细节很容易写错。2.4 基础变种恰好装满、求最小值和方案数模板最容易被坑的地方是dp数组的初始化。如果题目问“恰好装满背包时能得到的最大价值”那么初始化时dp[0]0dp[1..V]负无穷比如-1e9。理由是只有容量0这个状态是合法起点从0开始一步步凑出其他容量其他容量在还没放任何物品时不可能是“恰好装满”的合法状态。在转移时dp[j - w[i]]为负无穷的状态不应该被选进来所以答案还是有效的。如果题目问“总重量不超过V的最大价值”则dp数组全部初始化为0因为容量有多余无所谓空背包本身就是合法方案。如果题目问的是“最小价值”就把初始化反过来恰好装满时dp[0]0其余为INF不超过容量时全部为0。转移方程里的max改成min即可。至于“有多少种方案恰好装满”属于一个独立的变体后面专门用一章说。先把这三种基础搞明白后面的变体才能不慌。3. 完全背包与多重背包模板的横向扩展3.1 完全背包模板与正序原因完全背包和01背包唯一的区别是每件物品可以取无限次。很多人第一次学完全背包会觉得它和01背包差别很大其实只需要把内层循环倒过来。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]); } }正序的意思是计算dp[j]时dp[j - w[i]]可能已经在当前这轮物品i中被更新过了这意味着当前物品可以重复使用。比如容量是10物品重量是3在正序更新到dp[6]时dp[3]已经是“装了1个物品i”的价值所以dp[6]可以再装1个变成“装了2个物品i”。这样一路推下去同一件物品可以被取任意多次。这就是完全背包的核心逻辑。这里有个常见误区有人觉得完全背包需要再加一层k循环枚举物品选了几件。没错暴力解法确实是这样但复杂度是O(nVc)完全不可接受。一维正序已经隐式地完成了“无限制取用”的优化记住这个结论能省下大量时间。3.2 多重背包二进制拆分优化多重背包给了每件物品一个数量上限c[i]既不是最多1次也不是无限次而是有限次。朴素想法是把c[i]件物品当成c[i]个01背包物品处理但总复杂度会变成O(V * Σc[i])很容易超时。二进制拆分是竞赛里的标准做法。原理是任何一个正整数c都可以拆成若干个2的幂和一个余数这些拆分出来的组可以表示0到c之间的任意整数。比如c13拆成1、2、4、6剩余其中124613这四个数通过选或不选能组合出0到13的所有数量。于是原本13件相同物品被压缩成4个“组合物品”每个组合物品有重量w*k、价值v*k再跑一遍01背包即可。代码模板如下struct Node { int weight, value; }; vectorNode items; // 拆分过程 for (int i 1; i n; i) { int cnt c[i]; for (int k 1; k cnt; k 1) { items.push_back({w[i] * k, v[i] * k}); cnt - k; } if (cnt 0) { items.push_back({w[i] * cnt, v[i] * cnt}); } } // 对items跑01背包 for (auto it : items) { for (int j V; j it.weight; j--) { dp[j] max(dp[j], dp[j - it.weight] it.value); } }注意二进制拆分的结束条件剩余数量cnt不断减去k当k大于剩余cnt时循环终止然后要把剩下的cnt作为一个组补进去。这个“补余数”的步骤特别容易漏漏了之后有些数量凑不出来答案就会偏小。3.3 分组背包与二维费用背包分组背包是另一个高频变体。题目会给出若干组物品每组内只能选一个比如“每组代表一种选择方案互斥”。模板的关键是循环顺序先遍历组再倒序遍历容量最后遍历组内物品。写成C大概是for (int g 1; g groupCount; g) { for (int j V; j 0; j--) { for (int k 0; k group[g].size(); k) { if (j group[g][k].weight) { dp[j] max(dp[j], dp[j - group[g][k].weight] group[g][k].value); } } } }为什么容量循环要放在组内物品之前因为要保证每个组最多选择一个物品。如果先枚举物品再枚举容量同一个组里的多个物品可能在同一轮里被选进背包就失去了“互斥”的含义。这一点从代码顺序上就能看出来很多新手写反后答案会偏大。二维费用背包则是在原有一维容量上再加一个限制维度比如物品既有体积也有重量。这时dp数组变成dp[j][k]表示在容量j和重量k的同时限制下的最大价值转移多一维即可for (int i 1; i n; i) { for (int j V; j w[i]; j--) { for (int k W; k weight2[i]; k--) { dp[j][k] max(dp[j][k], dp[j - w[i]][k - weight2[i]] v[i]); } } }二维费用背包的循环仍然是倒序原理和01背包一样都是为了“每个物品最多选一次”。如果物品可以无限取就把倒序改成顺序。4. 背包问题方案输出与方案数统计4.1 方案数统计模板有些题目不问最大价值而问“填满背包的方案总数”。这是背包问题的另一种经典问法。转移方程从max变成累加dp[j] dp[j] dp[j - w[i]]初始状态dp[0] 1表示容量为0时有一种方案什么都不装。其余dp[j]初始化为0。枚举物品和容量时01背包仍然倒序完全背包仍然正序。下面以01背包为例dp[0] 1; for (int i 1; i n; i) { for (int j V; j w[i]; j--) { dp[j] (dp[j] dp[j - w[i]]) % MOD; } }为什么是累加而不是取max因为dp[j]包含了“不选当前物品的方案数”以及“选当前物品之后剩余容量j-w[i]对应的方案数”。这两类方案互不重叠所以直接相加。注意这里dp[j]表示方案数和前面最大价值的dp[j]含义完全不同需要重新定义。4.2 输出具体选择方案如果题目不仅要最大价值还要输出具体选了哪些物品那就不能用一维dp直接回溯了因为一维状态被覆盖了无法知道每个容量下的上一轮状态。所以要么保留二维dp数组要么额外用一个二维数组记录选择。二维回溯的思路是这样的先正常跑二维dp得到dp[n][V]。然后从in、jV开始判断第i个物品是否被选中。如果dp[i][j] dp[i-1][j]说明不选第i个物品也能达到同样的价值那就把i减1继续如果dp[i][j] dp[i-1][j-w[i]] v[i]说明选了第i个物品记录它并跳转到i-1、j-w[i]。两个条件可能同时成立根据题目要求选择优先输出一种方案即可。以下是记录选择的简化伪代码vectorint chosen; int i n, j V; while (i 1 j 0) { if (dp[i][j] dp[i - 1][j]) { i--; } else { chosen.push_back(i); j - w[i]; i--; } }有两点要注意一是最终答案dp[n][V]可能等于dp[n-1][V]这套回溯会优先选择不选得到“不使用当前物品”的方案二是当出现多种等价方案时这个流程只能输出一种若题目要求字典序最小需要另做处理。4.3 字典序最小方案处理技巧字典序最小意思是选中的物品编号序列按从小到大排序后字典序最小。比如{1, 3}小于{2}。处理技巧是DP反着做。从第n件物品往第1件做dp[i][j]表示“从第i件到第n件物品容量为j时的最大价值”。然后从第1件物品开始正着判断如果当前容量j能装下第1件物品并且选了它之后的收益不小于不选它的收益也就是dp[i][j] dp[i1][j-w[i]] v[i]那么优先选择它然后j减去w[i]否则不选跳到i1。因为编号小的物品优先级高所以能得到字典序最小的方案。这个技巧在竞赛里不算高频但在面试手写时可能会突然遇到知道思路比临时硬推要稳。5. 模板封装与实操经验5.1 把多种背包模板封装成通用函数平时刷题我建议把背包模板写成函数而不是每次都重敲循环。因为函数可以把“容量、物品数组、方式类型”作为参数代码复用性更高。比如C里可以写一个处理01背包的函数int knap01(const vectorint w, const vectorint v, int V) { vectorint dp(V 1, 0); int n w.size(); for (int i 1; i n; i) { for (int j V; j w[i - 1]; j--) { dp[j] max(dp[j], dp[j - w[i - 1]] v[i - 1]); } } return dp[V]; }如果你担心下标问题可以把w和v从下标1开始存或者直接用这种从0开始的写法只要下标对齐就行。我自己更习惯下标从1开始因为状态转移里的i-1语义更清晰。但这个不是强制标准重要的是每次写完检查一遍数组下标。封装的意义不只是省代码而是把“正序/倒序”这个区别隔离在函数内部。如果某道题需要同时处理01背包和完全背包你可以写两个函数名字一眼能区分避免自己在主函数里把循环顺序写混。比赛时要的是稳定输出不是现场炫技。5.2 复杂度与数据范围估算背包题的复杂度分析直接决定了模板能不能用。01背包时间复杂度O(nV)空间优化后O(V)。当n1000、V1000时是100万次运算随便跑当n10^5、V10^5时10^10次运算基本超时需要考虑其他做法比如价值范围较小的背包、单调队列优化等。完全背包同样O(nV)。多重背包经过二进制拆分后物品数量从Σc[i]变成Σlog2(c[i])再跑01背包所以复杂度是O(V * Σlog c[i])。例如n100、V1000、每个c[i]1000时拆分后每个物品约10个组总复杂度1000*100*1010^6非常快。内存上一维dp数组只需要O(V)。如果用了二维dp记得考虑n*V会不会超过内存限制。一般题目给出V1e4、n1e3二维就是1e7个int约40MB勉强可行V1e5就千万别用二维了。5.3 用暴力对拍验证模板模板写好后怎么确认它是正确的我自己的方法是写一个暴力程序或递归搜索然后跑小数据对拍。比如n10、V20暴力枚举所有物品组合把最大价值算出来和模板结果对比。如果随机生成1000组数据全部一致那这个模板基本上没问题。对于方案数问题也可以用相同方式去验证枚举所有子集统计总重量为某个值的方案数对比dp结果。把对拍脚本放在模板文件旁边以后改模板时随时跑一遍心里踏实。这个习惯帮我抓出过好几次递归边界写错的问题。6. 常见问题与排查技巧实录6.1 初始化陷阱这是背包问题出错率最高的地方没有之一。同样是求最大价值题目说“不超过容量V”和“恰好装满容量V”初始化的dp数组完全不一样。我把常见情况整理成一张表问题类型初始化方式转移方程求最大价值容量不超过Vdp[0..V]0max求最大价值恰好装满Vdp[0]0dp[1..V]-INFmax求最小价值容量不超过Vdp[0..V]0min求最小价值恰好装满Vdp[0]0dp[1..V]INFmin求方案数恰好装满Vdp[0]1dp[1..V]0累加为什么恰好装满时要用-INF或INF因为dp[j]要表示“凑到容量j”的合法状态没凑到就是非法。如果你初始化为0那么那些凑不出来的容量也会参与转移导致错误答案。很多题目的样例故意用“恰好装满”当坑就是考察这一点。6.2 循环顺序混淆排查背包问题里“正序/倒序”“外层物品/外层容量”是两大经典易错点。01背包外层物品、内层倒序容量完全背包外层物品、内层正序容量分组背包先组、再倒序容量、再物品。如果写反结果通常不是偏大就是偏小。排查技巧很简单输出dp数组用一个小样例手算验证。比如容量3一个物品重量2价值5。01背包正确结果dp[3]5完全背包正确结果dp[3]5因为只能放1个再举容量4物品重量2价值501背包dp[4]5完全背包dp[4]10。如果结果不对立刻能看出来是顺序问题。6.3 数组越界与状态继承一维背包写for (int j V; j w[i]; j--)时不用考虑jw[i]的情况因为那些状态会直接继承上一轮的dp[j]不会发生变化。但如果你写成for (int j V; j 0; j--)然后加if判断千万别忘记判断否则访问j-w[i]可能变成负数下标程序直接崩。二维背包也有类似问题转移前要判断jw[i] kweight2[i]。使用滚动数组时还要注意每一轮是否需要把dp数组清零或拷贝不同写法要求不同。6.4 方案数溢出与取模方案数累加时最坏情况会指数级增长哪怕n只有几十方案数也可能超过int范围。通常题目会让答案对1e97取模。取模时要小心加法取模没问题但如果后面有减法比如dp[j] (dp[j] - dp[j-w[i]] MOD) % MOD否则可能出现负数。这个MOD的小细节很多人会漏。6.5 从TLE到AC的排查清单如果你提交后超时按这个顺序检查多重背包是不是还在用三层循环暴力枚举如果是改成二进制拆分。完全背包是不是还在枚举k件物品如果是改成正序一维。数组大小是不是开小了导致越界越界有时会让程序卡死而不是报错。是否能用滚动数组把二维降成一维如果题目需要完整dp表回溯就在回溯时用二维否则用一维。数据范围是否特别大比如V达到1e9那样背包dp本身就不适用要考虑其他算法。按这个清单90%以上的背包超时问题都能定位到。最后再分享一个小习惯我把01背包和完全背包的模板放在一起注释里专门写着“正序无限取倒序有限取”每次写题前扫一眼。尤其是紧张的时候循环顺序写反的概率比想象中高。背包题万变不离其宗拿到新题先判断三件事物品能取几次容量限制是几维问的是价值还是方案数判断完再选模板基本就不会跑偏。希望这套模板能帮你把背包问题从“会背”变成“会懂”。