1. 先看清楚题目01背包到底让我们做什么1.1 一个你上手就会遇到的经典场景我当年第一次刷到 01背包 是在学校的 OJ 上题目描述到现在还记得有 n 件物品每件物品有自己的重量 w[i] 和价值 v[i]现在有一个容量为 V 的背包问你最多能装下多少价值的物品。限制条件很严格——每件物品只能选一次要么装进去要么不装不存在装半件或者装两件的说法。这也是01这个名字的由来每个物品的状态只有 0 和 1 两种。这道题看起来简单但它的地位在算法竞赛里非常高。C 选手入门动态规划十有八九是从 01背包 开始的而很多看起来完全不像背包的问题比如资源分配、任务调度、投资组合最后都能抽象成 01背包 模型。我在群里见过不少同学把 01背包 模板背得滚瓜烂熟结果题目稍微变一下——比如要求恰好装满、要求输出方案、要求计算方案数——就当场卡住。根本原因不是代码不熟而是没搞懂状态定义和转移方程背后的语义。这篇文章我会从最朴素的暴力枚举开始一步步推到二维 DP再从二维优化到一维滚动数组最后讲几个高频变式。全程用 C 写代码每个优化步骤都解释为什么而不是扔给你一个模板让你背。不管是刚学 C 语法、第一次接触动态规划的新手还是刷题遇到瓶颈想回头补基础的老手这篇文章应该都能给你一些新的视角。1.2 为什么选与不选这层窗户纸值得反复捅很多初学者第一次看到 dp 数组的时候最大的困惑是为什么要用一个二维数组为什么不能直接贪心这里先说一个常见的错误直觉——每次选性价比最高的不就行了吗也就是价值除以重量最大的优先选。这个想法在部分场景下确实对但反例太好找了。假设背包容量是 5有三件物品物品编号重量价值性价比价值/重量1231.52341.333482.0如果按性价比贪心会先选物品 3性价比 2.0剩下的容量只剩 1什么都装不下总价值是 8。但实际最优解是选物品 1 和物品 2总重量 5总价值 3 4 7。不对这里贪心结果反而更好……那再换一个例子。物品 1重量 3价值 4性价比 1.33 物品 2重量 3价值 4性价比 1.33 物品 3重量 2价值 3性价比 1.5 背包容量 4。按性价比贪心选物品 3价值 3剩余容量 2 什么也选不了总价值 3。但最优解选物品 1 或物品 2 中任意一个总价值 4。贪心失败了。所以问题没那么简单。每件物品选或不选n 件物品的组合方式是 2^n 种。当 n30 的时候直接枚举所有子集已经要跑十亿次级别n100 时更是天文数字。动态规划的价值在于它把决策变成了状态之间的转移用空间换时间把指数级复杂度降到了多项式级别。理解 01背包 的另一个关键点在于它是一切背包问题的地基。完全背包、多重背包、分组背包、依赖背包都是在每件物品只有一次选择机会这个模型上放松或增加限制。把 01背包 的 dp 方程吃透了后面学其他背包问题会非常快。2. 二维DP状态定义和状态转移方程是怎么一步步来的2.1 暴力枚举为什么不可行重叠子问题又是什么先别急着写代码我们推演一下暴力思路。枚举所有子集可以用位运算的方式n 件物品对应 n 位二进制每一位是 0 或 1。n20 时大约 100 万种子集还能勉强跑n30 时超过 10 亿已经不行了OJ 上 01背包 的 n 经常是 100 甚至 1000暴力必死。但直接跳到动态规划之前我想先讲一个更容易理解的中间步骤记忆化搜索。dfs(i, j) 表示当前处理到第 i 件物品背包剩余容量为 j能获得的最大价值然后在递归里做选和不选两种决策int dfs(int i, int j) { if (i 0) return 0; int res dfs(i - 1, j); // 不选第 i 件 if (j weight[i]) { res max(res, dfs(i - 1, j - weight[i]) value[i]); // 选第 i 件 } return res; }这个递归版代码直接展开就是暴力枚举。但它有一个特性同一个 (i, j) 状态会被反复计算。比如处理到第 5 件物品时容量可能通过不同路径来到达同一个值如果每次都重新递归就是指数级开销。加一个 memo 数组缓存结果就是记忆化搜索把递归改成自底向上的循环就是二维 DP。这个过程是我自己学动态规划时觉得最顺畅的一条路径比直接甩状态转移方程容易接受得多。2.2 dp[i][j] 的定义是怎么想出来的很多人背状态定义的时候不理解为什么 dp 要开两维。其实你可以这样想我们关心的核心变量有两个——当前考虑了前几件物品和当前背包用了多少容量。这两个变量共同决定了一个子问题。所以状态就自然设计成 dp[i][j]表示前 i 件物品中选取若干件放入容量为 j 的背包能获得的最大价值。接下来的问题是dp[i][j] 怎么从更小的状态推出来考虑第 i 件物品的决策只有两条路不选第 i 件物品那么前 i 件物品的最优解就等于前 i-1 件物品在容量 j 下的最优解即 dp[i-1][j]。选第 i 件物品前提是当前容量至少能放下这件物品即 j weight[i]。一旦选了价值变成 dp[i-1][j-weight[i]] value[i]意思是给第 i 件物品腾出 weight[i] 的空间剩下的容量 j-weight[i] 交给前 i-1 件物品去分配。两个方案取较大值这就是状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i]) 当 j weight[i] dp[i][j] dp[i-1][j] 当 j weight[i]理解这个方程的关键是明白 dp[i-1][j-weight[i]] 已经隐含了前 i-1 件物品在容量 j-weight[i] 下的最优解。也就是说我们不需要关心前 i-1 件具体选了哪些只需要知道那个子问题的最优价值是多少。这就是动态规划无后效性的体现——过去怎么选的不重要重要的是当前状态值。2.3 完整二维写法与手算推演下面给一版可以直接跑的 C 二维 DP 代码。我用的是从 1 开始的下标weight[1] 到 weight[n] 存每件物品重量value[1] 到 value[n] 存价值dp 数组第一维长度 n1第二维长度 V1注意下标范围别开小了。#include iostream #include algorithm using namespace std; const int MAXN 1005; const int MAXV 1005; int weight[MAXN], value[MAXN]; int dp[MAXN][MAXV]; int main() { int n, capacity; cin n capacity; for (int i 1; i n; i) { cin weight[i] value[i]; } for (int i 1; i n; i) { for (int j 0; j capacity; j) { dp[i][j] dp[i - 1][j]; // 不选第 i 件 if (j weight[i]) { dp[i][j] max(dp[i][j], dp[i - 1][j - weight[i]] value[i]); // 选第 i 件 } } } cout dp[n][capacity] endl; return 0; }跑个例子。n4容量 V5物品信息如下物品重量价值123212334422手动推一下二维表的部分关键位置。i1物品重量 2价值 3容量 j2 时 dp[1][j]0j2 时 dp[1][2]max(dp[0][2], dp[0][0]3)3j3 时 dp[1][3]max(0, dp[0][1]3)3j4、5 同理为 3。i2物品重量 1价值 2j1 时dp[2][1]max(dp[1][1], dp[1][0]2)2j2 时max(dp[1][2]3, dp[1][1]22)3j3 时max(dp[1][3]3, dp[1][2]25)5j4 时max(3, dp[1][3]25)5j5 时max(3, dp[1][4]25)5。i3物品重量 3价值 4j3 时max(dp[2][3]5, dp[2][0]44)5j5 时max(dp[2][5]5, dp[2][2]4347)7。i4物品重量 2价值 2j5 时max(dp[3][5]7, dp[3][3]2527)7这里两个方案持平。最终 dp[4][5]7对应的最优选择是物品 2重 1 价 2 物品 3重 3 价 4总重量 4总价值 6。等等这里是 426不对重新算一下。物品 2 价值 2物品 3 价值 4总共 6。dp 值怎么会是 7说明我推演的时候算错了或者最优选择是物品 1重 2 价 3 物品 3重 3 价 4总重量 5总价值 7。这才是最优解。我重新核对一下 i4 那一行。dp[3][3] 应该是背包容积 3 时前 3 件物品的最优价值。前 3 件物品是物品 12,3、物品 21,2、物品 33,4。容量 3 的情况下最优是选物品 1 物品 2重量 3价值 325或者只选物品 3价值 4所以 dp[3][3]5。那 dp[3][3]27 对应的方案是选物品 4重 2 价 2再加上 dp[3][3] 中价值 5 的方案物品 1 物品 2总重量 235总价值 257。这个方案是物品 1、物品 2、物品 4总价值 3227重量 5也是合法的。所以 dp[4][5]7 没问题但我上面那句最优选择是物品 2物品 3是错的应该是物品 1物品 2物品 4 或物品 1物品 3。这种手算推演很容易出错但也正是理解 DP 的好方法——建议你自己开个数组把整张表填一遍比看十遍教程都管用。3. 一维滚动数组优化空间减半背后的数学逻辑3.1 为什么可以把第一维去掉二维 DP 的时间复杂度是 O(n×V)空间复杂度也是 O(n×V)。当 n1000、V100000 的时候dp 数组要 1001×100001 个 int大约 4 亿字节400MB多半要炸内存。时间没法再降了因为状态数量本身是 n×V 级别的但空间可以优化。注意转移方程里dp[i][j] 只依赖 dp[i-1][j] 和 dp[i-1][j-weight[i]]。换句话说第 i 行的计算只用到了第 i-1 行再往前的数据用不到了。这就给了我们一个空间优化的机会只保留一行 dp 数组每次从前往后刷新这一行让 dp[j] 表示当前处理到第 i 件物品时容量为 j 的背包能获得的最大价值。更新完这一行它就从第 i-1 行的语义变成了第 i 行的语义。3.2 倒序遍历的真正原因这个优化最关键的细节是容量 j 的循环要倒着来。很多新手直接改成正序就跑出了完全背包的效果一件物品被重复选了好几次。为什么会这样因为正序遍历时当你更新 dp[j] 用到的 dp[j-weight[i]]可能已经在当前这一轮被更新过了。假设物品重量是 2价值是 3正序从 j0 循环到 capacityj2 时dp[2] max(dp[2], dp[0]3) 3这时 dp[2] 已经被第 i 件物品更新过了。j4 时dp[4] max(dp[4], dp[2]3)注意 dp[2] 现在是 3所以 dp[4] 会变成 6。这意味着同一件物品被选了两次。如果倒序遍历从 capacity 往小走j4 时dp[4] max(dp[4], dp[2]3)此时的 dp[2] 还是上一轮前 i-1 件物品的结果没有被第 i 件物品污染。j2 时dp[2] max(dp[2], dp[0]3)dp[0] 永远是 0不会出问题。所以倒序的本质是保证更新 dp[j] 时用到的是上一轮的状态而不是当前轮已经被第 i 件物品更新过的状态。这是 01背包 和完全背包在一维写法上的根本区别。完全背包就是正序因为它允许同一件物品无限选。3.3 一维写法的完整代码与复杂度对比一维优化后的 C 代码非常简洁#include iostream #include algorithm using namespace std; const int MAXV 100005; int dp[MAXV]; int main() { int n, capacity; cin n capacity; for (int i 1; i n; i) { int w, v; cin w v; for (int j capacity; j w; j--) { dp[j] max(dp[j], dp[j - w] v); } } cout dp[capacity] endl; return 0; }注意看这个版本甚至不需要 weight 和 value 数组——每读入一件物品就直接滚动更新 dp。这也是常见的空间优化手段比赛时很实用。二维与一维的对比对比项二维写法一维滚动数组状态含义dp[i][j] 前 i 件物品、容量 j 的最大价值dp[j] 当前处理到的物品、容量 j 的最大价值空间复杂度O(n×V)O(V)时间复杂度O(n×V)O(n×V)时间不变容量循环方向正序或倒序都行只要写对必须倒序适用场景需要回溯具体方案时更方便多数裸题和常规场景我自己的习惯是如果题目没要求输出方案一律用一维写法省内存、代码短、不容易写乱。如果题目要求输出具体选了哪些物品我才会回到二维或者额外开一个二维 bool 数组记录转移路径。4. 细节即地狱初始化、边界条件和枚举方向的高频坑4.1 初值用 0 还是 -INF两种背包语义01背包 最常见的翻车点不是转移方程而是初始化。dp 数组到底初始化为 0还是初始化为负无穷取决于题目问的是不超过容量 V还是恰好装满容量 V。如果题目说背包容量为 V求能装的最大价值那么容量为 0 时可以装 0 价值容量为 5 时也可以什么都不装价值为 0。所以所有 dp[j] 初始化为 0 是对的因为空背包这个方案对任何容量都合法。如果题目说恰好装满容量 V意思是你必须选取若干物品使它们的总重量刚好等于 V装不满不算。这时候容量为 0 的背包是合法状态什么也不装价值 0但容量大于 0 的背包在初始状态下是不可达的所以初始化 dp[0]0dp[1..V]-INF一个足够小的负数。转移时如果 dp[j-w] 是 -INF说明这个状态不可达跳过它避免用非法状态更新出错误答案。最后如果 dp[V] 仍然是负数说明无法恰好装满。这个细节我踩过不只一次。有一次做一道装箱问题题目要求恰好装满我直接拿普通 01背包 模板一交答案全错。想了半天才意识到问题出在初始化上。从那以后我每次写背包题都先问自己一句dp[0] 的语义是什么dp[0] 初始化成 0 合不合法4.2 容量循环边界和重量为 0 的陷阱另一个常被忽略的问题是重量为 0 的物品。如果重量允许为 0一维倒序循环 jcapacity 到 jw即 j0会导致一个严重的 bug因为 w0内层循环条件 j0 永远成立dp[j] 会不断被 dp[j]v 更新同一件物品被无限次叠加。怎么处理最简单的办法是读入时判断如果 w0直接把 v 累加到一个全局 answer 上因为零重量的物品无论如何都应该拿拿了不占空间价值只增不减。然后这一件物品就不参与背包 DP。如果题目数据明确说了重量为正整数那你可以不处理但养成这个防御性习惯总没错。容量循环的另一个边界是 j 的起点。一行代码里写 for (int j capacity; j w; j--) 和写 for (int j capacity; j 1; j--) 然后里面再 if (j w) 判断效果是一样的但前者少了一半无效判断效率略高也更清晰。建议直接让循环从 capacity 开始到 w 结束把容量小于 w 的状态跳过因为根本装不下当前物品。4.3 数据范围与 C 编码习惯01背包 的经典数据范围是 n≤1000、V≤100000价值如果不超过 10^6总价值最大 10^9 级别int 够用。但如果 n 和 V 再大一点或者价值上限是 10^9累计总价值可能超过 2^31-1int 就会溢出。稳妥起见dp 数组用 long long读入也用 long long反正内存多不了多少。还要注意 MAXV 开多大。很多新手直接在代码里写 int dp[100000]结果测试数据容量是 100001越界访问本地跑得好好的OJ 上就 Runtime Error。我的习惯是数组按题目数据上限再加 5 或 10 个余量比如 maxCapacity 是 100000就开 100005。多开几个 int 的成本可以忽略但因为少开一个元素而数组越界调试成本可就大了。C 里别忘了 includealgorithmmax 函数在algorithm里定义。有些编译器可能通过iostream间接包含了它但这是不保证的跨平台代码里裸用 max 不 include algorithm很容易在某个环境里编译报错。这种小问题看起来不值一提但我见过太多人在 OJ 上因为这个 CE编译错误。5. 变式实战从最大价值到恰好装满方案计数输出方案5.1 恰好装满一眼看穿的初始化陷阱我们直接上一个典型变式。题目改成给定 n 种物品每种物品只能用一次问能否恰好凑出容量 V如果能最大价值是多少。这个问题的做法就是在基础 01背包 上改初始化没有其他变化。#include iostream #include algorithm using namespace std; const int MAXV 10005; const int INF 0x3f3f3f3f; int dp[MAXV]; int main() { int n, capacity; cin n capacity; for (int i 0; i capacity; i) dp[i] -INF; dp[0] 0; for (int i 1; i n; i) { int w, v; cin w v; for (int j capacity; j w; j--) { if (dp[j - w] ! -INF) { dp[j] max(dp[j], dp[j - w] v); } } } if (dp[capacity] 0) { cout 无法恰好装满 endl; } else { cout dp[capacity] endl; } return 0; }你可以试着把这个代码里的 -INF 换成 0再跑一组装不满的数据。比如容量 10只有一件重量 3 价值 5 的物品恰好装满版本应该输出无法恰好装满但如果初始化全为 0就会错误地输出 0因为 dp[10] 会保留初始值 0。这就是两种语义的区别。5.2 方案计数加法原理与 01背包 的结合另一种常见变式是凑出容量 V 一共有多少种方案。这时的 dp[j] 语义变了不再是最大价值而是方案数量。状态转移的逻辑也变成dp[j] dp[j-w]意思是能凑出容量 j-w 的方案加上这件物品后就能凑出容量 j所以方案数累加。#include iostream using namespace std; const int MAXV 10005; long long dp[MAXV]; // 方案数可能很大用 long long 或取模 int main() { int n, capacity; cin n capacity; dp[0] 1; // 容量 0 只有一种方案什么都不选 for (int i 1; i n; i) { int w; cin w; for (int j capacity; j w; j--) { dp[j] dp[j - w]; } } cout dp[capacity] endl; return 0; }注意这个问题的初始化。dp[0]1其他为 0因为凑出容量 0有一种方案空集而凑出容量 kk0初始没有方案。这里不能用 -INF因为我们需要计数而不是比大小。方案计数问题在很多 OJ 上会要求取模比如答案对 10^97 取模那时候每加一次就取一次模。这个很简单但很容易忘。5.3 输出具体选中的物品集合最后一个变式是输出方案。很多人以为一维 dp 没法回溯其实可以额外开一个二维 bool 数组 record[i][j]记录在计算前 i 件物品、容量 j 时是否选择了第 i 件物品。DP 跑完后从最后一件事往前回溯如果 record[i][j] 为 true说明第 i 件物品被选了把 j 减去 weight[i]继续看 i-1否则直接看 i-1。最后把选中的物品编号收集起来。#include iostream #include vector using namespace std; const int MAXN 105; const int MAXV 10005; int weight[MAXN], value[MAXN]; int dp[MAXV]; bool record[MAXN][MAXV]; int main() { int n, capacity; cin n capacity; for (int i 1; i n; i) { cin weight[i] value[i]; } for (int i 1; i n; i) { for (int j capacity; j weight[i]; j--) { if (dp[j - weight[i]] value[i] dp[j]) { dp[j] dp[j - weight[i]] value[i]; record[i][j] true; } } } cout 最大价值: dp[capacity] endl; vectorint picked; int j capacity; for (int i n; i 1; i--) { if (record[i][j]) { picked.push_back(i); j - weight[i]; } } cout 选中的物品编号: ; for (int id : picked) { cout id ; } cout endl; return 0; }这里有个细节值得说明为什么 record 数组是二维的不能像 dp 那样压缩成一维因为回溯时我们需要知道在某个容量 j 下第 i 件物品是否被选这个信息只存在于二维维度压缩掉就丢了。所以凡是涉及输出方案的题目要么用二维 dp 直接回溯要么额外开二维记录数组空间上要做好心理准备。我在实际做题中发现很多同学一看到输出方案就慌其实是没建立决策记录这个概念。DP 的每一次转移都是一次决策只要把决策记录下来回溯只是从终态倒着走一遍而已。理解了这一点类似的问题就一通百通。另外一个个人习惯做背包问题的题目我永远先确定 dp[j] 的语义再想初始化最后写循环。顺序不能乱。语义错了代码再对也是错初始化错了边界数据必挂循环方向错了结果就是完全背包和 01背包 的差别。这三个检查点顺序过一遍能帮你省下大量调试时间。特别是当你从别的语言转过来写 C 时数组越界、int 溢出、忘 include 头文件这些小毛病一定要靠规范和习惯来堵住。