背包问题几乎是每个学算法的人绕不开的一道坎而01背包又是所有背包问题的地基。我第一次在C里写01背包时以为就是两层循环套个max结果一提交要么答案偏小要么直接超内存后来才明白理解状态定义比背模板重要得多。这篇文章把01背包的DP原理、C实现、空间优化、常见变体和调试经验一次讲透适合刚学动态规划的初学者也适合准备笔试面试想快速捡起来的选手。1. 先搞清楚01背包在解决什么问题1.1 一个具体的场景想象你有一个容量为W的背包地上有n件物品每件物品有自己的重量w[i]和价值v[i]。每件物品你只能决定“拿”或者“不拿”不能拿半件也不能重复拿。问在不超过背包容量的前提下能带走的最大总价值是多少这就是01背包问题。“01”这个名字本身就点明了核心——每件物品只有0和1两种状态选还是不选。这个看似简单的问题却是动态规划入门的经典模型后面所有背包问题基本都是在这个骨架上做扩展。我用一个具体例子来贯穿全文假设背包容量W10一共有5件物品物品编号重量w价值v126223365454546这个例子数据不大后面我可以带你手推一遍DP表格把过程看明白。1.2 为什么不能直接贪心很多人第一反应是按“性价比”排序优先装单位重量价值最高的物品不就行了我们来试试。5件物品的性价比分别是物品1是3物品2是1.5物品3约0.83物品4是0.8物品5是1.5。按性价比排序装先装物品1重量2价值6再装物品2重量4价值9再装物品5重量8价值15此时剩余容量2装不下物品3和4。总价值15。但真正的答案是多少背包容量10可以选物品12/6、物品36/5、物品54/6总重量12超了再试物品1物品3物品2重量10价值65314物品1物品4物品5重量11超了物品3物品4重量11超了物品1物品2物品5重量8价值63615物品2物品3物品1重量10价值14。看起来15好像已经不小了。那再换一组数据背包容量10两件物品物品A重量8价值9物品B重量7价值7。性价比A是1.125B是1贪心会选A得到9。但正确答案是选B然后还能不能塞别的如果只有这两件选A价值9选B价值7那还是A。所以这个例子不够好。换个经典反例容量10物品A重量6价值12性价比2物品B重量5价值9性价比1.8物品C重量5价值9性价比1.8。贪心选A剩余容量4什么都装不下总价值12。但正确答案是BC重量10总价值18。这下很直观了贪心只看单件效率忽略了“剩余空间能不能凑出更大价值”的组合效应。01背包问题天然带有组合优化的性质局部最优拼不出全局最优必须用动态规划。1.3 状态设计与转移方程动态规划的核心就是定义状态。01背包的定义方式非常经典设dp[i][j]表示“从前i件物品中选放入容量为j的背包能获得的最大总价值”。注意这个定义里“前i件”是一个范围“容量j”是一个限制。处理第i件物品时其实只有两种决策不选第i件物品那么问题变成从前i-1件物品中选容量还是j即dp[i-1][j]。选第i件物品前提是背包容量j至少能装下w[i]。一旦选了价值增加v[i]但背包剩余容量变成j-w[i]前面i-1件物品只能在剩余容量里选即dp[i-1][j-w[i]] v[i]。所以状态转移方程就是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) (j w[i]) dp[i][j] dp[i-1][j] (j w[i])这个方程几乎可以背下来但更重要的是看懂它背后的“做决策”思想。每一件物品都基于之前的状态做一次选择前面所有选择的组合都被压缩在dp数组里了。为了方便C实现通常把物品编号从1开始dp数组的行数是n1列数是W1。dp[0][j]表示一件物品都不选不管容量多少价值都是0。2. 二维数组实现先跑通再优化2.1 基础C代码二维版本是理解01背包最直观的写法也是面试时和面试官讲思路的最佳载体。先上完整代码#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXW 1005; int w[MAXN], v[MAXN]; int dp[MAXN][MAXW]; int main() { int n, W; cin n W; for (int i 1; i n; i) { cin w[i] v[i]; } for (int i 1; i n; i) { for (int j 0; j W; 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][W] endl; return 0; }这是最经典的二维DP写法。代码量不大但有几个细节我想单独拿出来说。2.2 几个容易忽略的细节为什么j要从0循环到W而不是从w[i]开始因为dp[i][j]里j代表背包容量容量小于w[i]的状态虽然不能选第i件物品但需要继承dp[i-1][j]的值。如果只从w[i]开始循环那j w[i]这些格子就没有被赋值后面用到时会出现未初始化的随机值。为什么dp数组要定义成MAXN * MAXW这么大如果n和W都是1000开二维数组是1005×1005大约100万个int内存4MB左右完全没问题。但你要知道这个二维数组是O(nW)的空间复杂度当n和W都到10000时数组1亿个int内存400MB直接爆掉。这也是后面要讲滚动数组的原因。为什么物品编号从1开始这是C里数组和循环配合时的一个小习惯。如果从0开始状态方程里w[i]和v[i]的下标需要同步调整逻辑上容易乱。从1开始dp[0][...]天然表示“前0件物品”的空状态循环也更顺。2.3 手推一遍DP表格光看代码不如亲手推一遍。用前面的数据n5W10初始dp[0][0..10]全是0。第1行只考虑物品1重量2价值6j0,1时容量小于2dp[1][0]0, dp[1][1]0j2..10时可以选物品1dp[1][j]6第2行加入物品2重量2价值3j2时max(dp[1][2]6, dp[1][0]33)取6j4时max(dp[1][4]6, dp[1][2]39)取9j6时max(dp[1][6]6, dp[1][4]39)取9j8时max(dp[1][8]6, dp[1][6]39)取9j10时max(dp[1][10]6, dp[1][8]39)取9第3行加入物品3重量6价值5j6时max(dp[2][6]9, dp[2][0]55)取9j8时max(dp[2][8]9, dp[2][2]56511)取11j10时max(dp[2][10]9, dp[2][4]59514)取14第4行加入物品4重量5价值4j5时max(dp[3][5]9, dp[3][0]44)取9j10时max(dp[3][10]14, dp[3][5]49413)取14第5行加入物品5重量4价值6j8时max(dp[4][8]11, dp[4][4]69615)取15j10时max(dp[4][10]14, dp[4][6]69615)取15最终dp[5][10]15。这就是背包容量10时的最大价值。看到没整个过程其实是在一张二维表上不断做取max的决策每一行都依赖上一行。2.4 这个版本的复杂度时间复杂度两层循环外层n内层W所以是O(nW)。这个复杂度对01背包来说是“标配”没法再低了因为每个状态都要算一遍。空间复杂度O(nW)的二维数组。n和W在1000级别二维没问题。但如果n10000W10000时间1亿次操作勉强能跑空间直接报废。所以笔试里如果看到n和W都比较大就要立刻想到用滚动数组优化空间。3. 空间优化一维滚动数组3.1 核心观察每行只用上一行回到状态转移方程dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]也就是第i行只依赖第i-1行再往前的行根本没再用到。那我们何必保留整个二维表直接用一个一维数组dp[j]在遍历物品时不断“滚动更新”就行了。滚动数组这个名字很形象——像滚轮一样用新值覆盖旧值只留当前需要的那一层。但这里有个关键坑更新一维数组时j到底应该从小到大还是从大到小3.2 为什么要倒序遍历直接说结论一维优化的01背包必须让j从W倒着循环到w[i]。理由是一个一维数组同时承载着dp[i-1]和dp[i]两个逻辑层如果正序遍历dp[j-w[i]]可能已经被本轮的更新覆盖导致同一件物品被反复选择相当于退化成了完全背包问题。我拿刚才的物品1重量2价值6举例。假设一维数组初始全0如果正序遍历jj2时dp[2] max(dp[2], dp[0]6) 6j4时dp[4] max(dp[4], dp[2]6) dp[2]已经是6了再加6得到12这就出问题了明明只有一件物品1容量4的时候居然算出12相当于把同一件物品装了两遍。因为j4时用的dp[2]已经被本轮更新过了那不再是“前i-1件物品”的状态而是“已经考虑过选第i件物品”之后的状态。倒序遍历就能避免这个问题先算j10dp[10] max(dp[10], dp[8]6)这时dp[8]还是上一轮的值0再算j9,j8...一直到j2整个过程里任何j-w[i]都小于当前j且还没有被本轮访问过所以拿到的都是上一轮的数据这就是倒序遍历的本质保证每一件物品只被考虑一次。3.3 优化后的完整代码#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXW 1005; int w[MAXN], v[MAXN]; int dp[MAXW]; int main() { int n, W; cin n W; for (int i 1; i n; i) { cin w[i] v[i]; } for (int i 1; 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] endl; return 0; }这段代码短到令人发指但每一行都值得琢磨。内层循环j从W开始到w[i]为止小于w[i]的容量根本装不下当前物品不需要更新dp[j]保持上一轮的值。这比二维版本还少了if判断代码更简洁。3.4 还能不能再省时间时间复杂度O(nW)是跑不掉的但常数上还有优化空间。比如内层循环上界可以不用W而是用当前所有已考虑物品的重量总和min(W, sumW)。当物品很多但总重量不大时这个优化能省不少无效更新。int sumW 0; for (int i 1; i n; i) { sumW min(W, sumW w[i]); for (int j sumW; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }sumW表示前i件物品在不超过背包容量的前提下总重量最多能到多少。超过W的部分没有任何意义直接截断。这个优化不需要记但理解了能帮你应对那些“重量很小但物品很多”的输入数据。3.5 空间优化后还能输出方案吗一维数组只记录了最优值没有记录路径。如果题目要求输出选了哪些物品需要额外开一个二维标记数组choice[i][j]表示“容量j时第i件物品是否被选择”然后从dp[n][W]倒着回溯。这里给一个完整示例代码int n, W; cin n W; for (int i 1; i n; i) cin w[i] v[i]; vectorvectorbool choice(n 1, vectorbool(W 1, false)); vectorint dp(W 1, 0); for (int i 1; i n; i) { for (int j W; j w[i]; j--) { if (dp[j - w[i]] v[i] dp[j]) { dp[j] dp[j - w[i]] v[i]; choice[i][j] true; } } } // 回溯输出 vectorint ans; int j W; for (int i n; i 1; i--) { if (choice[i][j]) { ans.push_back(i); j - w[i]; } }这个标记数组允许我们在算出最大值后逆向还原选择路径。注意回溯时j要减去w[i]因为选了第i件物品后剩余容量会减少。4. 常见变体与边界情况4.1 要求恰好装满背包怎么办01背包最常见的变形是背包容量为W问恰好装满背包时能获得的最大价值是多少。如果装不满就不算有效解。做法是在初始化上做文章。最大值问题里不能刚好装满的状态要设置成负无穷让它在max里永远不被选中vectorint dp(W 1, -1e9); dp[0] 0; for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } // 如果dp[W]仍然是负数说明无法恰好装满 if (dp[W] 0) cout 无法恰好装满 endl; else cout dp[W] endl;为什么dp[0]必须是0、其余是负无穷因为容量为0时一件物品都不装恰好装满且价值为0这是一个合法状态。而容量为其它值的状态一开始并没有任何物品组合能刚好凑到这个容量只能用“负无穷”标记不可达。随着物品逐渐加入不可达状态会被逐步更新为可达状态。如果最后dp[W]还是负无穷说明凑不出来。注意这里不能简单用INT_MIN因为dp[j - w[i]] v[i]有可能在INT_MIN上继续加导致int溢出所以用-1e9这类足够小又不会溢出的值比较稳妥。4.2 求最小价值怎么办如果题目改成“装到一定容量求最小价值”思路完全对称。初始化和max改成min即可但要把其余状态设成正无穷vectorint dp(W 1, 1e9); dp[0] 0; for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] min(dp[j], dp[j - w[i]] v[i]); } }这类题不多但理解了最大值最小值就是顺手的事。4.3 求方案总数还有一类计数问题容量恰好为W的方案数有多少种。状态定义变成dp[j]表示“凑出容量j的方案数”转移方程也变成累加vectorint dp(W 1, 0); dp[0] 1; for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] dp[j - w[i]]; } }这里dp[0]1的语义是“容量0有一种方案什么都不选”。每次加入一件物品时新的组合数等于原组合数加上“腾出w[i]容量后的组合数”。注意答案可能很大题目一般会要求取模。这个变体在动态规划题里非常常见比如凑硬币问题。4.4 01背包、完全背包、多重背包怎么区分很多初学者被三种背包绕晕。其实关键就在内层循环的方向上01背包每件物品最多选一次内层倒序遍历完全背包每件物品可以选无限次内层正序遍历多重背包每件物品有数量限制可以二进制拆分后转成若干个01背包或者用单调队列优化一句话记忆内层循环的顺序决定了“同一件物品能不能被重复选择”。如果看到“每件物品最多选一次”就是倒序看到“每件物品可选无数次”就是正序。这个判断比死记模板要可靠得多。5. 实战中的常见错误与排查技巧5.1 我踩过的五个典型坑问题现象根本原因解决办法结果比答案大很多内层循环写成正序变成完全背包改为j从W到w[i]倒序结果少了或全是0初始化数组时忘记将dp[0]设为0或循环范围写错检查dp数组初始化确认循环是j w[i]访问越界导致程序崩溃j - w[i]出现负数或数组开小了确保j w[i]再访问数组开到MAXW5大数相加溢出成负数使用INT_MIN或INT_MAX作为INF用-1e9或1e9作为正负无穷答案不对但样例能过状态定义理解错把dp[i]写成只装第i件物品回到定义确保dp[i][j]表示“前i件物品、容量j”5.2 调试口诀先小数据手动推再对拍每次写背包题卡住时我的流程是这样的先用一个n不超过3、W不超过10的小样例手动列出所有组合算出标准答案然后让程序输出整个dp表或一维dp数组的变化过程用肉眼把每一轮和手推结果对比找到第一处不一致的行列基本就能定位问题。以我平时写的调试代码为例在滚动数组版本里加一行输出看状态for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } cout 第 i 件物品处理后: ; for (int j 0; j W; j) cout dp[j] ; cout endl; }这个方法看起来土但真的能省掉很多瞎猜时间。尤其是刚学DP的朋友不要一上来就闷头跑大数据几行小样本就能把状态转移跑通。5.3 笔试面试中怎么答更稳面试官让你写01背包通常不是考你会不会背代码而是想看你有没有想清楚状态定义和转移逻辑。我建议答题顺序是先说暴力枚举思路每件物品有选/不选共2的n次方种方案数据大就不可行。引出动态规划定义dp[i][j]先写二维转移方程说明不选和选两个分支。分析时间和空间复杂度满足不了时再说滚动数组优化。最后写出一维版本并解释为什么倒序遍历。这样层层递进面试官会觉得你是真懂而不是只会默写模板。笔试做题时则可以直接用一维版本省内存又省代码量。5.4 我的一些小习惯我平时写01背包如果数据范围不大会直接用二维版本求最值用一维版本做优化因为二维版本在回溯方案时更直观。只有在空间告急时才被迫上一维。还有一点C里数组开到全局比开在main函数里更稳妥因为大的数组放栈上可能直接爆。我习惯把w、v、dp都定义成全局数组省心。最后分享一个我自己的体会动态规划题最重要的不是敲代码而是把状态定义说清楚。你如果能把“dp[i][j]表示什么”用一句话讲明白转移方程往往就顺理成章写出来了代码只是最后一步翻译。熟练之后你会发现01背包学的不只是这十几行代码而是一整套“把决策过程分层处理”的思维方式后面的完全背包、多重背包、区间DP、状压DP都是在同一个思路上加变化而已。