如果你正在学 C 算法入门准备把动态规划这块硬骨头啃下来那 01 背包问题大概率是你绕不开的第一站。这个题看着简单一堆物品一个背包每件东西要么装要么不装求能带走的最大价值。但就是这道题让无数人在“到底什么时候用 dp状态怎么转移”这个问题上卡了少则几天多则几周。我自己当年也是从暴力递归一路折腾到二维 dp再到一维优化中间踩了不少坑才真正理解它。这篇文章不打算给你堆术语而是想用我自己做题和带新人的经验把这题的思路、代码、坑一次讲透。你只要能跟着把下面的代码亲手敲一遍再画几张表基本上就能摸清动态规划的套路了。1. 01背包问题的本质先看懂这道题在问什么1.1 问题描述与一个贴近生活的例子01背包的标准描述是这样的有 n 件物品每件物品有自己的重量 w[i] 和价值 v[i]现在有一个容量为 C 的背包每件物品最多只能拿一次问在不超过背包容量的前提下最多能带走多大总价值。之所以叫“01”就是因为每件物品的状态只有两个0 表示不拿1 表示拿不存在拿半件或重复拿的概念。为了不让公式吓退你我习惯打个比方想象你要去野营行李箱容量有限帐篷、睡袋、炊具各有各的重量和“值不值得带”的评分你要在有限的空间里选出总评分最高的一套。这个比喻不是随便打打它和你后面在代码里做的事几乎一模一样对每一件物品做一次“要还是不要”的决策。还有一个很容易被忽略的点背包容量 C 和物品重量 w[i] 都是整数。整数这个性质非常关键因为后面要按容量开数组、建 dp 表正是靠容量离散成一格一格才能递推。如果容量是实数01背包就不能用这种经典解法得换思路。看懂这一点你才算真正进入状态。1.2 为什么暴力枚举撑不过 20 件物品刚接触这道题的人第一反应往往是枚举所有组合挑价值最大的一组。每件物品有选和不选两种可能n 件物品的组合数就是 2 的 n 次方。n10 时有 1024 种看起来不多n20 时超过一百万种n30 时已经超过十亿。实际竞赛或面试题里 n 通常到几百甚至上千暴力枚举直接彻底不可行。这里我就踩过坑早期做题n 只有 20 的时候我用 DFS 枚举加剪枝能跑过后来数据量一涨程序跑几十秒都不出结果这才老老实实去学 DP。所以千万别觉得“枚举剪枝能解决一部分就够了”你真正要掌握的是面对大规模数据时依然稳定高效的方法也就是动态规划。1.3 动态规划解决这个问题的底层逻辑DP 能解决这题靠的是两个关键性质子问题重叠和无后效性。所谓子问题重叠是指“前 i 件物品放进容量为 j 的背包”这个问题会被后面更大的问题反复引用。比如“前 5 件物品在容量 10 下的最优解”既可能是“前 6 件物品在容量 10 下不选第 6 件”时用到的子状态也可能是“前 7 件物品在容量 10 下选了第 7 件”时用到的子状态。如果每次都重新算代价极高但如果把每个子问题的答案记住后面直接查表就行。所谓无后效性是指一旦容量和前 i 件物品确定后面怎么决策只跟当前这个状态有关不需要关心之前具体选了哪些物品。今天做出的决定不会改变昨天已经定下来的事。这个性质保证了我们可以从小规模状态开始一步步推出大规模状态而不需要回看完整的选择历史。简单说DP 把“选哪些物品”这件复杂的事拆成了一连串“当前这件到底选不选”的小决策用一张表把每种情况的最优结果记下来避免重复计算。这是所有背包问题乃至大多数线性 DP 问题的共同骨架。2. 从暴力递归到记忆化搜索DP思路是怎么自然“长”出来的2.1 先写一个不优化的递归版本很多教程一上来就抛状态转移方程看起来很高大上但初学者根本记不住。我建议你先写一个最朴素的递归从第 n 件物品开始往前考虑定义 dfs(i, cap) 表示“从第 1 到第 i 件物品中在剩余容量 cap 下能获得的最大价值”。如果当前物品重量超过剩余容量就跳过否则就取“不装”和“装”两种选择的最大值。道理非常直观代码也短#include bits/stdc.h using namespace std; int n, C; vectorint w, v; int dfs(int i, int cap) { if (i 0) return 0; // 没有物品可选价值为 0 if (cap w[i]) return dfs(i - 1, cap); // 装不下跳过 return max(dfs(i - 1, cap), dfs(i - 1, cap - w[i]) v[i]); }这个版本的时间复杂度是 O(2^n)因为它会一路枚举所有组合。第一次跑通的时候你会发现n 稍微大一点程序就像卡死了一样。这不是电脑慢是算法本身就爆炸式增长。2.2 发现重叠子问题并记录结果当你真的运行这个递归n 稍微大一点就慢得离谱因为同样的 dfs(i, cap) 会被反复计算。比如 dfs(3, 5) 可能在很多分支里都出现过但每次都重新算一遍。这时候加一个二维数组 memo 来缓存结果思路几乎不用变——这就是记忆化搜索。它和最终的 DP 其实是同一套状态设计只是计算方向不同一个从上往下递归一个从底往上递推。vectorvectorint memo(n 1, vectorint(C 1, -1)); int dfs(int i, int cap) { if (i 0) return 0; if (memo[i][cap] ! -1) return memo[i][cap]; // 算过就直接返回 if (cap w[i]) return memo[i][cap] dfs(i - 1, cap); return memo[i][cap] max(dfs(i - 1, cap), dfs(i - 1, cap - w[i]) v[i]); }这样改完之后每个状态最多只计算一次时间复杂度降到了 O(n*C)。从枚举所有组合变成枚举“物品 x 容量”的表格这是本质性的飞跃。2.3 自顶向下的优缺点为什么入门还是要学迭代写法记忆化搜索是不是就完美了也不是。第一递归调用有栈开销n 很大或系统栈较小时可能爆栈第二很多进阶题目要求你在背包模型上继续优化比如滚动数组、单调队列、二进制分组这些几乎都是基于迭代 DP 的思路去做的。你可以把记忆化搜索当作理解工具用来搞懂状态设计和转移关系但真正写题时我更推荐用后面的二维迭代写法。另外从面试角度说大多数算法面试官看到你写递归会继续追问“能不能把递归改成递推”“能不能优化空间”。如果你只会递归版本现场改起来会比较慌。反过来如果你从一开始就理解迭代 DP那这些问题对你来说就是送分题。3. 二维DP表的构建状态定义和转移方程是核心中的核心3.1 dp[i][j] 的含义与边界初始化迭代写法的核心是建一张二维表 dp[i][j]。i 表示考虑了前 i 件物品j 表示当前背包的容量dp[i][j] 的含义是在前 i 件物品中挑选若干件总重量不超过 j 时能获得的最大总价值。初始化时i0 表示一件物品都没考虑无论容量 j 是多少价值都是 0所以整个第 0 行全为 0。这个初始化看起来简单但它是后面所有递推的起点。还有一个细节数组下标 j 要从 0 开始遍历到 C因为容量为 0 也是一种合法状态表示背包空着。先说一下环境我平时写算法题用 VSCode 配 MinGW-w64装好 C/C 插件就能编译运行。很多新手去搜 Microsoft Visual C Redistributable那通常是运行别人编译好的 Windows 程序才需要装的运行库自己写源码用 g 编译的话一般不用纠结这个。环境问题别卡太久能编译跑起来就行。3.2 转移方程的推导过程当从 i-1 走到 i 时第 i 件物品只有两种命运不选它那当前价值就是 dp[i-1][j]选它则前提是剩余容量够也就是 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])这里要特别注意的是选第 i 件时为什么要看 dp[i-1][j-w[i]]而不是 dp[i-1][j]。我举个例子你就明白了。假设当前容量 j5第 i 件物品重量 w[i]2那么选了第 i 件之后前 i-1 件物品最多只能占用容量 3也就是 5-23。所以你要找的是“前 i-1 件物品在容量 3 下的最大价值”而不是容量 5 下的最大价值。这个“预留容量”的思想是所有背包问题转移方程的命门。如果 j w[i]装不下当前物品那就只能不选dp[i][j] 直接等于 dp[i-1][j]。3.3 完整 C 实现与运行结果演示直接上一份可以跑通的完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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]; } vectorvectorint dp(n 1, vectorint(C 1, 0)); for (int i 1; i n; i) { for (int j 0; j C; j) { if (j w[i]) { dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]); } else { dp[i][j] dp[i - 1][j]; } } } cout dp[n][C] \n; return 0; }用下面这组数据测试4 5 2 3 1 2 3 4 2 2跑出来的答案是 7。选第 1 件物品重量 2价值 3和第 3 件物品重量 3价值 4总重量刚好是 5总价值是 7。你可以自己手动在纸上画一下这张 5 行 6 列的 dp 表从第 0 行开始一行一行填。很多人在这一步忽然就“开窍”了因为表填到一半你会发现每个格子都不是凭空来的而是从上一行某个格子加或跳过得到的。4. 空间优化到一维为什么必须倒着遍历容量4.1 从表格推导到滚动数组观察二维转移方程你会发现dp[i][j] 只和 dp[i-1][...] 这一行有关和更早的行没有关系。于是我们完全可以只保留一行数组每次更新时用这一行同时充当“旧行”和“新行”。这就是滚动数组也叫空间优化。为了更直观先做个对比方案时间复杂度空间复杂度代码难度适用场景二维 DPO(n*C)O(n*C)容易理解初学阶段、需要回溯方案一维滚动数组O(n*C)O(C)中等倒序易错竞赛、空间受限的题目空间复杂度从 O(n*C) 降到 O(C)在大容量大物品数的时候非常可观。比如 n1000C10000二维表要开一千万个 int约 40MB 内存一维数组只需要 40KB。竞赛中内存限制经常只有 64MB 甚至 32MB这时候空间优化就是救命稻草。4.2 一维代码与倒序遍历的原因一维版本长这样vectorint dp(C 1, 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]); } }这里最反直觉的就是第二层循环必须从 C 倒着遍历到 w[i]。核心原因是倒序遍历时dp[j-w[i]] 还是上一轮 i-1 的结果如果正序遍历dp[j-w[i]] 可能已经被本轮更新过那第 i 件物品就可能被重复选择结果就从 01 背包偷偷变成了完全背包。你可以把一行数组想象成一张纸条正着更新就是从左边到右边划后面的格子会用到前面刚写下的新值倒着更新就是从右边到左边划后面的格子永远读到的是上一轮留下的旧值。我们需要的恰好是旧值。4.3 一个必踩的坑正序遍历会把01背包变成完全背包我直接举个反例你一看就懂。容量 C4只有一件物品重量 2价值 3。正确答案是选一次价值 3。正序遍历j 从 2 到 4。dp[2] 更新成 3然后 j4 时dp[4] max(dp[4], dp[2] 3)因为 dp[2] 已经变成 3 了所以 dp[4] 变成 6。明明是同一件物品却被拿了两次。倒序遍历j 从 4 到 2。j4 时dp[4] max(dp[4], dp[2] 3)此时 dp[2] 还是旧值 0所以 dp[4] 3j3 时 dp[3]3j2 时 dp[2]3。答案正确。这类 bug 只看代码很难看出来加上一两个小测试用例立刻现原形。所以我的建议是把两种循环各写一遍对着小数据打印 dp 数组印象会非常深刻。你先踩过这个坑以后写背包题就不会再犯。5. 初始化陷阱恰好装满与不超过容量的区别5.1 两种问法对应的初始化方式同样是 01 背包题目可能会问“不超过容量 C 的最大价值”也可能会问“恰好装满容量 C 时的最大价值”。这两种问法代码只差一行初始化但含义完全不同。不超过容量的做法就是前面写的所有 dp[j] 初始化为 0因为什么都不装就是一种合法方案价值为 0。恰好装满的做法则是让 dp[0]0但 dp[1..C] 初始化为一个很大的负数比如 -1e9 或 INT_MIN/2const int NEG -1e9; vectorint dp(C 1, NEG); dp[0] 0;这样做的效果是只有从 dp[0] 出发一步步累加物品重量直到恰好等于目标容量对应的价值才是正数任何凑不到目标容量的状态都会一直保持为很大的负数在取 max 的时候不可能胜出。5.2 用负无穷初值过滤非法状态的原理为什么不用 -1 来初始化因为物品价值有可能为 0用 -1 会把“价值为 0 的合法方案”和“非法的凑不满状态”混淆。用很负的值可以保证非法状态永远比任何合法状态小从而被自动过滤掉。这里有个经验别用 INT_MIN 直接加因为负无穷加正数可能溢出。用 INT_MIN/2 或 -1e9 这种安全值既足够小又不会在加法运算时溢出。这个细节不少老手都吃过亏尤其是价值很大的数据一溢出就是未定义行为答案完全乱掉。5.3 附一个常见的判断技巧判断是哪种问法建议直接看题目措辞。出现“不超过容量”“最多能装下多大价值”基本就是第一种出现“恰好装满”“求装满时的最大价值”或者“若无法装满则输出 -1”这样的提示就是第二种。还有一个变体有些题会问“最少需要多少物品才能凑出某个价值”或者“装满背包的方案数”。这些问题本质上也依赖初始化方式所以推荐你把“不超过”和“恰好”两种模板都存下来做题时快速切换。6. 路径回溯如何知道背包里到底装了哪些物品6.1 利用 dp 表反推选择的物品很多初学者学会算最大价值后就停了但实际项目或面试里经常会被追问“方案是什么选了哪几件”这时候二维 dp 表就派上大用场。从 dp[n][C] 开始往前反推如果 dp[i][j] dp[i-1][j]说明第 i 件物品没有被选否则说明选了第 i 件此时容量 j 变成 j-w[i]同时把物品 i 记下来。这里的逻辑很直接既然 dp[i][j] 大于 dp[i-1][j]那说明第 i 件物品的加入让价值变高了它一定在最优方案里。6.2 从二维表反推与一维方案反推的差异如果你用的是优化后的一维数组反推会麻烦一些因为旧行的信息被覆盖了。想在不牺牲空间的情况下反推通常得额外记录一个二维布尔数组或者干脆保留完整二维表。我的建议是初学阶段老老实实保留二维表来练回溯等熟悉之后再考虑用一维数组只求价值。毕竟回溯不是每道题都要求但一旦要求你手里得有完整的决策历史才能还原方案。6.3 C 回溯实现代码基于二维 dp 表回溯的代码vectorint chosen; int j C; for (int i n; i 1; --i) { if (dp[i][j] ! dp[i - 1][j]) { chosen.push_back(i); j - w[i]; // 容量减少继续往前找 } } reverse(chosen.begin(), chosen.end());当 dp[i][j] 和 dp[i-1][j] 恰好相等时说明选和不选价值一样这种并列情况随便记录一种即可。上面代码会把第 i 件判为“没选”这不影响价值的正确性只是方案可能和题解不同。如果有“输出字典序最小方案”这种要求就需要额外设计不过那是后话了。7. 从01背包延伸出去的DP变形题附练习建议7.1 完全背包、多重背包、分组背包与01背包的联系01 背包是所有背包问题的地基。完全背包只是把“每件只能选一次”改成“每件可以选无限次”代码变化极小把内层循环 j 从 C 到 w[i] 改成从 w[i] 到 C 正序遍历即可。多重背包加上数量限制每种物品最多选 k 个分组背包每组最多选一件。这些变体看着复杂但本质都是“选与不选选多少”的决策问题。理解了 01 背包后面这些基本都是小改。我见过很多人一上来就刷一堆背包变体结果连 01 背包的倒序都讲不清这很吃亏。背包九讲里的东西再多也是从 01 背包这个地基长出来的。7.2 常见变体二维费用、依赖关系、求方案数还有二维费用背包比如重量和体积两个限制条件那就把 dp 数组加一维依赖背包比如买了主件才能买附件求方案数则把转移方程里的 max 改成求和。另一个进阶方向是当物品重量范围很大、价值范围相对较小的时候可以把 dp 数组的维度反过来用 dp[v] 表示“达到价值 v 所需的最小重量”。这个技巧很多竞赛题会考它不是什么黑魔法依然是 01 背包的换皮。7.3 给初学者的刷题路线最后给一条亲测好走的路线先把这篇的代码打一遍确保能独立写出二维和一维两个版本然后找两到三题裸题练手比如 HDU 2602 Bone Collector 和洛谷 P1048 采药再试试 P1060 开心的金明感受一下依赖背包的味道。每次遇到不会的题先自己画二维表再查题解效果比直接看代码好得多。我见过最快的学员就是用这个方法一周内把背包专题吃透的。抛开各种技巧不说我最想强调的是01 背包真的值得你多花时间亲手推几遍表。我第一次理解滚动数组是在纸上画了十几个格子之后而不是在看完某篇博客之后。希望这篇也能让你少走一点我当时走过的弯路。