1. 从“背包”说起动态规划为什么值得死磕不管你是刚接触算法竞赛还是在为面试刷题动态规划里的背包问题几乎是一道绕不过去的坎。而我今天想聊的是用C把这类问题从“背模板”变成“真理解”。很多人在刷到01背包、完全背包、多重背包时第一反应是记住状态转移方程然后套着写。但一旦题目变个花样比如加上“恰好装满”“求方案数”“输出具体选了哪些物品”就彻底懵了。原因很简单你只记住了公式没理解决策过程。这篇文章会从最基础的01背包讲起一路讲到完全背包、多重背包的二进制优化、空间压缩再配合滚动数组、一维逆序更新这些C实现里的关键细节。每个部分我都会给出可直接运行的代码、参数推导过程以及我在实际调试中踩过的坑。适合三类人看正在准备笔试面试的求职者、打算法竞赛的选手以及那些学完动态规划但一做题就卡壳的自学者。先说个结论背包问题的核心不是“背状态转移方程”而是理解“每个物品到底选还是不选”这一决策如何被抽象成子问题并且如何用一张表把子问题的答案存下来。C的高效性恰好适合我们把这种二维表格推到一维再推到常数空间。这个从二维到一维的优化过程就是理解动态规划的关键一步。#include bits/stdc.h using namespace std;上面这个万能头文件在竞赛里很常见但面试手写时建议还是老老实实写标准头文件。接下来的所有代码我默认使用C17标准如果你用的是老版本编译器注意数组越界和auto推导的小差异。2. 01背包所有背包问题的地基2.1 状态定义与转移方程的由来01背包描述的是这样一个场景你有N件物品每件物品有自己的重量w[i]和价值v[i]背包容量为C每件物品只能拿一次问能装下的最大价值是多少。很多教程上来就甩出dp[j] max(dp[j], dp[j - w[i]] v[i])但从来不讲这个式子是怎么来的。我这里换个角度用“决策”来推一遍。假设我们已经处理完了前i-1件物品现在要决定第i件物品怎么办。这时只有两种选择不拿它背包容量不变价值就是dp[i-1][j]拿它需要腾出w[i]的空间即背包从j-w[i]容量时的最优解加上v[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[i][j]表示前i件物品中在容量为j的背包里能获得的最大价值。这个二维数组的每一行只跟上一行有关这就是后面所有优化的切入点。2.2 最容易被忽略的初始化问题初始化是背包问题里最阴险的地方没有之一。先用最常见的“恰好装满”和“不超过容量”两种问法来说明。如果题目说“不超过容量C就能装”那么dp[0][j]全部初始化为0因为容量再大不放任何东西价值也是0。但如果题目说“恰好装满背包”那么dp[0][0] 0dp[0][j]j 0必须初始化为一个极小值比如负无穷。为什么因为容量为j但一件物品都不放时这个状态是不合法的只有容量为0才合法。如果不这么初始化转移时会把不合法的状态当成0参与max运算结果就是你“恰好装满”算出来的答案偏大。我第一次在线上笔试里翻车就是栽在这。题目要求的“恰好装满”我当时全初始化为0结果三组样例过了隐藏用例全错。所以拿到任何背包题第一步不是写循环而是看清楚题目问的是“不超过”还是“恰好”。2.3 一维滚动数组的正确姿势二维dp是很好理解但空间复杂度O(N*C)在数据量稍大时就顶不住了。比如N1000C100000二维数组直接爆内存。这时候就该滚动数组上场。先看错误写法我见过太多人这么写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]); } }这样写有一个致命bug内层循环从小到大会重复使用当前物品。假设当前物品重量为2价值为3当j遍历到4时dp[2]已经在本轮被更新过了于是dp[4]会基于dp[2]再算一次等于同一件物品被拿了两次。这在01背包里是不允许的。正确写法必须让内层循环从大到小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]); } }这个逆序的底层逻辑是dp[j]的更新依赖的是上一轮的状态也就是还没有放入当前物品时的dp[j - w[i]]。如果从小到大更新dp[j - w[i]]已经被本轮污染过了相当于当前物品可能被重复选择。而逆序时j-w[i]一定小于j我们在这一轮还没有碰过它所以它仍是上一轮的旧值正好符合01背包“每件物品只能拿一次”的约束。2.4 完整的01背包参考实现#include iostream #include vector #include algorithm using namespace std; int main() { int N, C; cin N C; vectorint w(N 1), v(N 1); for (int i 1; i N; i) cin w[i] v[i]; vectorint dp(C 1, 0); // 默认“不超过容量”全部初始化为0 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]); } } cout dp[C] endl; return 0; }这段代码你已经能解决绝大多数01背包基础题了。接下来我们在这个基础上做三个常见变化体积恰好装满、求具体方案、求方案总数。这三种变形在面试里出现频率极高但很多刷题平台上的题解讲得都很简略。2.5 变体一恰好装满时的写法恰好装满时dp数组除了dp[0]0其余全部设为INT_MIN或一个足够小的负数。转移方程不变只是转移前要判断dp[j - w[i]]是否为负数。const int NEG_INF -1e9; vectorint dp(C 1, NEG_INF); dp[0] 0; for (int i 1; i N; i) { for (int j C; j w[i]; j--) { if (dp[j - w[i]] ! NEG_INF) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } } // 如果dp[C]仍是NEG_INF说明无法恰好装满按题目要求输出对应结果注意这里的判断一定不能省。如果不判断NEG_INF加上v[i]之后虽然还是负数但可能已经大于原来的NEG_INF了导致一个不合法的状态被错误地当成合法状态参与后续转移。2.6 变体二输出选择的具体方案输出具体方案是很多人一遇到就放弃的题但其实思路非常简单用一个二维数组path[i][j]记录第i件物品在容量j时是否被选择然后倒着回溯。vectorvectorint path(N 1, vectorint(C 1, 0)); // 在更新dp的地方同步记录 if (dp[j] dp[j - w[i]] v[i]) { dp[j] dp[j - w[i]] v[i]; path[i][j] 1; } // 回溯 vectorint selected; for (int i N, j C; i 1; i--) { if (path[i][j]) { selected.push_back(i); j - w[i]; } }这里有个细节倒序回溯是因为我们在递推时是从第1件到第N件处理的最后一件是否被选择的信息记录在path[N][C]里。如果path[N][C]为1说明第N件被选了容量扣掉w[N]然后去看第N-1件在容量j-w[N]下的决策。这样一路回溯回去就能还原出完整的选择列表。要注意的是输出顺序一般是倒着的如果题目要求按原顺序输出记得reverse一下。2.7 变体三方案总数的计算如果题目问“有多少种装法能达到最大价值”或者“有多少种方式恰好装满”状态定义就要从“最大价值”改成“方案数”转移方程也相应变为累加。vectorint dp(C 1, 0); dp[0] 1; // 容量为0时什么都不装也是一种方案 for (int i 1; i N; i) { for (int j C; j w[i]; j--) { dp[j] dp[j] dp[j - w[i]]; } }此时dp[j]的含义是“凑成容量j的方案数”不再是最大价值。初始化dp[0]1很好理解容量为0时只有“空集”这一种方案。递推关系本质上是不选当前物品的方案数dp[j]原来的值加上选当前物品的方案数dp[j-w[i]]。这类题目偶尔会问“方案数可能很大需要取模”那就每次累加后取模即可。3. 完全背包从小到大的内层循环才是关键3.1 与01背包的本质区别完全背包和01背包唯一的区别是每件物品可以无限取用。注意这里说的是“每件物品”不是“每种物品”所以不存在同一种物品数量限制的问题。很多人把完全背包的代码改成这样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]); } }发现咦竟然AC了对完全背包就是这么神奇只需把内层循环从逆序改成顺序即可。原因在于顺序遍历时dp[j - w[i]]在当前轮已经被更新过代表的是“已经考虑过放入当前物品若干次之后”的最优状态因此当前物品可以被反复使用恰好满足完全背包的“无限取用”约束。这里我踩过的坑是在学完全背包时总想用一个二维数组还试图在转移方程里加一个k循环表示取k件结果时间复杂度直接变成O(NCC/k)级别的。其实完全背包的正解就是那个看似随手改出来的顺序循环背后的“同轮覆盖”思想非常精妙。3.2 一个典型的硬币凑数问题完全背包最常见的考试题是“硬币找零”和“凑金额的组合数”。比如给你若干面值的硬币每种硬币无限量问凑成目标金额有多少种方法。这里有两个变种我分开讲下。如果问的是“组合数”不考虑顺序即{1,2}和{2,1}算同一种那么外层遍历物品、内层遍历容量代码如下vectorlong long dp(target 1, 0); dp[0] 1; for (int i 1; i N; i) { for (int j coins[i]; j target; j) { dp[j] dp[j - coins[i]]; } }如果问的是“排列数”{1,2}和{2,1}算不同则要交换循环顺序外层遍历容量、内层遍历物品for (int j 1; j target; j) { for (int i 1; i N; i) { if (j coins[i]) { dp[j] dp[j - coins[i]]; } } }这个区别很重要。组合数问题外层物品内层容量是因为我们以物品为主体每一轮只允许当前物品参与组合天然去重。排列数问题外层容量内层物品是因为每个容量状态都要遍历所有物品相当于每一步都可以选择任意一枚硬币加入序列因此不同顺序被计算为不同方案。我建议你亲手跑一遍这两个版本的对比感受一下循环嵌套顺序对“顺序无关性”的影响。这个理解会伴随你解决很多DP计数问题。3.3 完全背包的一个经典优化思路在某些完全背包场景里如果价值v[i]和重量w[i]之间满足v[i]/w[i]较大的物品更优我们其实可以先用贪心思想删掉一些劣质物品。具体来说如果两件物品A和B满足w[A] w[B]且v[A] v[B]那么物品B就可以直接扔掉因为A比B轻且价值更高任何选B的方案都可以替换成选A并获得更优或相同的价值。这个优化在实际竞赛里用得不多因为大部分题目数据范围并不需要这个预处理但它在“物品数量极大、但重量范围很小”的题里能大幅减少N。比如某道题N达到了10万但容量C只有1000那么所有重量大于C的物品全部不可选剩下的物品里如果存在“又轻价值又高”的同类替代品筛完之后N可能只剩几十复杂度直接下降好几个数量级。这个trick值得记在脑子里。4. 多重背包二进制拆分把优化推向极致4.1 为什么不能直接套完全背包多重背包的特点是第i件物品最多有m[i]件可以取0到m[i]件中的任意数量。最朴素的做法是把m[i]件物品摊开成m[i]个独立的01背包物品然后直接跑01背包。问题在于如果m[i]很大比如总物品数量达到10万甚至100万而容量也有10万直接展开的复杂度O(N*C)会直接超时。举个例子一件物品有10000件展开成10000个物品每个物品都参与一次容量为100000的01背包循环计算量就是10^9级别稳超时。我们需要一种方式用更少的物品组合出“取0到10000件”的所有可能性。4.2 二进制拆分的核心思想二进制拆分的原理很简单任何一个正整数都可以表示成若干个2的幂次之和。比如13 1 2 4 6不对应该写成13 1 2 4 6但6不是2的幂。正确做法是先按1、2、4、8这样的二进制位拆分最后剩下一个余数。具体规则是对数量m依次拆出1、2、4、8...直到剩余部分小于下一个2的幂最后把剩余的数作为一个单独物品包。比如m13拆出1剩余12拆出2剩余10拆出4剩余6拆出8不行因为剩余6小于8所以不能再拆8直接把剩余6作为一个包于是13被拆成1、2、4、6这四个包。用这四个包能组合出0到13的所有整数吗1, 2, 4可以组合出0到7的所有数二进制表示再加上6就能组合出6到13的所有数。拼起来正好是0到13全覆盖。基于这个性质我们把“取0到13件”等价为“从四个包中选若干个”每个包只有选和不选两种状态于是转成了01背包。代码如下vectorint newW, newV; for (int i 1; i N; i) { int cnt m[i]; int k 1; while (k cnt) { newW.push_back(w[i] * k); newV.push_back(v[i] * k); cnt - k; k 1; } if (cnt 0) { newW.push_back(w[i] * cnt); newV.push_back(v[i] * cnt); } } // 然后对newW、newV跑标准01背包这里k 1是左移一位等价于k * 2写法上更贴近二进制拆分的语义。4.3 单调队列优化当数据量再翻一个量级二进制拆分已经把复杂度从O(NmC)降到O(N*log(m)C)但有些题目的数据范围仍然不够比如N1000m1000C100000算下来还是10^8量级在评测机上只能卡着过。这时候就要上单调队列优化把多重背包压到O(NC)。具体做法是把容量C按模w[i]的余数分组。比如当前物品重量为w我们把容量j表示成j q*w r其中0 r w。对每一个余数r单独处理所有q。状态转移方程可以改写成关于q的滑动窗口最值问题用单调队列维护窗口内的最值。这里我先把代码给出再解释它的来历for (int i 1; i N; i) { int c m[i], ww w[i], vv v[i]; for (int r 0; r ww; r) { dequeint dq; // 每个余数r单独处理k表示该余数下可放的件数 for (int q 0; q * ww r C; q) { int j q * ww r; // 维护窗口中dp[j] - q * vv 的最大值 int val dp[j] - q * vv; while (!dq.empty() dq.back() val) dq.pop_back(); dq.push_back(val); // 如果窗口长度超过c1即最多放c件弹出队头 // 队头就是最优来源 dp[j] dq.front() q * vv; } } }这段代码第一次看很容易懵我拆开讲一下。对于固定余数r所有j r, rww, r2ww, ...形成一条链。dp[j] max(dp[j], 其中j在[j-(c1)*ww, j]之间) vv * 相应的数量差。把dp[j]减去j对应的“数量乘以单价”之后就变成一个滑动窗口内的最大值问题用单调队列维护即可。这个优化的边界条件非常容易写错我在初次实现时在窗口长度上翻过车。核心是要想清楚当前容量j最多能放多少件当前物品答案是min(q, c)也就是当前容量对应的件数和物品库存量之间的较小值。因此窗口大小是c1个状态不是c个。如果你写错了往往在小数据上恰好能过大数据随机测试时才暴露问题。4.4 分组背包与混合背包除了上述三种基础背包还有两类高频变种分组背包和混合背包。分组背包指某些物品必须分组每组内最多选一个。做法是把“每个组”当成一层在每组内先做一次01背包决策选择该组中的最优物品。核心代码for (int k 1; k K; k) { // 第k组 for (int j C; j 0; j--) { // 容量逆序 for (auto item : group[k]) {// 组内每个物品 if (j item.w) { dp[j] max(dp[j], dp[j - item.w] item.v); } } } }为什么容量循环要在组内物品循环之前因为我们要保证每一组内最多选择一个物品。先枚举容量再枚举组内物品使得同一个容量j在本轮中只能被更新一次不会出现在同一组内连续选多个物品的情况。如果交换循环顺序就可能在同一轮里叠加组内多个物品那就不符合“每组最多选一个”的约束了。混合背包就是把01背包、完全背包、多重背包混在一起给物品。处理方式很简单分别判断每件物品是01背包型、完全背包型还是多重背包型然后用对应的循环方式更新即可。多重背包部分建议直接用二进制拆分转成01背包处理这样代码统一也避免单调队列的复杂边界。5. 从二维到常数空间背包空间的进化之路5.1 为什么老玩家都在讲“空间压缩”很多新手觉得空间复杂度不过是个数字只要数组开得下就没问题。但事实上一些背包题可以做到只用一个一维数组而某些更进阶的题目对空间的限制极其苛刻比如内存只有16MBN和C都上万二维int数组就是40MB直接超限。况且空间压缩不只是为了省内存。它强迫我们用“决策覆盖”的视角理解DP这种视角对后续学习状压DP、树形DP都有帮助。理解了为什么必须逆序更新01背包、顺序更新完全背包你对“状态依赖关系”的理解会深刻得多。5.2 一个只用一个数组的完整示例以01背包为例最省空间的方式就是只用一个dp数组下标含义已经是“容量为j时的最优解”。这其实是在用时间换空间或者说用“覆盖”来代替“保留历史行”。因为每一轮只需要上一行的数据所以我们不需要保留所有历史行只需要保证覆盖时不会读到一个已经被本轮污染的数据这就是逆序循环存在的全部意义。我建议你做这样一个练习把二维dp表手工画一遍比如3件物品、容量为5然后对照一维逆序代码一行一行模拟变量的变化。你会发现一维数组在每一轮迭代后保存的其实是“前i件物品在各个容量下的最优值”。这个过程只要亲手推一遍以后就再也不会把循环顺序记反。5.3 一些加深理解的练习题建议学习背包问题光看不练没有意义。我推荐按这个顺序刷题基础01背包先做纯01背包再做到恰好装满再求方案数完全背包做硬币凑数问题分别体会组合数和排列数两种问法多重背包先用二进制拆分解决再用单调队列优化跑一遍同题对比性能分组背包和混合背包做一两道综合题即可每道题做完之后试着修改题目条件如果把“最大价值”改成“最小花费”初始化该怎么做如果价值可能是负数dp数组要初始化为多少如果物品顺序有依赖关系状态定义要不要加维度这些引申思考比刷十道重复题更有价值。6. 常见问题排查与实战心得6.1 你可能会遇到的五个经典Bug我在教别人写背包时发现大家的报错模式高度集中这里整理成一张速查表症状可能原因解决方案答案比期望值大可能是01背包内层循环写成了顺序把内层循环改成从C到w[i]逆序答案偏小恰好装满问题但dp数组初始化为0把dp[0]初始化为0其余设为极小值数组越界j - w[i]没做边界判断循环下限设为w[i]或增加if判断完全背包方案数错误循环顺序没区分组合数和排列数确认题目要求的是组合数还是排列数多重背包TLE直接暴力展开物品使用二进制拆分或单调队列优化这张表我建议收藏笔试前扫一眼能帮你省下大量调试时间。6.2 笔试中的时间管理技巧背包问题在笔试中通常不会单独考而是作为某一题的中间步骤出现比如“字符串匹配背包”“图论背包”这种组合题。所以不要指望题目会告诉你“这是背包问题”。识别背包问题的几个信号有容量/预算上限、有若干物品且每个物品有消耗/收益、目标是最大化收益或最小化消耗。一旦看到这些信号先往背包方向想。另外笔试环境通常没有本地IDE调试困难。我的习惯是先把状态定义写在草稿纸上再写转移方程最后才写循环。不要上来就敲代码背包问题一旦状态定义错了代码再对也是白搭。6.3 一个真实调试案例最近帮一个朋友看他的代码他自己写了一个“多重背包恰好装满”的题但答案一直不对。我看了一眼发现他把多重背包直接写成了完全背包的顺序循环。他说因为多重背包也能取多个所以我就用了顺序。这就是典型的没有理解逆序和顺序的本质区别。我给他打了个比方01背包逆序更新相当于“每个物品只有一件用了就没了”完全背包顺序更新相当于“物品在货架上无限供应随时可以再拿”多重背包则介于两者之间“货架上的数量有限不能无限拿”。他听完瞬间就理解了。这个类比你也可以用来给朋友解释比直接说“状态被污染”亲切得多而且更容易形成直觉。6.4 再谈一个容易被忽视的细节数据类型背包问题的数据范围经常不声不响地大起来。如果N和C都在10^4以上答案可能会超过int范围。比如一件物品价值10^9背包容量10^5那么答案可能是10^14量级int完全装不下。所以写代码时我习惯直接用long long只有在题目明确说明答案不超过int时才用int。反正空闲内存足够用long long不会多花多少时间却能避免溢出导致的WA。一个简单的经验是输入里只要有关于价值的数字超过10^5就默认用long long。7. 写在最后的经验之谈背包问题的套路感很强但它的价值绝不止于“会写模板”。我见过太多人背下来01背包的代码但一旦题目从“最大价值”改成“最小花费”或者从“恰好装满”改成“至少达到某个容量”就完全不会了。问题在于你只记住了max和0没有记住为什么是max为什么从0开始。我的建议是找几张草稿纸亲手把dp表格画出来把每一次更新的数值填进去。这个过程只需要半小时但做完之后你对状态转移、滚动数组、逆序更新的理解会远超刷一百道题。我当年就是这么干的现在遇到任何背包变种基本都能在几分钟内写出状态定义和转移方程。如果你还在学习阶段不妨给自己定一个小目标不看任何参考代码独立写出01背包、完全背包、多重背包二进制拆分版这三个程序并解释清楚每一层循环顺序为什么这样写。能做到这一步背包问题的大门才算真正为你打开。接下来不管是状压背包、树上背包还是依赖背包你会发现自己已经有了举一反三的底气。