1. 从“背包九讲”说起为什么01背包是算法入门的必修课如果你接触过动态规划大概率听过“背包九讲”这个名字。很多人在准备面试、参加竞赛或者自学算法时第一个认真啃的模型就是01背包。它看起来只是“选或不选”的简单决策但背后那一套状态定义、状态转移、滚动数组优化的思路几乎贯穿了你后面会遇到的所有DP问题——LIS、区间DP、树形DP本质上都脱胎于这套思想。01背包问题的标准描述是这样的有N件物品和一个容量为V的背包第i件物品的重量是w[i]价值是v[i]每件物品只能用一次求解在不超过背包容量的前提下能装入的物品最大总价值是多少。“每件物品只能用一次”这八个字就是“01”的含义——每个物品只有选1和不选0两种状态。这篇文章我会从零开始用C一点一点把二维DP、一维滚动数组优化、初始化细节、常见变种全部拆开讲透最后附上我实际刷题时踩过的坑和排查方法。不管你是刚学C的萌新还是想系统复习DP的老手都建议花二十分钟把这篇文章过一遍看完再去刷LeetCode的416题分割等和子集、494题目标和你会发现套路极其相似。2. 暴力思路的“天花板”为什么非要用动态规划第一次看到01背包很多人本能会想这不就是组合枚举吗把所有物品的子集列出来算一下总重量和总价值取最大值不就行了思路没错但复杂度完全扛不住。N件物品的子集数量是2的N次方N20的时候大约是100万看着还行N30就到了10亿级别已经明显跑不动了等你面对N100、N1000这种竞赛和数据流场景暴力枚举在实际运行中根本不可能完成。那贪心行不行按单位重量价值排序优先装性价比高的这个策略在很多情况下是错的因为背包是“整件装”的不是你买水果可以切一块下来。一个反例就能说明问题容量10物品A重量6价值12单位价值2物品B重量5价值10单位价值2物品C重量5价值10单位价值2。按性价比优先选A剩下容量4什么都装不了总价值12但选BC总重量10总价值20明显更优。贪心处理不了这种“容量碎片”问题它只看局部最优无法统筹全局。所以需要动态规划。DP的核心思路不是枚举所有子集而是把大问题拆成重叠的子问题前i件物品在容量j下的最优解只跟前i-1件物品的状态有关。这个“只跟上一层有关”的性质让状态可以被复用也让我们能用一个二维表格逐步填出最终答案。3. 二维DP先把状态定义和转移方程吃透3.1 状态定义与核心转移方程的由来我们用dp[i][j]表示考虑前i件物品背包容量为j时能够获得的最大总价值。那么对于第i件物品它只有两种结局不放进背包或者放进去。这两种选择对应两个值不选第i件物品dp[i][j] dp[i-1][j]。意思是我直接沿用前i-1件物品在容量j下的最优解第i件物品不参与决策。选第i件物品前提是容量j必须大于等于w[i]否则放不下。如果能放那么价值就是dp[i-1][j-w[i]] v[i]。这里的dp[i-1][j-w[i]]表示给第i件物品腾出w[i]的空间后前i-1件物品在剩余容量下的最大价值再加上第i件物品的价值。所以状态转移方程就是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])当j w[i]如果j w[i]那只能不选dp[i][j] dp[i-1][j]。为什么要这么定义因为dp[i][j]的定义天然具备“无后效性”——当前状态只由前一个阶段的状态推导而来不关心你是怎么走到前一个状态的。这正好符合动态规划的两个核心要求最优子结构和无后效性。3.2 手推一遍DP表比看十遍代码都有用光看公式容易飘我建议你自己拿纸笔画一张表。我举个具体例子背包容量V5有4件物品物品编号重量w价值v123212334422初始化dp数组全为0因为前0件物品不管是多少容量价值都是0。然后一行一行填。填充规则就一条比较“不选当前物品”的dp[i-1][j]和“选当前物品”的dp[i-1][j-w[i]]v[i]取大者。拿第1件物品w2,v3来说j0和j1时容量不够dp[1][0]0dp[1][1]0。j2开始dp[1][2]max(dp[0][2], dp[0][0]3)3。j3dp[1][3]max(dp[0][3], dp[0][1]3)3。以此类推j4时为3j5时为3。第2件物品w1,v2加进来后j1时dp[2][1]max(dp[1][1], dp[1][0]2)2。j2时dp[2][2]max(dp[1][2]3, dp[1][1]22)3。j3时dp[2][3]max(dp[1][3]3, dp[1][2]25)5。j4时dp[2][4]max(3, dp[1][3]25)5。j5时dp[2][5]max(3, dp[1][4]25)5。这样一直填到第4件物品最终dp[4][5]就是答案。我强烈建议你亲自把这个表填完填完你就明白为什么说DP的核心是“填表”而不是背代码。3.3 二维DP的C标准写法#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXV 1005; int w[MAXN], v[MAXN]; int dp[MAXN][MAXV]; int main() { int N, V; cin N V; for (int i 1; i N; i) { cin w[i] v[i]; } 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; }这里有两件事要提醒新手第一数组下标从1开始读入这样dp[0][j]0这个初始状态天然成立不用额外处理第二容量j的循环从0到V都要遍历因为即使某件物品放不下dp[i][j]也要被赋值为dp[i-1][j]保证表格连续性后面更大的容量可能会用到这个中间状态。4. 滚动数组优化把二维压成一维为什么必须倒序遍历4.1 压缩的原理二维DP的时间复杂度是O(NV)空间复杂度也是O(NV)。当N和V都到几千甚至上万时一个int二维数组直接能吃掉几十MB内存竞赛中经常直接爆内存。观察状态转移方程你会发现dp[i][j]只依赖dp[i-1][...]也就是说当前这一行只跟上一行有关再往前的行根本没用了。那我们大可不必开一个二维数组只需要保留“上一行”的数据边算边覆盖这就是滚动数组的思想。代码上最简单粗暴的压缩是直接去掉第一维用一维数组dp[j]表示“当前容量j下的最大价值”外层循环每次处理一件物品时不断更新这个数组。4.2 为什么内层循环必须从大到小此处是01背包最容易翻车的地方。如果内层循环j从V到w[i]倒序遍历一维DP的更新公式长这样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]); } }关键在于dp[j-w[i]]必须在本次物品处理前还是旧状态即没选过当前物品的状态这样dp[j] max(dp[j], dp[j-w[i]] v[i])就等价于二维的dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。如果j从小到大正序遍历比如j2算完dp[2]3等到j4时dp[j-w[i]] dp[2]已经被刚才那次更新覆盖了此时dp[2]3表示的是“已经装过一次当前物品”的状态。用它再去更新dp[4]相当于同一件物品被装了两遍这就变成完全背包了。我当年学的时候就是在这里反复踩坑。你可以在纸上模拟一下一件物品w2,v3容量V4正序遍历会发生什么初始化dp全0j2时dp[2]max(0, dp[0]3)3j3时dp[3]max(0, dp[1]3)3j4时dp[4]max(0, dp[2]3)6直接装了两件。但01背包每件物品只能一次正确答案应该是3。倒序则不会因为更新dp[4]时dp[2]还是上一轮物品处理完后的旧值没有被动过。4.3 一维优化的C完整代码#include bits/stdc.h using namespace std; const int MAXV 10005; int dp[MAXV]; int main() { int N, V; cin N V; for (int i 1; i N; i) { int w, v; cin w v; for (int j V; j w; j--) { dp[j] max(dp[j], dp[j-w] v); } } cout dp[V] endl; return 0; }5. 初始化不是小事恰好装满与不超过容量的区别很多题不会直接问“不超过容量最大价值”而是问“恰好装满背包的最大价值”这两者的初始化方式完全不同。如果要求“不超过容量”所有dp[j]初始化为0即可。因为容量没用完也合法什么都不装价值当然是0这是一个合法的起点。如果要求“恰好装满”dp[0]初始化为0容量0刚好装满什么都不装但dp[j]j0要初始化为负无穷比如-1e9。为什么因为容量j在没有物品时不可能被“恰好装满”这是一个非法状态。用负无穷标记非法后续转移时如果dp[j-w[i]]是负无穷即使加上v[i]还是负无穷max操作会自动忽略这个非法状态。举个例子同样是前面那组数据如果要求恰好装满最终dp[5]5选物品2和3重量134不对这个要算准。让我重新算一下物品2重量1价值2、物品3重量3价值4加起来重量4价值6没装满5要装满5的话物品1重量2价值3 物品4重量2价值2 物品2重量1价值2 重量5价值7所以恰好装满容量5时最大价值是7。你看和“不超过容量”时能在容量5装出价值5的解不一样背包恰好装满的问题通常会要求你精打细算所有容量必须被完全利用或者允许部分浪费理解题意的区别至关重要。求方案数的初始化也有讲究如果题目问“装满背包的方案数”dp[0]1容量0有一种方案什么都不选其余dp[j]0然后状态转移改为dp[j] dp[j-w[i]]遍历顺序同样倒序。LeetCode 494题“目标和”就是这种套路的典型应用。6. 从01出发完全背包、多重背包、多维背包怎么变6.1 完全背包一改循环顺序就完事完全背包和01背包唯一的区别是每件物品可以用无限次。此时内层循环j从w[i]到V正序遍历这样dp[j-w[i]]可能已经被当前物品更新过从而允许同一件物品被多次选中。代码改动极小但语义完全不同面试时一定要说清楚为什么。6.2 多重背包二进制拆分是常用套路多重背包指第i件物品最多有c[i]件可用。最朴素的做法是把它拆成c[i]件01背包的物品但数量太大时会超时。竞赛常用的优化是二进制拆分把c[i]件物品拆成若干个“组”每组数量分别是1、2、4、8……这样任意0到c[i]的件数都能通过选若干组表示出来把O(c[i])的枚举复杂度降为O(log c[i])。拆分完就跑01背包模板不用单独写新的DP逻辑。6.3 多维背包状态维度加一维如果题目变成“重量体积两个限制”就是二维费用背包。做法很简单dp加一维变成dp[j][k]表示容量j且体积k下的最大价值转移时同时考虑两个限制for (int i 1; i N; i) { for (int j V; j w[i]; j--) { for (int k U; k z[i]; k--) { dp[j][k] max(dp[j][k], dp[j-w[i]][k-z[i]] v[i]); } } }我之前在做“多重背包”的二进制优化加多维费用混合题时经常把维度搞混后来养成了一个习惯先把问题分类确定“有几个限制条件就开几维状态每个限制对应一维容量”再套模板就稳很多。7. 我实际调试中踩过的坑列成一张避坑清单这块算是我自己刷题多年总结出的“血泪史”。新手很容易在这些地方卡几个小时数组越界。dp数组开小了V和N没加一点余量。我习惯开MAXN5、MAXV5防止边界检查的疏漏。循环顺序搞反。01背包内层倒序、完全背包内层正序这是硬规矩背下来不丢人理解了自然记得住。忘记处理j w[i]的情况。一维写法中j从V到w[i]循环就已经保证了j小于w[i]时不会更新没问题。但二维写法如果少了if判断数组就会当前行变成0导致后续计算错误。背包容量和物品数量搞混。外层到底循环物品还是容量01背包必须外层物品、内层容量因为每个物品最多选一次。反过来写你会得到一堆错误答案而且很难debug。答案输出错位。一维DP结束后dp[V]就是答案但有些题会让你输出具体选了哪些物品这时一维DP就做不了必须用二维DP倒推。倒推的方法是从dp[N][V]出发如果dp[i][j] dp[i-1][j]说明第i件物品没选j不变否则说明选了j减去w[i]然后i减1继续。这个技巧在处理“输出方案”的题目里几乎是标准操作平时可以多练练。调试技巧方面我会在关键位置打印中间dp数组尤其是内层循环跑完一件物品后把dp[0…V]全打出来肉眼检查状态转移是否符合预期。这比断点调试管用一万倍因为DP的错误往往是整体性的单步跟踪反而看不出问题。8. 除了刷题01背包还能用在哪些真实场景别以为背包问题只活在OJ和面试题里现实中它的应用场景非常多。资源分配问题预算有限要在多个候选项目中选择投资组合每个项目有成本重量和预期收益价值每个项目只能投一次这就是一个标准的01背包。类似地服务器给你的程序分配算力每个任务占用资源不同、产出不同选哪些任务上线也是背包问题的工程化表达。物流装箱货车载重有限一批货物有不同的重量和运费收入挑哪些货装车能赚最多同样是01背包。甚至航班行李限额也是一样行李架空间有限你在家纠结带哪些东西出门时其实就在做一次小规模背包DP。市场营销场景中选择推广渠道组合每个渠道预算固定预计带来用户量不同预算封顶的情况下最大化总转化量本质上也是多维背包问题。理解了这个模型你会发现很多“取舍优化”的问题都能翻译成背包语言。这也是我很推荐算法初学者先把背包吃透的原因它有具体的现实映射比抽象的图论问题更好理解又能帮你建立DP的思维框架。我个人在带新人时反复强调一个方法拿到背包题先不要急着写代码先大声说出“状态是什么、转移是什么、初始化和遍历顺序是什么”四句话能讲清楚代码就不会错。反之哪怕代码背下来了换个问法就懵。最后再分享一个小技巧背包问题里“能否装满容量j”这种问法可以用布尔数组dp[j]表示是否能组合出重量j转移时dp[j] dp[j] || dp[j-w[i]]本质上还是01背包。LeetCode 416题“分割等和子集”就是让判断数组能否分成两个子集使和相等这题我每次带人入门DP都会推荐因为它把01背包的“选/不选”内核嵌套在了一个特别生活化的场景里适合用来检验今天学的所有内容。