1. 背包问题到底在解决什么三类基础背包的共性与区别动态规划里最容易被新手拿来“入门即劝退”的就是背包问题。而我见过最多的情况是上课听的时候觉得状态转移方程挺简单一上机写代码就卡在“为什么容量循环要倒着写”“为什么能压缩成一维数组”这些细节上。这篇博文想用C代码配合推导把0/1背包、完全背包、多重背包这三类最基础的背包问题串一遍顺带说说我在实际刷题和写项目里踩过的坑。先说背包问题的共性。给定一个容量为W的背包以及n件物品每件物品有自己的重量w[i]和价值v[i]目标是选出若干件物品装入背包后总重量不超过W同时让总价值最大。这个模型看起来简单但它几乎能套进所有“有限资源下做最优选择”的场景预算买设备、服务器分配算力、货车装载货物本质上都是背包。三类基础背包的区别只有一句话0/1背包是每件物品最多取一次完全背包是每件物品可以取无限次多重背包是每件物品最多取c[i]次。就这一个小小的条件差异会导致状态转移方程的方向完全不同也会让代码里那两层for循环的写法产生天壤之别。我经常跟朋友说背包问题是一个特别好的“动态规划思维体检仪”。因为它把“状态定义”“状态转移”“边界处理”“空间优化”这几个动态规划核心要素全占齐了。你只要能把背包问题写得滚瓜烂熟动态规划里的很大一部分套路你其实已经掌握了。后面遇到最长上升子序列、区间DP、树形DP虽然场景不同但思考方式是一样的先定义清楚dp[i][j]代表什么再想怎么从更小的子问题推出当前状态。2. 0/1背包从二维DP到一维滚动数组2.1 先写一版不会错的二维DP我建议零基础的人别一上来就用一维数组先老老实实开二维数组把状态转移写对。虽然一维写法面试笔试里更常见但二维写法能帮你把状态定义彻底想清楚。定义dp[i][j]表示“考虑前i件物品当前背包容量为j时能获得的最大价值”。边界是dp[0][j] 0一件物品都不考虑价值自然是0。状态转移方程长这样第i件物品不选dp[i][j] dp[i-1][j]第i件物品选前提是j w[i]此时dp[i][j] dp[i-1][j-w[i]] v[i]取两者最大值。写成C就是#include vector #include algorithm using namespace std; int knapsack01_2d(int W, const vectorint w, const vectorint v) { int n w.size(); vectorvectorint dp(n 1, vectorint(W 1, 0)); for (int i 1; i n; i) { for (int j 0; j W; j) { dp[i][j] dp[i - 1][j]; if (j w[i - 1]) { dp[i][j] max(dp[i][j], dp[i - 1][j - w[i - 1]] v[i - 1]); } } } return dp[n][W]; }这里有个容易搞晕的小地方代码里的w[i-1]对应第i件物品因为vector下标从0开始。我见过不少人在这里反复调半天最后发现不是思路错纯粹是下标差一位。二维版本的时间复杂度是O(nW)空间复杂度也是O(nW)。当n和W都是几千的时候二维数组就有点吃紧了。比如n2000W2000数组大小是400万个int十几MB勉强能跑但如果n10000W10000那就是1亿个int400MB内存直接爆掉。所以掌握空间优化是必须的。2.2 一维数组与倒序枚举关键在于“每个物品只选一次”从二维变成一维的思路很朴素dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]也就是当前这一行只和上一行有关。那我干脆只保留一行滚动更新就好了。于是写出这样的代码int knapsack01_1d(int W, const vectorint w, const vectorint v) { int n w.size(); vectorint dp(W 1, 0); for (int i 0; i n; i) { for (int j W; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }注意内层循环的顺序从W往小枚举到w[i]就停下来。这就是被问过无数次的问题为什么0/1背包的容量循环要倒序我拿一个具体例子说明。假设容量W5只有一件物品重量4价值100。如果容量循环正着写从0枚举到5j4时dp[4] max(dp[4], dp[0]100) 100没毛病。j5时dp[5] max(dp[5], dp[1]100) 100也还好。但问题出在j4已经更新了dp[4]如果后面有另一件重量1的物品当j5的时候用的是dp[4]而dp[4]里可能已经包含了第一件物品的价值。如果这算是“允许重复取一件物品”那正好是完全背包但在0/1背包里每件物品只能用一次倒序枚举可以保证在计算dp[j]时dp[j-w[i]]还是上一轮物品循环结束后的旧值还没有被当前物品污染。我一直觉得“污染”这个词特别形象。正序枚举时当前物品像一个调皮的孩子会把dp数组从左到右全改一遍倒序枚举时它从右往左改碰到的左边区域还是干净的上一轮状态。空间优化后代码短了但可读性其实下降了。所以我写代码有个习惯如果面试或者写竞赛题需要一维写法我会在草稿纸上先把二维转移画一遍确认状态含义正确再压缩成一维。这个习惯帮我挡住了很多低级错误。2.3 试一下手写推导光看代码可能还不够我建议你拿纸笔推一组小数据。比如W4三件物品分别是物品1重量1价值15物品2重量3价值20物品3重量4价值30初始化一维dp数组为[0,0,0,0,0]。第一轮迭代物品1倒序更新j4dp[4]max(0, dp[3]15)15j3dp[3]max(0, dp[2]15)15j2dp[2]max(0, dp[1]15)15j1dp[1]max(0, dp[0]15)15此时dp[0,15,15,15,15]。第二轮迭代物品2注意现在dp[1]15说明物品1已经被选过了j4dp[4]max(15, dp[1]20)max(15,35)35j3dp[3]max(15, dp[0]20)20第三轮迭代物品3j4dp[4]max(35, dp[0]30)35所以最优解是35对应物品1物品2总重量4总价值35。这个手推过程做完你对“每个物品只能选一次”的直觉会强很多。3. 完全背包与多重背包状态方程的微小改动3.1 完全背包的正序枚举到底改了什么完全背包允许每件物品取无限次但要保证不超过容量。这时候最直接的想法是把“取k次”枚举一遍但那样复杂度会变成O(nW*maxCount)不太好看。实际上完全背包的状态转移可以写成dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])j w[i]。注意这里第二项是dp[i][j-w[i]]而不是dp[i-1][j-w[i]]。它的含义是当前这件物品我已经“考虑过继续取同一件”的可能性所以允许在同一个物品循环内部反复叠加。放到一维数组里就变成了正序枚举int knapsackComplete(int W, const vectorint w, const vectorint v) { int n w.size(); vectorint dp(W 1, 0); for (int i 0; i n; i) { for (int j w[i]; j W; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }和0/1背包一维代码相比区别只有一行内层for循环从j w[i]正序枚举到W。为什么会这样回到刚才“污染”的说法正序枚举时dp[j-w[i]]已经被当前物品更新过里面可能已经包含了多个当前物品所以后面再更新dp[j]时天然支持“再取一件当前物品”的操作。这东西你动手推一遍比死记硬背强。比如W4只有一件物品重量2价值3。正序枚举j2dp[2]3j3dp[3]dp[1]33这里不含当前物品因为12j4dp[4]dp[2]36而dp[2]里已经有第一件物品了所以相当于取两件总价值6。这就实现了无限取用。3.2 多重背包的二进制拆分多重背包是每件物品最多用c[i]次。最朴素的做法是在0/1背包内层再加一重循环枚举使用数量k但那是三重循环n、W、c都可能到1000甚至10000直接超时。常用套路是二进制拆分。原理是任何正整数c都能拆成若干个“2的幂次”和一个剩余数的组合比如c13可以拆成1、2、4、6也就是13 1246。这样只需要把原来的13件物品拆成4个“新物品”每个新物品的重量和重量分别是原物品的对应倍数然后做0/1背包即可。这个技巧能把O(nWc)降到O(nW log c)。代码长这样int knapsackMultiple(int W, const vectorint w, const vectorint v, const vectorint c) { vectorint nw, nv; for (int i 0; i (int)w.size(); i) { int cnt c[i]; for (int k 1; cnt 0; k 1) { int take min(k, cnt); nw.push_back(w[i] * take); nv.push_back(v[i] * take); cnt - take; } } vectorint dp(W 1, 0); for (int i 0; i (int)nw.size(); i) { for (int j W; j nw[i]; --j) { dp[j] max(dp[j], dp[j - nw[i]] nv[i]); } } return dp[W]; }这里最需要注意的就是拆分循环里的边界k 1 可能会溢出尤其是c特别大的时候。我用int写一般没问题但习惯上会在while循环里写成 k cnt 这种形式免得k翻倍后溢出变成负数最后死循环。这个问题我真实遇到过真的会让人想砸键盘。多重背包还能用单调队列优化到O(nW)但那个写起来很长初学者如果只是应付面试和常规刷题二进制拆分已经够用。只有遇到c非常大的极限题才需要上单调队列我自己的建议是先把二进制拆分写熟不要贪多。3.3 关于完全背包和多重背包的混合还有一个常见的“混合背包问题”就是有的物品只能取一次有的可以取无限次有的最多取c[i]次。解法其实不神秘把0/1背包看作c1的多重背包完全背包看作c很大的多重背包然后用多重背包的二进制拆分统一处理。不过更直接的做法是逐个物品判断如果是0/1就倒序更新如果是完全就正序更新如果是多重就拆成0/1再倒序更新。这个在实际题目里偶有出现掌握三者的核心区别后就不难。4. 背包问题的几个进阶变形恰好装满、最小价值、方案数4.1 “恰好装满”的-inf初始化很多题不是问“容量不超过W的最大价值”而是“恰好装满容量W的最大价值”。这时候如果还用dp数组初始化为0会出现一个很隐蔽的错误背包没装满也算一种“合法状态”最终结果可能把“没装满但价值高”的方案当作答案。解决办法是把dp数组初始化为负无穷比如-1e9只有dp[0]0。转移的时候如果dp[j-w[i]]是负无穷说明这个状态不可达不能用来转移。最终判断dp[W]是否为负无穷如果是说明无法凑出恰好装满的情况。int knapsack01_exact(int W, const vectorint w, const vectorint v) { const int NEG -1e9; vectorint dp(W 1, NEG); dp[0] 0; for (int i 0; i (int)w.size(); i) { for (int j W; j w[i]; --j) { if (dp[j - w[i]] ! NEG) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } } return dp[W] NEG ? -1 : dp[W]; }这个负无穷初始化技巧在动态规划里特别常用。不只是背包很多“必须满足某个严格条件”的DP题都要这么干。比如最短路径里的“恰好经过k条边”本质上也是用这种不可达标记。4.2 求方案数时物品循环与容量循环的顺序背包还能用来求方案数比如“有多少种方式把容量W装满”。这时dp[j]表示容量j有多少种凑法转移变为dp[j] dp[j-w[i]]。但这里有个经典陷阱如果你想统计的是组合数也就是不考虑物品选取顺序必须先枚举物品再枚举容量如果你想统计的是排列数比如把物品看成可以按任意顺序放入就得先枚举容量再枚举物品。我以前写过一个小例子来说明容量3物品重量分别是1和2。组合数视角下只有两种方案12和21算同一种所以答案是2排列数视角下12和21算两种答案就变成3。这取决题目描述里是否强调顺序。背包经典模型一般是组合数所以物品循环在外层容量循环在内层如果你看到“序列”“排列”这类字眼就要警惕是不是应该反过来。4.3 二维背包与分组背包再进阶一点的是二维背包每件物品有两个维度的限制比如体积和重量背包容量也有两个上限。这时候dp要开成二维数组dp[i][j]表示体积为i、重量为j时的最大价值。转移的时候两层容量循环都分别按0/1背包的方式倒序枚举即可。分组背包则是把物品分成若干组每组最多取一个。经典例题听起来像每个组里的物品互斥比如手机套餐只能三选一。处理方法是在组外先枚举容量组内再枚举物品或者反过来组内枚举物品外层枚举容量具体顺序需要根据一维数组是否被污染来判断。我自己更推荐的做法是按“组 - 容量倒序 - 组内物品”的顺序这样每一步都在用上一组的旧状态不会串组。这几个变形不是独立的知识点它们共同说明一件事背包问题的核心是“状态怎么定义”和“枚举顺序怎么设计”。你把这个想明白了换多少层限制都不怕。5. 我实操中踩过的坑与排查技巧5.1 数组开小、下标错位、多组数据不清零我在刷背包相关题目和平时写算法demo时真实踩过的坑可以整理成一个速查表每一格都是血泪教训。坑现象排查与解决数组开成W而不是W1容量正好是W时越界或漏算所有dp数组一律开W1养成肌肉记忆物品下标从1开始但vector从0开始转移时w[i]取错要么手动把vector前面补一个0要么统一用i-1多组测试数据没有重新初始化dp第二组数据结果莫名变大在每组输入前重新fill或重新构建vector容量循环起始条件写错0/1背包写成jw[i]正序导致无限取0/1背包记“倒序”完全背包记“正序”数据大但用了int累加价值时溢出成负数dp和v、w统一用long long除非确定范围下标错位那个问题我特别有感触。有一次我写二维版本直接拿1到n作为物品循环单位又忘记在w数组前面补一个0结果w[i]取到的是下一件物品的重量答案怎么跑都是错的。排查半天最后发现只是下标差一位。后面我的习惯是如果代码里使用1-based下标就在读入后统一做w.insert(w.begin(), 0)和v.insert(v.begin(), 0)让下标对上不给自己添堵。5.2 用long long收底以及能提前break就break还有一个很多人忽视的细节是数据范围。如果W能到1e5物品价值能到1e9那dp数组里的累加值很容易超过2^31-1。我第一次没注意跑出来负数还以为是思路错折腾了很久才发现是int溢出。从那以后凡是和“价值最大化”沾边的DP题我默认用long long。这不是炫技就是省心。另外如果物品重量已经超过W或者价值为0这类物品在转移时没有任何正向作用。我写0/1背包的时候会先做一次过滤把重量为0且价值不为0的物品单独处理掉再参与DP。重量为0但价值为正的物品理论上可以无限白拿但这个属于特殊边界很多题不会出出了就要仔细读题看清楚能不能拿0重量物品。能提前break的地方也要用起来。比如完全背包里如果某一轮物品循环结束后dp数组完全没有变化说明后面的物品都不可能再产生新贡献可以直接跳出。这个优化不是必须的但遇到W特别大的极限数据时能救你一命。5.3 怎么debug转移方程动态规划代码的debug比普通代码难因为很多时候不是编译错误而是“答案差一点”。我自己的debug步骤是这样第一步先把一维DP改成二维DP跑一遍标准样例。二维版本逻辑直观容易确认是不是思路本身错了。第二步如果二维版本对那就说明是空间优化或枚举顺序的锅。重点检查内层循环是正序还是倒序以及起始条件是不是w[i]。第三步用纸笔手动模拟一个很小的数据逐步打印dp数组的中间过程。我也经常直接在代码里加上打印语句把每次外层循环结束后的dp数组打印出来看dp[W]是怎么一步步变大的。这一步效率极高往往一眼就能看出问题。第四步如果还是不对检查边界。容量为0、只有一件物品、所有物品重量都大于W这些极端情况最容易暴露“恰好装满”和“不超过容量”的思路混淆。6. 背包问题还能用在哪不只是刷题6.1 资源分配、预算、装箱很多人觉得背包问题只活在面试和竞赛里实际工作用不上。我不这么看。日常开发里“在有限的预算/资源下组合出最大价值”的场景比比皆是。比如给你一个服务器预算要在各种配置方案里选组合让总性能分最高这就是一个典型的0/1背包比如优惠券叠加方案每个商品可以用多张券券的总面值有上限想最大化优惠这就是完全背包或者多重背包的变体再比如物流装箱一个车有载重限制要在多个货物里选一批让总价值最大也是背包。虽然业务代码里你可能不会真去写一个叫knapsack的函数但算法思路能帮你把需求抽象成“资源、成本、价值”三个要素然后直接套模板。还有一类题是“最小重量达到目标价值”本质是把价值和重量对调后的背包问题。这类题我在做实际需求时也遇到过要求在预算约束下购买设备让总性能达标。写的时候只要把“容量”和“价值”的定义换一下状态转移几乎没有区别。6.2 背包思路作为动态规划的思维基石背包问题的价值还体现在它是理解更复杂DP问题的跳板。比如很多树形DP题先递归到叶子节点然后用“背包合并”的方式把子树的dp数组合并到父节点这就是“树上背包”只不过物品之间的依赖关系变成了父子关系。又比如区间DP里有一些题也是把大区间拆成子区间再合并和背包的状态转移逻辑很像。再比如状态压缩DP里经常用“选哪些物品”的位掩码来做集合转移背包的dp定义思路可以直接平移过去。我特别喜欢把背包问题叫做“动态规划的Hello World”。它不像数学题那么玄乎靠背板也能得分但真正理解它之后你会建立一种条件反射凡是题目里出现“容量、上限、选择物品、最大化/最小化某个指标”第一反应就是构建dp数组然后思考枚举顺序和边界。6.3 最后分享一个我常用的模板与体会把自己常用的模板总结成代码块放在最后方便直接抄// 0/1背包通用模板w、v下标从0开始 #include bits/stdc.h using namespace std; int main() { int n, W; cin n W; vectorint w(n), v(n); for (int i 0; i n; i) cin w[i] v[i]; vectorlong long dp(W 1, 0); for (int i 0; i n; i) { for (int j W; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[W] \n; return 0; }如果要改成完全背包把内层循环变成for (int j w[i]; j W; j)。如果要改成恰好装满把dp初始化的0改成NEG并让dp[0]0。这三处改动基本覆盖了绝大多数背包入门题。我个人在实际操作中的体会是先理解为什么0/1背包要倒序再机械记忆模板这样即使紧张也能写对。倒序和正序我原来也总记混后来给自己编了个口诀“0/1往左走完全往右走”。意思是0/1背包容量从右往左降完全背包容量从左往右升。每次写完检查一遍循环方向就能避开最经典的错误。多练几道经典题之后你会发现背包问题只是包装吓人内在逻辑一旦通了反而是所有动态规划题型里最有把握的一类。