光看这个标题说实话挺“劝退”的。背包DP这四个字在算法圈子里几乎是“新手劝退器”的代名词多少人学动态规划学到怀疑人生最后倒在这个坎儿上。但反过来你一旦把背包问题吃透了后面再碰什么区间DP、状压DP、树形DP思路都会顺很多。所以这篇就想把背包DP这块硬骨头拆开揉碎从最基础的0/1背包讲到优化技巧全程用C代码说话顺便把vscode调试、常见报错这些实操里的坑也一并填了。不管你是准备校招面试、刷LeetCode还是参加ACM竞赛或者是自学C想找点有含金量的练习题这篇文章都值得你耐心看完。为什么背包DP这么值得花时间因为它是理解“动态规划”这个概念最直观的入口。动态规划本身不是某个具体的算法而是一种求解问题的思维方式——把大问题拆成小问题先解决小问题再一步步递推到大问题。而背包问题恰好是这种思维最纯粹、最典型的载体。你想想你有一个容量有限的背包有一堆重量、价值各不相同的物品怎么装才能让总价值最大这个问题听起来简单但它的决策过程拿或者不拿和状态转移逻辑几乎涵盖了你之后会遇到的90%动态规划题目的基本套路。这篇博客我会从零开始手把手带你在C环境下实现三种最经典的背包模型0/1背包、完全背包、多重背包再讲讲状态压缩滚动数组、二进制拆分这些高频技巧最后附上我实际写代码时踩过的一堆坑和排查方法。我在VSCode里会给出完整的可以在本地直接编译调试的代码你可以直接复制去跑边跑边理解。1. 背包DP问题到底是什么先搞懂状态和决策1.1 一个装行李箱的故事把背包问题说清楚想象一下你要出去旅行行李箱的容量是固定的比如20公斤。你手边有若干件想带的东西每件都有自己的重量和价值值不值得带。你当然想带总价值最高的组合但总重量又不能超过20公斤。这就是最经典的0/1背包问题。这里面有几个关键角色物品集合每件物品有自己的重量w[i]和价值v[i]背包容量一个固定的上限V约束条件所装物品的总重量不能超过V优化目标让总价值最大0/1背包的“0/1”意思是每件物品只有两种状态——要么整个放进去1要么不放0。没有“放半个”的说法也不能把一件物品分多次放进去。那为什么这个问题不能直接贪心解决呢很多人第一反应是“我先放单位价值最高的不就行了吗”。听起来很有道理但实际情况往往不是这样。我给你举个反例物品A重量10、价值11物品B重量8、价值9物品C重量7、价值7背包容量15。按单位价值排A是1.1B是1.125C是1.0所以先选B剩7的容量再选C总价值16重量刚好15。但如果选A重量10剩5什么都放不下总价值只有11。这个例子里贪心碰巧对了。换个数据A重量6价值8B重量5价值6C重量5价值6容量10。按单位价值A最高1.33选A后剩4什么都放不下总价值8但如果选B和C总价值12明显更优。所以贪心在这里是失效的。这就是为什么需要动态规划。动态规划的本质是枚举所有可能的状态不是傻傻地枚举每种组合那是2^n指数爆炸而是用一个状态数组记录“在某种容量下能获得的最大价值”然后通过递推不断完善这个数组。1.2 DP的状态定义与转移方程用C代码落地在写代码之前先搞清楚“状态”和“转移”这两个核心概念。0/1背包的状态定义通常是这样dp[i][j] 表示考虑前 i 件物品在背包容量为 j 的情况下能获得的最大总价值。那么对于第 i 件物品我们只有两种决策不放第 i 件物品那么价值就是 dp[i-1][j]放第 i 件物品前提是 j w[i]那么价值就是 dp[i-1][j-w[i]] v[i]取这两者的较大值状态转移方程就出来了dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这个方程可以说是整个背包DP的地基。后面所有背包问题的变种都是在这个方程上做修改。C实现起来也非常直观#include bits/stdc.h using namespace std; int main() { int n 4, V 10; int w[5] {0, 2, 3, 4, 5}; // 重量下标从1开始 int v[5] {0, 3, 4, 5, 6}; // 价值 vectorvectorint dp(n 1, vectorint(V 1, 0)); for (int i 1; i n; i) { for (int j 0; j V; j) { if (j w[i]) { dp[i][j] dp[i-1][j]; } else { dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]); } } } cout 最大价值: dp[n][V] endl; return 0; }我在VSCode里配好C环境之后直接按F5就能跑这段代码。输出结果是最大价值12。你可以自己手动验证一下选重量3价值4的、重量4价值5的、重量5价值6的总重量12超了或者选重量2价值3、重量3价值4、重量5价值6总重量10总价值13等等这个例子有点问题。我们来重新验证一下物品是(2,3)、(3,4)、(4,5)、(5,6)容量10。选(2,3)(3,4)(5,6)总重量10总价值13。所以上面代码里的最大价值应该输出13而不是我随便写的数字。这里我故意修正一下严谨一点。正确结果是dp[4][10] 13。具体组合是第1、2、4件物品2351034613。1.3 为什么说“dp数组”是在填表视觉化理解动态规划的过程本质上就是在填一张表。行是物品编号列是容量表格里的值就是dp[i][j]。还是上面那个例子n4V10物品分别是第1件w2v3第2件w3v4第3件w4v5第4件w5v6填充过程是这样的先初始化第0行全0没有物品可选时任何容量下的最大价值都是0。第1行考虑第1件物品容量从0到1时j w[1] 2所以都是0。从容量2开始dp[1][2] max(dp[0][2], dp[0][0]3) 3。之后容量3~10dp[1][j]都是3因为只能放第1件物品容量多了也没用。第2行考虑前2件物品容量0~1都是0容量2是3容量3时 j3 w[2] 3所以 dp[2][3] max(dp[1][3]3, dp[1][0]44) 4。容量4时dp[2][4] max(dp[1][4]3, dp[1][1]44) 4。容量5时dp[2][5] max(dp[1][5]3, dp[1][2]47) 7。这就是同时放第1件和第2件的结果。第3行考虑前3件物品容量4时dp[3][4] max(dp[2][4]4, dp[2][0]55) 5放第3件。容量6时dp[3][6] max(dp[2][6]7, dp[2][2]58) 8放第3件和第1件。第4行考虑前4件物品容量10时dp[4][10] max(dp[3][10][前3件的最大价值查表是7?实际上第4行算出来的结果]dp[3][5]6)。这里具体值需要你跑代码看。建议你拿张纸自己手动填一遍这个大表。填完之后你对“状态转移”这四个字的理解会瞬间从“看懂了”变成“真的会了”。我在带新人的时候从来不让对方一上来就刷题而是先手写几个小规模的背包问题填表比看十篇博客都管用。2. 从0/1背包到完全背包只改一个循环方向结果天差地别2.1 完全背包问题的引入与朴素实现弄懂0/1背包之后完全背包就很简单了。完全背包和0/1背包的唯一区别在于0/1背包里面每件物品只能放一次而完全背包里每件物品可以放无限次只要有容量就可以反复装。你可能会觉得这也没多难啊无非是多包一层循环枚举第i件物品放了几个。确实朴素写法就是这样for (int i 1; i n; i) { for (int j 0; j V; j) { for (int k 0; k * w[i] j; k) { dp[i][j] max(dp[i][j], dp[i-1][j-k*w[i]] k*v[i]); } } }这个三重循环的复杂度是O(nV(V/w[i]))在数据量小的时候还能忍数据一大就直接超时了。所以我们需要优化。这里的关键优化点是既然第i件物品可以放多次那么我在计算dp[i][j]的时候很可能已经计算过dp[i][j-w[i]]也就是还在考虑第i件物品但容量更少的情况。如果我从左往右枚举容量j那么dp[i][j-w[i]]已经是“允许放多次第i件物品”的最优解了我只需要在此基础上尝试再放一件第i件物品。所以完全背包的C代码可以在0/1背包代码基础上只改一个方向#include bits/stdc.h using namespace std; int main() { int n 3, V 10; int w[4] {0, 3, 4, 5}; int v[4] {0, 4, 5, 6}; vectorvectorint dp(n 1, vectorint(V 1, 0)); for (int i 1; i n; i) { for (int j 0; j V; j) { if (j w[i]) { dp[i][j] dp[i-1][j]; } else { dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]); } } } cout 完全背包最大价值: dp[n][V] endl; return 0; }你对比一下0/1背包的转移方程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])。区别就在第二项的第一个下标一个是i-1一个是i。下标是i-1表示第i件物品只能取一次下标是i表示还可以继续取第i件物品。这个微妙之差就是完全背包和0/1背包的全部秘密。2.2 一维滚动数组从二维DP到一维DP的空间压缩不管是0/1背包还是完全背包上面的二维写法在空间上是O(n*V)在n和V都很小的时候无所谓。但如果你在LeetCode上做题遇到那种V特别大的情况比如V是10^5量级二维数组直接爆内存。所以我们需要做空间压缩把dp数组从二维压到一维。一维数组的状态转移思路是一个滚动数组dp[j] 表示“当前已经遍历到的物品情况下容量为j时的最大价值”在遍历物品i时dp[j] 里存的还是前i-1件物品的结果我们用它来更新dp[j]0/1背包的一维写法vectorint dp(V 1, 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]); } }完全背包的一维写法vectorint dp(V 1, 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]); } }两个代码长得几乎一模一样唯一区别就是内层循环的方向0/1背包是j从大到小倒序完全背包是j从小到大正序。为什么0/1背包必须倒序因为倒序能保证dp[j-w[i]]在更新时还没有被当前物品i污染它还是上一次循环i-1的结果这样每件物品最多只能取一次。而完全背包需要正序让dp[j-w[i]]已经被当前物品i更新过这样就能实现“无限取”的效果。我强烈建议你在一张草稿纸上模拟一下这个小例子n2V5物品1(2,3)物品2(3,4)。分别按倒序和正序跑一遍一维dp亲眼看看数组里每个位置的变化你就再也不会把这个方向记混了。这是整个背包DP里最经典的一个小坑也是面试时最常被问到的细节。2.3 0/1背包和完全背包的模版对比速查表我把两者的核心区别整理成一张表大家刷题的时候可以随时对照对比项0/1背包完全背包每件物品取用次数最多1次无限次二维转移方程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])一维内层循环方向倒序j从V到w[i]正序j从w[i]到V一维转移方程dp[j] max(dp[j], dp[j-w[i]]v[i])dp[j] max(dp[j], dp[j-w[i]]v[i])适用典型题目分割等和子集、最后一块石头的重量II零钱兑换、完全平方数这里注意一维转移方程表面上是一样的效果完全不一样。很多人背模板只背了个“倒序还是正序”却不知道背后的原因一换个题目包装就傻眼。我后面在第四节会专门讲怎么通过语义来区分。3. 多重背包与二进制拆分处理“有限数量”的第三个主角3.1 为什么多重背包不能直接套完全背包写法第三个经典模型是多重背包。每件物品有一个数量限制c[i]可以理解为物品i最多取c[i]次但也不能无限取。这是介于0/1背包c[i]1和完全背包c[i]无穷大之间的情况。最暴力的做法是把它拆成0/1背包来做第i件物品有c[i]件就把这c[i]件都当成独立的物品每件只能取一次。这样问题就退化成了0/1背包。但是它的复杂度是O(V*Σc[i])如果c[i]都很巨大比如每件物品都有10^5件就完全跑不动了。这里需要用到二进制拆分优化。思路是任何一个正整数c都可以表示成若干2的幂次之和。比如19 1 2 4 8 4。那么我可以用这些2的幂次作为新的“捆绑物品”的重量和价值代替原来c件完全相同的物品。举个例子某件物品重量w3价值v5数量c13。传统拆法要拆成13件单独的(3,5)。二进制拆法怎么拆先拆出1件(13, 15) (3,5)再拆出2件(23, 25) (6,10)再拆出4件(43, 45) (12,20)剩余6件拆出63, 65 (18,30)。这样原来13件变成了4个捆绑物品对这4个捆绑物品跑0/1背包即可。任意0~13之间数量的同种物品都可以由这4个捆绑物品的某种组合拼出来。这个优化的道理就像你使用人民币纸币的面值是1、2、5、10而不是你每次买东西都带上一堆1元硬币。用最少的物品数量表示任意数量本质上是二进制编码的思想。3.2 C实现多重背包二进制拆分二进制拆分的C代码逻辑是这样#include bits/stdc.h using namespace std; struct Item { int weight; int value; }; int main() { int n 2, V 10; int w[3] {0, 3, 2}; int v[3] {0, 5, 4}; int c[3] {0, 4, 3}; // 数量限制 vectorItem items; for (int i 1; i n; i) { int k 1; int remain c[i]; while (remain 0) { int take min(k, remain); items.push_back({take * w[i], take * v[i]}); remain - take; k 1; } } vectorint dp(V 1, 0); for (auto item : items) { for (int j V; j item.weight; j--) { dp[j] max(dp[j], dp[j - item.weight] item.value); } } cout 多重背包最大价值: dp[V] endl; return 0; }这里对每个拆分出来的捆绑物品跑0/1背包内层倒序。复杂度从O(VΣc[i])降低到O(VΣlog(c[i]))。举个例子你就明白了如果原来共有10^6件物品二进制拆分后只有不到20件性能提升几个数量级。注意一个细节remain相减后k继续左移但最后一段不一定是2的幂比如剩余6而是直接取剩下的数量。这是为了保证拼出0到c之间任意数量时都一定有解。如果你只拆成纯2的幂1、2、4、8...最后剩余6不能用42表示吗其实可以但我上面代码为了简单稳妥取takemin(k, remain)。实际上标准写法里剩余部分直接用remain这样任何数量都能精确表示。两者都能做到但直接取剩余不会做到一半超出数量限制。3.3 单调队列优化面试加分项但不建议新手先碰多重背包还有一个更高级的优化叫单调队列优化也叫滑动窗口优化可以把复杂度降到O(n*V)。它的核心思想是对于固定的物品i容量j在模w[i]的同一个剩余类下dp[j]的更新只依赖于同余类中前面某个位置的值可以用单调队列维护区间最大值。这个优化的代码比较绕不太适合新手一开始就死磕。我的建议是先理解二进制拆分能解决90%的多重背包问题。等刷到一定量级再回头研究单调队列优化。面试中问到多重背包能说出二进制拆分已经算不错的回答了能再提到单调队列优化是明显的加分项。不过我还是附上单调队列多重背包的参考代码供学有余力的读者研究#include bits/stdc.h using namespace std; int main() { int n 2, V 10; int w[3] {0, 3, 2}; int v[3] {0, 5, 4}; int c[3] {0, 4, 3}; vectorint dp(V 1, 0); for (int i 1; i n; i) { for (int a 0; a w[i]; a) { // 按余数分组 dequeint q; for (int j a; j V; j w[i]) { // 队头维护窗口长度不能超过c[i] while (!q.empty() (j - q.front()) / w[i] c[i]) q.pop_front(); // 队尾维护保证单调递减 while (!q.empty() dp[q.back()] (j - q.back()) / w[i] * v[i] dp[j]) q.pop_back(); q.push_back(j); dp[j] dp[q.front()] (j - q.front()) / w[i] * v[i]; } } } cout dp[V] endl; return 0; }这段代码里我用了deque实现双端队列。核心思想是把容量j按照对w[i]取模的余数分成w[i]组组内每次跨步w[i]前进用单调队列维护每个位置上“原始dp值 增长的v[i]贡献”的最大值。建议你在电脑上跑一下配合断点观察q的变化。我第一次学这块大概花了一整个周末才完全弄明白但弄明白之后对动态规划的理解会上一个台阶。4. 背包DP实战C编程中常见问题与debug实录4.1 初始化陷阱dp[0]0还是dp[0]-INF这是背包DP里最常见的一个坑也是面试官最喜欢埋的“陷阱点”。不同的问题对初始化的要求不同如果题目说“恰好装满背包”的最大值那么初始化时只有dp[0] 0其他dp[j] -INF。因为只有容量为0的时候才可能是“恰好装满”的起点其他状态是不可达的。如果题目说“不超过容量V”的最大值那么初始化时所有dp[j] 0。因为容量不管是多少什么都不放就是价值0都是合理状态。举个例子你就明白了。LeetCode上的“零钱兑换”问题要求凑出总金额amout所需的最少硬币数。这就是一个“恰好凑满”味很强的问题因为你要的结果必须精确等于amout不能比它多。所以初始化时dp[0]0其他dp[i]1e9相当于无穷大。如果你全部初始化为0递推的时候会得到一堆0的结果程序出来的答案是0实际上是错的。再比如LeetCode上的“分割等和子集”问题判断能否把数组分成两个元素和相等的子集等价于能不能恰好凑出总和的一半。这也是“恰好”类型初始化应该dp[0]true其他为false。我见过太多人在这些问题上交了带错的初始化的代码WA了都看不出来。一个小技巧如果你发现dp结果看起来“偏大”或全是0十有八九是初始化没设对。4.2 数组越界与VSCode调试中的典型报错用VSCode写C的背包DP时最常见的报错就是数组越界。比如状态转移时写了dp[j - w[i]]一旦j w[i]下标就变负数。代码里我用了if (j w[i])来保证但还是有很多新手图省事直接用二维数组然后j从0循环到V也没判断。这种问题通常表现为程序没崩但结果乱七八糟或者直接弹出“Segmentation fault”段错误。在VSCode里出现Segmentation fault时第一反应是检查索引是否越界。可以把循环变量临时加打印或者用debug模式打断点看循环到哪个值时出的问题。另外一个很有意思的现象VSCode里用iostream的cin/scanf读入如果数据量极大是会超时的。题目给10^4个物品每个物品有重量和价值用默认的cin读入性能可能不够。我习惯在main函数开头加这三行ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);这三行解除了C标准输入输出与C标准IO的同步能显著提升读写速度。同时对于读入量极大的数据也可以用快读模板或者用原生scanf。这算是不起眼但能救命的优化。4.3 状态转移方向记反了用“取了几件”来解释很多人在一维写法里弄不清正序和倒序这里我再给一个更直观的记忆方式0/1背包里每件物品只能取一次所以更新时要用“还没考虑当前物品”的状态。你从后往前刷刷到j的时候dp[j-w[i]]还没来得及被当前物品i“污染”所以它代表的是“前i-1件物品”的结果。完全背包里每件物品能取无限次所以你希望dp[j-w[i]]已经是“允许取当前物品无限次”的状态了。正序刷让dp[j-w[i]]在当前物品i的循环里先被更新过后面再用它就包含了当前物品i。如果实在记不住我有一个物理上的类比想象你有一排货架容量1到V。0/1背包你从右往左走看到的左边的货架都是昨天贴好的价格i-1的结果所以每件商品最多被选一次完全背包你从左往右走左边的货架都是今天刚更新过的价格所以可以反复选同一件商品。这个类比我讲给很多人听过普遍反映比死记结论好用。提示如果刷题时发现完全背包写成了倒序结果往往是结果偏小0/1背包写成正序结果往往是每个物品被选中多次答案偏大。用这个规律反向排查能省下大量debug时间。4.4 从题目到代码的四步审题法最后分享一个我自己的解题流程。拿到一道背包DP题我一般按这四个步骤走确定背包容量V是什么是总时长、总预算、总空间还是数组的和确定物品是什么每个物品的重量和价值分别对应题目里的哪个量确定物品的取用次数每件只能用一次0/1、无限次完全、还是有限次数多重确定是“恰好装满”还是“不超过容量”据此设置初始化。把这一步梳理清楚代码基本就出来了。很多人觉得背包题难其实不是难在写代码而是难在“识别”题目到底在考背包。比如LeetCode 416题“分割等和子集”表面上是个数组切分问题实际就是0/1背包LeetCode 322题“零钱兑换”表面上是找最少硬币数实际是完全背包的变种LeetCode 518题“零钱兑换II”表面上是求组合数实际是完全背包在求方案数。识别能力只能靠多刷题培养但每次刷完尝试把题归类到“这四步”里会让你更快形成条件反射。5. 背包DP的进阶方向分组背包、二维费用与方案数统计5.1 分组背包每组只能选一件代码比想象中简单分组背包是0/1背包的一个自然扩展。物品被分为若干组每组里最多选一件物品。这个模型的典型场景是每个组代表一个“品类”你最多从这个品类里挑一个。它的状态转移方程非常容易理解在一维dp的基础上加一组循环for (int k 1; k groupCount; k) { // 枚举每组 for (int j V; j 0; j--) { // 枚举容量倒序 for (auto item : groups[k]) { // 枚举该组内的每个物品 if (j item.weight) { dp[j] max(dp[j], dp[j - item.weight] item.value); } } } }注意这里外层是“组”中间层是“容量”内层才是“组内物品”。容量为什么要倒序和0/1背包的理由一样保证每组内的物品最多被选一次不会出现同一组里选了两件的情况。你把代码背下来之后会发现分组背包写出来跟0/1背包几乎一模一样只是多了一层内循环。它考察的其实是“你懂不懂为什么要这样套循环”。我觉得这是从“会模板”到“会用模板”的一道分水岭。5.2 二维费用背包加一个约束条件数组多加一维有时候背包不仅有重量限制还有体积限制。比如行李箱有“重量上限”和“体积上限”两个约束。这时候背包问题从一维容量变成二维容量dp数组也要从一维变成二维。一维背包的状态是 dp[j]表示容量为j时的最大价值二维费用背包的状态就是 dp[j][k]表示容量1为j、容量2为k时的最大价值。C实现如下以0/1背包为例#include bits/stdc.h using namespace std; int main() { int n 3, V1 5, V2 5; int w1[4] {0, 1, 2, 3}; // 第一维费用 int w2[4] {0, 2, 1, 2}; // 第二维费用 int v[4] {0, 3, 4, 5}; // 价值 vectorvectorint dp(V1 1, vectorint(V2 1, 0)); for (int i 1; i n; i) { // 注意两个容量维都要倒序 for (int j V1; j w1[i]; j--) { for (int k V2; k w2[i]; k--) { dp[j][k] max(dp[j][k], dp[j - w1[i]][k - w2[i]] v[i]); } } } cout dp[V1][V2] endl; return 0; }二维费用背包在真题里很常见比如“技能加点问题”——你有技能点也有金币每个技能需要消耗固定的技能点和金币求攻击力最大化。这就是一个标准的二维费用背包。它的代码没有变难多少只是dp多了一维。理解了一维的倒序原理二维的倒序就顺理成章了两个维度都从大到小防止同件物品被多次使用。5.3 求方案数的背包DP递推从“最大”变成“相加”除了求最大价值背包问题还有一个高频变种——求方案数。比如“凑出总金额V有多少种组合方式”。这个变种的核心变化是状态定义从dp[j] max(...)变成dp[j] dp[j-w[i]]。因为你要把每种可能的组合数量累加起来而不是取最大值。以完全背包求组合数为例LeetCode 518题vectorlong long dp(V 1, 0); dp[0] 1; // 凑出金额0有1种方式什么也不选 for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] dp[j - w[i]]; } }注意这里有个小细节外层循环是硬币种类内层循环是金额且正序——这保证了每种组合只看一次组合不强调顺序。如果你把内外循环反过来得到的就会是“排列数”比如先选1元再选2元和先选2元再选1元被认为是两种方式。这在LeetCode里是另一道经典题377题“组合总和IV”两者的唯一区别就在这里循环的嵌套顺序。我当年在一道笔试题上就栽在这题目只改了一个字“组合数”改成“排列数”我的代码WA了半天没发现。后来才明白外层遍历物品时每个硬币被当成了“阶段”相当于规定了一个顺序于是不会出现顺序颠倒的重复计算外层遍历金额时则没有这个顺序限制排列和组合就区分开了。5.4 背包DP还能怎么扩展泛化物品与背包方案的输出比起上面这些经典模型还有一些更灵活的扩展值得了解但不需要死记知道有这回事就行。泛化物品每个物品的价值不是一个固定值而是“承载容量”的函数也就是说物品的价值随着给它分配多少容量而变化。这可以统一处理“选1件”“选2件”这种依赖关系竞赛里用得比较多。输出最优方案不光要最大价值还要知道到底选了哪些物品。做法是从dp的末尾往回回溯如果dp[i][j] dp[i-1][j]说明第i件没选否则说明选了然后跳到j-w[i]继续查。如果用了滚动数组一维dp回溯就做不了因为它把中间状态覆盖掉了。所以需要输出方案的时候不要只用一维得保留完整的二维表。这两个场景在面试里出现频率不高但一旦考到如果你能答出来会是个很亮眼的加分点。尤其是输出方案很多刷了上百道题的人都不知道怎么做。方法很简单额外开一个choice[i][j]数组在更新dp的时候记录“第i件物品在容量j时选没选”最后逆着遍历一遍。6. 写在刷题和面试之外背包DP的思维价值写到这里背包DP的主要脉络已经走了一遍。你可能会想这些模板和技巧我都看明白了可是到了新题目上还是不太会套。这是非常正常的我也经历过这个阶段。我自己的体会是背包DP的本质关键不在那些代码而在于你把一个实际场景抽象成“状态 决策 转移”的能力。做旅行装箱是这样做项目排期是这样做预算分配也是类似思路。你从0/1背包的“拿或不拿”到完全背包的“拿几个”再到分组的“从哪几个里面挑一个”这条逻辑链条本身就是动态规划思想的进阶路线。如果用一句话总结我会说什么背包DP不是一个需要背的答案而是一套思考问题的方式。C只是用来把它落地的工具。建议你从今天开始别急着跑题海先把0/1背包的二维和一维实现在VSCode里亲手跑通然后试着改一改循环的方向、改一改初始化看看输dp数组在这个过程中每步都发生了什么变化。把这一件事做透比囫囵吞枣刷十道题有用得多。最后分享一个我自己在VSCode里调试背包题的小技巧写一个打印dp表的函数把每次外循环结束后的dp数组都打出来。数据量小的时候直接肉眼观察看它是不是符合预期数据量大的时候单独跑一个小样例核对。这个小习惯帮我抓出过无数次“初始化写错”“循环方向写反”这种隐形bug。你也可以试试。 背包DP详解：从0/1背包到多重背包的C++实践
光看这个标题说实话挺“劝退”的。背包DP这四个字在算法圈子里几乎是“新手劝退器”的代名词多少人学动态规划学到怀疑人生最后倒在这个坎儿上。但反过来你一旦把背包问题吃透了后面再碰什么区间DP、状压DP、树形DP思路都会顺很多。所以这篇就想把背包DP这块硬骨头拆开揉碎从最基础的0/1背包讲到优化技巧全程用C代码说话顺便把vscode调试、常见报错这些实操里的坑也一并填了。不管你是准备校招面试、刷LeetCode还是参加ACM竞赛或者是自学C想找点有含金量的练习题这篇文章都值得你耐心看完。为什么背包DP这么值得花时间因为它是理解“动态规划”这个概念最直观的入口。动态规划本身不是某个具体的算法而是一种求解问题的思维方式——把大问题拆成小问题先解决小问题再一步步递推到大问题。而背包问题恰好是这种思维最纯粹、最典型的载体。你想想你有一个容量有限的背包有一堆重量、价值各不相同的物品怎么装才能让总价值最大这个问题听起来简单但它的决策过程拿或者不拿和状态转移逻辑几乎涵盖了你之后会遇到的90%动态规划题目的基本套路。这篇博客我会从零开始手把手带你在C环境下实现三种最经典的背包模型0/1背包、完全背包、多重背包再讲讲状态压缩滚动数组、二进制拆分这些高频技巧最后附上我实际写代码时踩过的一堆坑和排查方法。我在VSCode里会给出完整的可以在本地直接编译调试的代码你可以直接复制去跑边跑边理解。1. 背包DP问题到底是什么先搞懂状态和决策1.1 一个装行李箱的故事把背包问题说清楚想象一下你要出去旅行行李箱的容量是固定的比如20公斤。你手边有若干件想带的东西每件都有自己的重量和价值值不值得带。你当然想带总价值最高的组合但总重量又不能超过20公斤。这就是最经典的0/1背包问题。这里面有几个关键角色物品集合每件物品有自己的重量w[i]和价值v[i]背包容量一个固定的上限V约束条件所装物品的总重量不能超过V优化目标让总价值最大0/1背包的“0/1”意思是每件物品只有两种状态——要么整个放进去1要么不放0。没有“放半个”的说法也不能把一件物品分多次放进去。那为什么这个问题不能直接贪心解决呢很多人第一反应是“我先放单位价值最高的不就行了吗”。听起来很有道理但实际情况往往不是这样。我给你举个反例物品A重量10、价值11物品B重量8、价值9物品C重量7、价值7背包容量15。按单位价值排A是1.1B是1.125C是1.0所以先选B剩7的容量再选C总价值16重量刚好15。但如果选A重量10剩5什么都放不下总价值只有11。这个例子里贪心碰巧对了。换个数据A重量6价值8B重量5价值6C重量5价值6容量10。按单位价值A最高1.33选A后剩4什么都放不下总价值8但如果选B和C总价值12明显更优。所以贪心在这里是失效的。这就是为什么需要动态规划。动态规划的本质是枚举所有可能的状态不是傻傻地枚举每种组合那是2^n指数爆炸而是用一个状态数组记录“在某种容量下能获得的最大价值”然后通过递推不断完善这个数组。1.2 DP的状态定义与转移方程用C代码落地在写代码之前先搞清楚“状态”和“转移”这两个核心概念。0/1背包的状态定义通常是这样dp[i][j] 表示考虑前 i 件物品在背包容量为 j 的情况下能获得的最大总价值。那么对于第 i 件物品我们只有两种决策不放第 i 件物品那么价值就是 dp[i-1][j]放第 i 件物品前提是 j w[i]那么价值就是 dp[i-1][j-w[i]] v[i]取这两者的较大值状态转移方程就出来了dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这个方程可以说是整个背包DP的地基。后面所有背包问题的变种都是在这个方程上做修改。C实现起来也非常直观#include bits/stdc.h using namespace std; int main() { int n 4, V 10; int w[5] {0, 2, 3, 4, 5}; // 重量下标从1开始 int v[5] {0, 3, 4, 5, 6}; // 价值 vectorvectorint dp(n 1, vectorint(V 1, 0)); for (int i 1; i n; i) { for (int j 0; j V; j) { if (j w[i]) { dp[i][j] dp[i-1][j]; } else { dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]); } } } cout 最大价值: dp[n][V] endl; return 0; }我在VSCode里配好C环境之后直接按F5就能跑这段代码。输出结果是最大价值12。你可以自己手动验证一下选重量3价值4的、重量4价值5的、重量5价值6的总重量12超了或者选重量2价值3、重量3价值4、重量5价值6总重量10总价值13等等这个例子有点问题。我们来重新验证一下物品是(2,3)、(3,4)、(4,5)、(5,6)容量10。选(2,3)(3,4)(5,6)总重量10总价值13。所以上面代码里的最大价值应该输出13而不是我随便写的数字。这里我故意修正一下严谨一点。正确结果是dp[4][10] 13。具体组合是第1、2、4件物品2351034613。1.3 为什么说“dp数组”是在填表视觉化理解动态规划的过程本质上就是在填一张表。行是物品编号列是容量表格里的值就是dp[i][j]。还是上面那个例子n4V10物品分别是第1件w2v3第2件w3v4第3件w4v5第4件w5v6填充过程是这样的先初始化第0行全0没有物品可选时任何容量下的最大价值都是0。第1行考虑第1件物品容量从0到1时j w[1] 2所以都是0。从容量2开始dp[1][2] max(dp[0][2], dp[0][0]3) 3。之后容量3~10dp[1][j]都是3因为只能放第1件物品容量多了也没用。第2行考虑前2件物品容量0~1都是0容量2是3容量3时 j3 w[2] 3所以 dp[2][3] max(dp[1][3]3, dp[1][0]44) 4。容量4时dp[2][4] max(dp[1][4]3, dp[1][1]44) 4。容量5时dp[2][5] max(dp[1][5]3, dp[1][2]47) 7。这就是同时放第1件和第2件的结果。第3行考虑前3件物品容量4时dp[3][4] max(dp[2][4]4, dp[2][0]55) 5放第3件。容量6时dp[3][6] max(dp[2][6]7, dp[2][2]58) 8放第3件和第1件。第4行考虑前4件物品容量10时dp[4][10] max(dp[3][10][前3件的最大价值查表是7?实际上第4行算出来的结果]dp[3][5]6)。这里具体值需要你跑代码看。建议你拿张纸自己手动填一遍这个大表。填完之后你对“状态转移”这四个字的理解会瞬间从“看懂了”变成“真的会了”。我在带新人的时候从来不让对方一上来就刷题而是先手写几个小规模的背包问题填表比看十篇博客都管用。2. 从0/1背包到完全背包只改一个循环方向结果天差地别2.1 完全背包问题的引入与朴素实现弄懂0/1背包之后完全背包就很简单了。完全背包和0/1背包的唯一区别在于0/1背包里面每件物品只能放一次而完全背包里每件物品可以放无限次只要有容量就可以反复装。你可能会觉得这也没多难啊无非是多包一层循环枚举第i件物品放了几个。确实朴素写法就是这样for (int i 1; i n; i) { for (int j 0; j V; j) { for (int k 0; k * w[i] j; k) { dp[i][j] max(dp[i][j], dp[i-1][j-k*w[i]] k*v[i]); } } }这个三重循环的复杂度是O(nV(V/w[i]))在数据量小的时候还能忍数据一大就直接超时了。所以我们需要优化。这里的关键优化点是既然第i件物品可以放多次那么我在计算dp[i][j]的时候很可能已经计算过dp[i][j-w[i]]也就是还在考虑第i件物品但容量更少的情况。如果我从左往右枚举容量j那么dp[i][j-w[i]]已经是“允许放多次第i件物品”的最优解了我只需要在此基础上尝试再放一件第i件物品。所以完全背包的C代码可以在0/1背包代码基础上只改一个方向#include bits/stdc.h using namespace std; int main() { int n 3, V 10; int w[4] {0, 3, 4, 5}; int v[4] {0, 4, 5, 6}; vectorvectorint dp(n 1, vectorint(V 1, 0)); for (int i 1; i n; i) { for (int j 0; j V; j) { if (j w[i]) { dp[i][j] dp[i-1][j]; } else { dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]); } } } cout 完全背包最大价值: dp[n][V] endl; return 0; }你对比一下0/1背包的转移方程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])。区别就在第二项的第一个下标一个是i-1一个是i。下标是i-1表示第i件物品只能取一次下标是i表示还可以继续取第i件物品。这个微妙之差就是完全背包和0/1背包的全部秘密。2.2 一维滚动数组从二维DP到一维DP的空间压缩不管是0/1背包还是完全背包上面的二维写法在空间上是O(n*V)在n和V都很小的时候无所谓。但如果你在LeetCode上做题遇到那种V特别大的情况比如V是10^5量级二维数组直接爆内存。所以我们需要做空间压缩把dp数组从二维压到一维。一维数组的状态转移思路是一个滚动数组dp[j] 表示“当前已经遍历到的物品情况下容量为j时的最大价值”在遍历物品i时dp[j] 里存的还是前i-1件物品的结果我们用它来更新dp[j]0/1背包的一维写法vectorint dp(V 1, 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]); } }完全背包的一维写法vectorint dp(V 1, 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]); } }两个代码长得几乎一模一样唯一区别就是内层循环的方向0/1背包是j从大到小倒序完全背包是j从小到大正序。为什么0/1背包必须倒序因为倒序能保证dp[j-w[i]]在更新时还没有被当前物品i污染它还是上一次循环i-1的结果这样每件物品最多只能取一次。而完全背包需要正序让dp[j-w[i]]已经被当前物品i更新过这样就能实现“无限取”的效果。我强烈建议你在一张草稿纸上模拟一下这个小例子n2V5物品1(2,3)物品2(3,4)。分别按倒序和正序跑一遍一维dp亲眼看看数组里每个位置的变化你就再也不会把这个方向记混了。这是整个背包DP里最经典的一个小坑也是面试时最常被问到的细节。2.3 0/1背包和完全背包的模版对比速查表我把两者的核心区别整理成一张表大家刷题的时候可以随时对照对比项0/1背包完全背包每件物品取用次数最多1次无限次二维转移方程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])一维内层循环方向倒序j从V到w[i]正序j从w[i]到V一维转移方程dp[j] max(dp[j], dp[j-w[i]]v[i])dp[j] max(dp[j], dp[j-w[i]]v[i])适用典型题目分割等和子集、最后一块石头的重量II零钱兑换、完全平方数这里注意一维转移方程表面上是一样的效果完全不一样。很多人背模板只背了个“倒序还是正序”却不知道背后的原因一换个题目包装就傻眼。我后面在第四节会专门讲怎么通过语义来区分。3. 多重背包与二进制拆分处理“有限数量”的第三个主角3.1 为什么多重背包不能直接套完全背包写法第三个经典模型是多重背包。每件物品有一个数量限制c[i]可以理解为物品i最多取c[i]次但也不能无限取。这是介于0/1背包c[i]1和完全背包c[i]无穷大之间的情况。最暴力的做法是把它拆成0/1背包来做第i件物品有c[i]件就把这c[i]件都当成独立的物品每件只能取一次。这样问题就退化成了0/1背包。但是它的复杂度是O(V*Σc[i])如果c[i]都很巨大比如每件物品都有10^5件就完全跑不动了。这里需要用到二进制拆分优化。思路是任何一个正整数c都可以表示成若干2的幂次之和。比如19 1 2 4 8 4。那么我可以用这些2的幂次作为新的“捆绑物品”的重量和价值代替原来c件完全相同的物品。举个例子某件物品重量w3价值v5数量c13。传统拆法要拆成13件单独的(3,5)。二进制拆法怎么拆先拆出1件(13, 15) (3,5)再拆出2件(23, 25) (6,10)再拆出4件(43, 45) (12,20)剩余6件拆出63, 65 (18,30)。这样原来13件变成了4个捆绑物品对这4个捆绑物品跑0/1背包即可。任意0~13之间数量的同种物品都可以由这4个捆绑物品的某种组合拼出来。这个优化的道理就像你使用人民币纸币的面值是1、2、5、10而不是你每次买东西都带上一堆1元硬币。用最少的物品数量表示任意数量本质上是二进制编码的思想。3.2 C实现多重背包二进制拆分二进制拆分的C代码逻辑是这样#include bits/stdc.h using namespace std; struct Item { int weight; int value; }; int main() { int n 2, V 10; int w[3] {0, 3, 2}; int v[3] {0, 5, 4}; int c[3] {0, 4, 3}; // 数量限制 vectorItem items; for (int i 1; i n; i) { int k 1; int remain c[i]; while (remain 0) { int take min(k, remain); items.push_back({take * w[i], take * v[i]}); remain - take; k 1; } } vectorint dp(V 1, 0); for (auto item : items) { for (int j V; j item.weight; j--) { dp[j] max(dp[j], dp[j - item.weight] item.value); } } cout 多重背包最大价值: dp[V] endl; return 0; }这里对每个拆分出来的捆绑物品跑0/1背包内层倒序。复杂度从O(VΣc[i])降低到O(VΣlog(c[i]))。举个例子你就明白了如果原来共有10^6件物品二进制拆分后只有不到20件性能提升几个数量级。注意一个细节remain相减后k继续左移但最后一段不一定是2的幂比如剩余6而是直接取剩下的数量。这是为了保证拼出0到c之间任意数量时都一定有解。如果你只拆成纯2的幂1、2、4、8...最后剩余6不能用42表示吗其实可以但我上面代码为了简单稳妥取takemin(k, remain)。实际上标准写法里剩余部分直接用remain这样任何数量都能精确表示。两者都能做到但直接取剩余不会做到一半超出数量限制。3.3 单调队列优化面试加分项但不建议新手先碰多重背包还有一个更高级的优化叫单调队列优化也叫滑动窗口优化可以把复杂度降到O(n*V)。它的核心思想是对于固定的物品i容量j在模w[i]的同一个剩余类下dp[j]的更新只依赖于同余类中前面某个位置的值可以用单调队列维护区间最大值。这个优化的代码比较绕不太适合新手一开始就死磕。我的建议是先理解二进制拆分能解决90%的多重背包问题。等刷到一定量级再回头研究单调队列优化。面试中问到多重背包能说出二进制拆分已经算不错的回答了能再提到单调队列优化是明显的加分项。不过我还是附上单调队列多重背包的参考代码供学有余力的读者研究#include bits/stdc.h using namespace std; int main() { int n 2, V 10; int w[3] {0, 3, 2}; int v[3] {0, 5, 4}; int c[3] {0, 4, 3}; vectorint dp(V 1, 0); for (int i 1; i n; i) { for (int a 0; a w[i]; a) { // 按余数分组 dequeint q; for (int j a; j V; j w[i]) { // 队头维护窗口长度不能超过c[i] while (!q.empty() (j - q.front()) / w[i] c[i]) q.pop_front(); // 队尾维护保证单调递减 while (!q.empty() dp[q.back()] (j - q.back()) / w[i] * v[i] dp[j]) q.pop_back(); q.push_back(j); dp[j] dp[q.front()] (j - q.front()) / w[i] * v[i]; } } } cout dp[V] endl; return 0; }这段代码里我用了deque实现双端队列。核心思想是把容量j按照对w[i]取模的余数分成w[i]组组内每次跨步w[i]前进用单调队列维护每个位置上“原始dp值 增长的v[i]贡献”的最大值。建议你在电脑上跑一下配合断点观察q的变化。我第一次学这块大概花了一整个周末才完全弄明白但弄明白之后对动态规划的理解会上一个台阶。4. 背包DP实战C编程中常见问题与debug实录4.1 初始化陷阱dp[0]0还是dp[0]-INF这是背包DP里最常见的一个坑也是面试官最喜欢埋的“陷阱点”。不同的问题对初始化的要求不同如果题目说“恰好装满背包”的最大值那么初始化时只有dp[0] 0其他dp[j] -INF。因为只有容量为0的时候才可能是“恰好装满”的起点其他状态是不可达的。如果题目说“不超过容量V”的最大值那么初始化时所有dp[j] 0。因为容量不管是多少什么都不放就是价值0都是合理状态。举个例子你就明白了。LeetCode上的“零钱兑换”问题要求凑出总金额amout所需的最少硬币数。这就是一个“恰好凑满”味很强的问题因为你要的结果必须精确等于amout不能比它多。所以初始化时dp[0]0其他dp[i]1e9相当于无穷大。如果你全部初始化为0递推的时候会得到一堆0的结果程序出来的答案是0实际上是错的。再比如LeetCode上的“分割等和子集”问题判断能否把数组分成两个元素和相等的子集等价于能不能恰好凑出总和的一半。这也是“恰好”类型初始化应该dp[0]true其他为false。我见过太多人在这些问题上交了带错的初始化的代码WA了都看不出来。一个小技巧如果你发现dp结果看起来“偏大”或全是0十有八九是初始化没设对。4.2 数组越界与VSCode调试中的典型报错用VSCode写C的背包DP时最常见的报错就是数组越界。比如状态转移时写了dp[j - w[i]]一旦j w[i]下标就变负数。代码里我用了if (j w[i])来保证但还是有很多新手图省事直接用二维数组然后j从0循环到V也没判断。这种问题通常表现为程序没崩但结果乱七八糟或者直接弹出“Segmentation fault”段错误。在VSCode里出现Segmentation fault时第一反应是检查索引是否越界。可以把循环变量临时加打印或者用debug模式打断点看循环到哪个值时出的问题。另外一个很有意思的现象VSCode里用iostream的cin/scanf读入如果数据量极大是会超时的。题目给10^4个物品每个物品有重量和价值用默认的cin读入性能可能不够。我习惯在main函数开头加这三行ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);这三行解除了C标准输入输出与C标准IO的同步能显著提升读写速度。同时对于读入量极大的数据也可以用快读模板或者用原生scanf。这算是不起眼但能救命的优化。4.3 状态转移方向记反了用“取了几件”来解释很多人在一维写法里弄不清正序和倒序这里我再给一个更直观的记忆方式0/1背包里每件物品只能取一次所以更新时要用“还没考虑当前物品”的状态。你从后往前刷刷到j的时候dp[j-w[i]]还没来得及被当前物品i“污染”所以它代表的是“前i-1件物品”的结果。完全背包里每件物品能取无限次所以你希望dp[j-w[i]]已经是“允许取当前物品无限次”的状态了。正序刷让dp[j-w[i]]在当前物品i的循环里先被更新过后面再用它就包含了当前物品i。如果实在记不住我有一个物理上的类比想象你有一排货架容量1到V。0/1背包你从右往左走看到的左边的货架都是昨天贴好的价格i-1的结果所以每件商品最多被选一次完全背包你从左往右走左边的货架都是今天刚更新过的价格所以可以反复选同一件商品。这个类比我讲给很多人听过普遍反映比死记结论好用。提示如果刷题时发现完全背包写成了倒序结果往往是结果偏小0/1背包写成正序结果往往是每个物品被选中多次答案偏大。用这个规律反向排查能省下大量debug时间。4.4 从题目到代码的四步审题法最后分享一个我自己的解题流程。拿到一道背包DP题我一般按这四个步骤走确定背包容量V是什么是总时长、总预算、总空间还是数组的和确定物品是什么每个物品的重量和价值分别对应题目里的哪个量确定物品的取用次数每件只能用一次0/1、无限次完全、还是有限次数多重确定是“恰好装满”还是“不超过容量”据此设置初始化。把这一步梳理清楚代码基本就出来了。很多人觉得背包题难其实不是难在写代码而是难在“识别”题目到底在考背包。比如LeetCode 416题“分割等和子集”表面上是个数组切分问题实际就是0/1背包LeetCode 322题“零钱兑换”表面上是找最少硬币数实际是完全背包的变种LeetCode 518题“零钱兑换II”表面上是求组合数实际是完全背包在求方案数。识别能力只能靠多刷题培养但每次刷完尝试把题归类到“这四步”里会让你更快形成条件反射。5. 背包DP的进阶方向分组背包、二维费用与方案数统计5.1 分组背包每组只能选一件代码比想象中简单分组背包是0/1背包的一个自然扩展。物品被分为若干组每组里最多选一件物品。这个模型的典型场景是每个组代表一个“品类”你最多从这个品类里挑一个。它的状态转移方程非常容易理解在一维dp的基础上加一组循环for (int k 1; k groupCount; k) { // 枚举每组 for (int j V; j 0; j--) { // 枚举容量倒序 for (auto item : groups[k]) { // 枚举该组内的每个物品 if (j item.weight) { dp[j] max(dp[j], dp[j - item.weight] item.value); } } } }注意这里外层是“组”中间层是“容量”内层才是“组内物品”。容量为什么要倒序和0/1背包的理由一样保证每组内的物品最多被选一次不会出现同一组里选了两件的情况。你把代码背下来之后会发现分组背包写出来跟0/1背包几乎一模一样只是多了一层内循环。它考察的其实是“你懂不懂为什么要这样套循环”。我觉得这是从“会模板”到“会用模板”的一道分水岭。5.2 二维费用背包加一个约束条件数组多加一维有时候背包不仅有重量限制还有体积限制。比如行李箱有“重量上限”和“体积上限”两个约束。这时候背包问题从一维容量变成二维容量dp数组也要从一维变成二维。一维背包的状态是 dp[j]表示容量为j时的最大价值二维费用背包的状态就是 dp[j][k]表示容量1为j、容量2为k时的最大价值。C实现如下以0/1背包为例#include bits/stdc.h using namespace std; int main() { int n 3, V1 5, V2 5; int w1[4] {0, 1, 2, 3}; // 第一维费用 int w2[4] {0, 2, 1, 2}; // 第二维费用 int v[4] {0, 3, 4, 5}; // 价值 vectorvectorint dp(V1 1, vectorint(V2 1, 0)); for (int i 1; i n; i) { // 注意两个容量维都要倒序 for (int j V1; j w1[i]; j--) { for (int k V2; k w2[i]; k--) { dp[j][k] max(dp[j][k], dp[j - w1[i]][k - w2[i]] v[i]); } } } cout dp[V1][V2] endl; return 0; }二维费用背包在真题里很常见比如“技能加点问题”——你有技能点也有金币每个技能需要消耗固定的技能点和金币求攻击力最大化。这就是一个标准的二维费用背包。它的代码没有变难多少只是dp多了一维。理解了一维的倒序原理二维的倒序就顺理成章了两个维度都从大到小防止同件物品被多次使用。5.3 求方案数的背包DP递推从“最大”变成“相加”除了求最大价值背包问题还有一个高频变种——求方案数。比如“凑出总金额V有多少种组合方式”。这个变种的核心变化是状态定义从dp[j] max(...)变成dp[j] dp[j-w[i]]。因为你要把每种可能的组合数量累加起来而不是取最大值。以完全背包求组合数为例LeetCode 518题vectorlong long dp(V 1, 0); dp[0] 1; // 凑出金额0有1种方式什么也不选 for (int i 1; i n; i) { for (int j w[i]; j V; j) { dp[j] dp[j - w[i]]; } }注意这里有个小细节外层循环是硬币种类内层循环是金额且正序——这保证了每种组合只看一次组合不强调顺序。如果你把内外循环反过来得到的就会是“排列数”比如先选1元再选2元和先选2元再选1元被认为是两种方式。这在LeetCode里是另一道经典题377题“组合总和IV”两者的唯一区别就在这里循环的嵌套顺序。我当年在一道笔试题上就栽在这题目只改了一个字“组合数”改成“排列数”我的代码WA了半天没发现。后来才明白外层遍历物品时每个硬币被当成了“阶段”相当于规定了一个顺序于是不会出现顺序颠倒的重复计算外层遍历金额时则没有这个顺序限制排列和组合就区分开了。5.4 背包DP还能怎么扩展泛化物品与背包方案的输出比起上面这些经典模型还有一些更灵活的扩展值得了解但不需要死记知道有这回事就行。泛化物品每个物品的价值不是一个固定值而是“承载容量”的函数也就是说物品的价值随着给它分配多少容量而变化。这可以统一处理“选1件”“选2件”这种依赖关系竞赛里用得比较多。输出最优方案不光要最大价值还要知道到底选了哪些物品。做法是从dp的末尾往回回溯如果dp[i][j] dp[i-1][j]说明第i件没选否则说明选了然后跳到j-w[i]继续查。如果用了滚动数组一维dp回溯就做不了因为它把中间状态覆盖掉了。所以需要输出方案的时候不要只用一维得保留完整的二维表。这两个场景在面试里出现频率不高但一旦考到如果你能答出来会是个很亮眼的加分点。尤其是输出方案很多刷了上百道题的人都不知道怎么做。方法很简单额外开一个choice[i][j]数组在更新dp的时候记录“第i件物品在容量j时选没选”最后逆着遍历一遍。6. 写在刷题和面试之外背包DP的思维价值写到这里背包DP的主要脉络已经走了一遍。你可能会想这些模板和技巧我都看明白了可是到了新题目上还是不太会套。这是非常正常的我也经历过这个阶段。我自己的体会是背包DP的本质关键不在那些代码而在于你把一个实际场景抽象成“状态 决策 转移”的能力。做旅行装箱是这样做项目排期是这样做预算分配也是类似思路。你从0/1背包的“拿或不拿”到完全背包的“拿几个”再到分组的“从哪几个里面挑一个”这条逻辑链条本身就是动态规划思想的进阶路线。如果用一句话总结我会说什么背包DP不是一个需要背的答案而是一套思考问题的方式。C只是用来把它落地的工具。建议你从今天开始别急着跑题海先把0/1背包的二维和一维实现在VSCode里亲手跑通然后试着改一改循环的方向、改一改初始化看看输dp数组在这个过程中每步都发生了什么变化。把这一件事做透比囫囵吞枣刷十道题有用得多。最后分享一个我自己在VSCode里调试背包题的小技巧写一个打印dp表的函数把每次外循环结束后的dp数组都打出来。数据量小的时候直接肉眼观察看它是不是符合预期数据量大的时候单独跑一个小样例核对。这个小习惯帮我抓出过无数次“初始化写错”“循环方向写反”这种隐形bug。你也可以试试。