0-1背包问题几乎是每一门《算法设计与分析》课程的“必考点”也是动态规划入门时最容易让人卡住的一道坎。网上讲这个问题的文章一抓一大把但很多要么直接甩公式要么只给代码不讲为什么看完似懂非懂换个题目又不会了。我当年学的时候也在这上面折腾了不少时间所以这次干脆把0-1背包的动态规划解法从头到尾彻底拆一遍包含状态定义、转移方程、手算填表、一维数组优化、回溯找具体方案、初始化陷阱以及考试和面试里最常见的那些变形考法。全文没有任何跳步你只要能静下心看完一定能真正把它吃透。1. 暴力递归的瓶颈为什么0-1背包不能靠简单的枚举在正式进入动态规划之前先回到问题的起点。0-1背包的题面是这样的有一个容量为W的背包面前有n件物品每件物品有自己的重量w[i]和价值v[i]。现在要在不超过背包容量的前提下从这些物品中挑出若干件使得装入背包的总价值最大。每件物品只有两个选择——装进去或者不装进去不存在“装一半”这种操作所以才叫0-1背包。初学者最容易产生的疑问就是那我把所有组合都枚举一遍找出价值最大的那一组不就行了吗确实理论上可以但现实很骨感。n件物品每件有“选”和“不选”两种状态总的组合数是2的n次方这个增长速度是爆炸性的。用具体数字感受一下假设n10也就是10件物品组合数大概是1024种手算都能接受。但n增加到30组合数超过10亿n60时组合数已经超过10的18次方普通计算机一秒钟能执行的运算量也不过是10的8到9次方量级全部枚举根本跑不完。算法设计与分析这门课里反复强调的“复杂度分析”在这里第一次展现出它的实际意义。对于0-1背包的暴力枚举 - 组合总数2^n - 时间复杂度O(2^n) - 空间复杂度O(n)递归栈或组合生成空间如果你用递归来实现暴力枚举其实就是在构造一棵深度为n的二叉树。树的每一层对应一个物品左分支代表“不选”右分支代表“选”。走到叶子节点时统计一下当前路径上选的物品总重量和总价值如果重量不超过背包容量就用这个价值去更新答案。这个思路非常直觉代码写起来也不难但它的致命伤就是前面说的指数级复杂度。我在实际教学中发现很多同学知道暴力不可行却说不出为什么动态规划能比暴力快那么多。要理解这一点得先看清楚暴力搜索的过程里到底浪费了什么。我画过一棵递归搜索树来观察。以4件物品为例搜索树从根节点出发经过4层决策到达叶子理论上应该有16个叶子节点。但你仔细看中间那些节点的状态就会发现大量不同的决策路径到达了完全相同的“当前正在处理第i件物品、剩余容量为j”的状态。比如先看第1件物品选不选再看第2件物品选不选和先看第2件再看第1件最终到达第3件物品时如果剩余容量相同这两个分支后面的所有决策就是完全重复的计算。换句话说暴力搜索是把同一个子问题反复计算了一遍又一遍。动态规划的核心思想就是把这种重复计算的结果保存下来下次再遇到直接查表而不是重新递归。这就是“用空间换时间”的经典体现。想通这一点动态规划的大门就算真正推开了。2. 状态设计与转移方程dp[i][j]从哪来、到哪去0-1背包动态规划解法里最重要的一步就是定义状态数组。很多同学在这里犯迷糊不知道该把哪些维度放进状态里。其实思路很简单你要问自己做决策做到一半的时候当前局面需要用哪些信息来描述才能决定后面的路怎么走。对于0-1背包有两样信息是必不可少的一是现在已经处理到了哪些物品也就是“前i件物品”这个范围二是背包当前的剩余空间。于是就有了最经典的状态定义dp[i][j] 从前i件物品中挑选若干件装入容量为j的背包时能获得的最大总价值注意这里的下标含义。i的取值范围是0到nj的取值范围是0到W。dp[0][j]表示一件物品都不选时容量再大价值也是0dp[i][0]表示背包容量为0时什么都装不下价值也是0。状态定义好了接下来想状态转移方程。处理第i件物品时我们面临两个选择第一个选择是不选第i件物品。那问题就退化成“从前i-1件物品中选装入容量为j的背包”也就是dp[i-1][j]。第二个选择是选第i件物品。选了它就要占用w[i]的重量前提是j w[i]。一旦选了背包剩余容量变成j - w[i]前面i-1件物品就要在这个更小的容量下做最优选择即dp[i-1][j-w[i]]最后再加上第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]为什么这个转移是对的这里其实用到了动态规划的两个基石最优子结构和无后效性。最优子结构指的是全局最优解一定包含了子问题的最优解。具体到这个问题如果“从前i件物品中选若干件装入容量j”的最优方案里包含了第i件物品那么去掉第i件物品后剩下的部分一定也是“从前i-1件物品中选若干件装入容量j-w[i]”的最优方案。这一点可以用反证法证明如果剩下的那部分不是最优的那就能用更优的子方案替换它从而得到全局更优的方案产生矛盾。无后效性指的是当前状态一旦确定后续状态的转移只跟当前状态有关而不需要关心当前状态是怎么一步步走过来的。dp[i][j]已经把“前i件物品在容量j下的最优价值”完全封装好了至于这个价值是通过怎样的物品组合得到的对后面的决策没有任何影响。正是因为这个性质我们才能放心地只保留这个状态值而不必记录完整的决策路径。很多同学刚开始学动态规划喜欢去“背”状态转移方程我倒不建议这么做。更好的办法是把dp表当作一张二维表格一行一行地填填到某个格子时问自己这个格子代表什么它的值可能从哪些格子来想清楚这两个问题每一种动态规划题目的转移方程其实都能自己推出来。3. 一张表走完全过程从4个物品的完整填表看动态规划的逻辑纸上得来终觉浅状态转移方程看着简单但真正要理解它我建议亲手填一次表。下面我用一个足够简单的实例把整张dp表从0开始一步步填出来。你跟着走一遍很多模糊的地方会自动清晰起来。假设背包容量W5有4件物品物品编号 1 2 3 4 重量w 2 1 3 2 价值v 12 10 20 15建立一个二维数组dp行代表物品编号从0到4列代表容量从0到5。第0行和第0列全部初始化为0这对应“没有物品可选”和“背包容量为0”两种情况。先填第1行也就是只考虑第1件物品重量2价值12。j0放不下dp[1][0]0。j1放不下dp[1][1]0。j2容量够了max(dp[0][2]0, dp[0][0]1212)取12。j3max(dp[0][3]0, dp[0][1]1212)取12。j4同理取12。j5同理取12。所以第1行是[0, 0, 12, 12, 12, 12]。接着填第2行相当于加入第2件物品重量1价值10。j0放不下0。j1max(dp[1][1]0, dp[1][0]1010)取10。j2max(dp[1][2]12, dp[1][1]1010)取12。这里有个关键点一定要用上一行的dp[1][1]而不是本行刚算出来的值同一件物品不能重复选。j3max(dp[1][3]12, dp[1][2]1022)取22。j4max(dp[1][4]12, dp[1][3]1022)取22。j5max(dp[1][5]12, dp[1][4]1022)取22。第2行是[0, 10, 12, 22, 22, 22]。填第3行加入第3件物品重量3价值20。j00。j1j w[3]放不下取dp[2][1]10。j2放不下取dp[2][2]12。j3max(dp[2][3]22, dp[2][0]2020)取22。注意这里选了第3件反而比不选少因为第2件物品太具性价比了。j4max(dp[2][4]22, dp[2][1]2030)取30。j5max(dp[2][5]22, dp[2][2]2032)取32。第3行是[0, 10, 12, 22, 30, 32]。填第4行加入第4件物品重量2价值15。j00。j1放不下取dp[3][1]10。j2max(dp[3][2]12, dp[3][0]1515)取15。j3max(dp[3][3]22, dp[3][1]1525)取25。j4max(dp[3][4]30, dp[3][2]1527)取30。j5max(dp[3][5]32, dp[3][3]1537)取37。第4行是[0, 10, 15, 25, 30, 37]。最终答案就是dp[4][5]37。我常用的填表模版可以写成这样n 4 W 5 weight [0, 2, 1, 3, 2] value [0, 12, 10, 20, 15] dp [[0] * (W 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, W 1): if j weight[i]: dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i]) else: dp[i][j] dp[i-1][j] print(dp[n][W])对于这个例子dp[4][5]37对应的最优组合是物品1、物品2和物品4总重量2125总价值12101537。还有一组物品3物品4总重量5价值35比37小所以不是最优。你自己在草稿纸上把这张表填一遍比我在这里讲一百句话都有用。4. 一维数组优化滚动数组为什么必须逆序更新二维dp表虽然直观但空间开销不小。当n和W都很大的时候一个(n1)行(W1)列的二维数组可能会占用大量内存在一些内存受限的环境里甚至会直接爆掉。而且仔细看转移方程就会发现dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]也就是说新的一行只跟紧挨着的上一行有关系跟更早的行没有任何关系。既然如此为什么要保留整张二维表呢完全可以只用一个一维数组在每一轮迭代中不断覆盖更新。这就是滚动数组的思想也是面试中进阶提问的常客。它的核心代码长这样dp [0] * (W 1) for i in range(1, n 1): for j in range(W, weight[i] - 1, -1): dp[j] max(dp[j], dp[j - weight[i]] value[i]) print(dp[W])用前面那个例子手动模拟一维数组的变化过程。初始dp全部为0处理第1件物品w2v12从j5往j2倒着更新dp[5]max(0, 012)12dp[4]max(0, 012)12dp[3]max(0, 012)12dp[2]max(0, 012)12更新后dp[0,0,12,12,12,12]。处理第2件物品w1v10从j5往j1倒着更新dp[5]max(12, dp[4]1022)22dp[4]max(12, dp[3]1022)22dp[3]max(12, dp[2]1022)22dp[2]max(12, dp[1]1010)12dp[1]max(0, dp[0]1010)10更新后dp[0,10,12,22,22,22]。处理第3件物品w3v20从j5往j3倒着更新dp[5]max(22, dp[2]2032)32dp[4]max(22, dp[1]2030)30dp[3]max(22, dp[0]2020)22更新后dp[0,10,12,22,30,32]。处理第4件物品w2v15从j5往j2倒着更新dp[5]max(32, dp[3]1537)37dp[4]max(30, dp[2]1527)30dp[3]max(22, dp[1]1525)25dp[2]max(12, dp[0]1515)15最终dp[0,10,15,25,30,37]答案dp[5]37。和二维表结果完全一致。很多初学者会问为什么一维数组要逆序遍历j而不能正着遍历这个问题是所有0-1背包讲解里的重头戏我用自己的话解释一遍。核心原因在于一维数组在更新dp[j]的时候必须确保用到的dp[j-weight[i]]还是上一轮也就是没放第i件物品之前的值。如果j从小到大正序遍历那么在算dp[j]之前dp[j-weight[i]]可能已经被本轮更新过了它代表的是“已经放入了第i件物品”的状态。这样一来同一个物品就可能被放进背包多次0-1背包就变成了完全背包事情就乱套了。可以这样直观理解正序遍历的时候dp[j-weight[i]]是“我刚刚用这个物品更新过”的值后面再拿这个值去更新dp[j]等于把这个物品又用了一次。而逆序遍历时j-weight[i]一定小于j在从大到小的遍历顺序下这个较小的下标还没被本轮更新过所以它仍然是上一轮的状态这和我们用二维表时dp[i-1][j-weight[i]]的逻辑完全对齐。我自己在刚开始写代码时也犯过这个错把内层循环写成从小到大结果算出来的答案明显偏大。后来用一个小例子去推才发现问题就出在“正序会导致重复选取”上。记住一句话0-1背包内层循环逆序完全背包内层循环正序这是两类问题代码上最直观的区别。空间复杂度从O(nW)降到了O(W)这是一个非常显著的优化。在大规模数据下这个优化往往是程序能不能跑起来的关键。5. 回溯求解具体方案从dp表里把“选了谁”挖出来有时候题目不只要最大价值还要你输出具体选了哪些物品。这时候光有一维滚动数组就不够了因为它压缩掉了一整维的信息仅仅保留每一轮更新后的最大值无法再还原决策路径。想要回溯必须使用二维dp表因为每一格的转移来源都记录在那个格子里。回溯的基本规则很简单从dp[n][W]开始倒着向前推。检查dp[i][j]和dp[i-1][j]是否相等。如果相等说明第i件物品没被选中因为不选它也能达到同样的价值那就继续看dp[i-1][j]。如果不相等说明第i件物品被选中了那就把第i件物品记下来然后背包容量减去w[i]即j变成j-w[i]继续看dp[i-1][j-w[i]]。为什么这个逻辑成立回看状态转移方程dp[i][j]的值要么来自dp[i-1][j]不选要么来自dp[i-1][j-w[i]]v[i]选。如果两个值恰好相等那说明选和不选效果一样题目如果有特殊要求比如输出字典序最小的方案需要额外处理这种相等的情况如果不相等根据最大值到底来自哪个方向就能判定第i件物品是否被选中。用前面那个实例来完整走一遍回溯过程起点dp[4][5]37dp[3][5]3237不等于32说明第4件物品被选中。记录物品4容量变为5-23。看dp[3][3]22dp[2][3]22两者相等说明第3件物品没被选中。继续往前。看dp[2][3]22dp[1][3]12不相等说明第2件物品被选中。记录物品2容量变为3-12。看dp[1][2]12dp[0][2]0不相等说明第1件物品被选中。记录物品1容量变为2-20。回溯结束得到选中的物品编号是1、2、4总价值12101537总重量正好5和前面填表的结论一致。如果题目要求输出选中的物品重量和价值回溯完再用编号去查原始数据就行。如果在回溯时遇到dp[i][j]等于dp[i-1][j]但是dp[i-1][j]也等于dp[i-1][j-w[i]]v[i]的情况那说明存在多个最优方案具体选哪个取决于题目要求。这时候只需要在相等时默认走“不选”分支就能得到一个合法方案。6. 初始化陷阱与常见变体不恰好装满与恰好装满0-1背包最经典的问法是“在不超过背包容量的前提下求最大价值”此时dp数组全部初始化成0没有任何问题因为什么都不装、价值为0本身就是一个合法方案。但题目稍微改一个字变成“恰好装满背包时能获得的最大价值”整个初始化逻辑就要换掉。这个“恰好装满”的坑在期末考试和面试里都特别常见。很多人把代码背熟了换个说法就不会了。恰好装满的含义是最终选出来的物品总重量必须严格等于背包容量W多余的容量哪怕还能塞进一件物品的一小部分也不算数。对应到状态定义dp[i][j]表示“从前i件物品中选若干件恰好装满容量为j的背包时能获得的最大价值”。如果根本不存在任何一种方案能恰好装出容量j这个状态就是无解的需要用一个特殊值来标记。一般用负无穷来表示“无解”编程时可以用一个足够小的负数比如负的10的9次方。初始化的规则是dp[0][0]0其余dp[0][j]全部设为负无穷。含义是只用0件物品时容量为0的背包恰好被装满价值是0容量大于0的背包没有任何物品可选永远不可能恰好装满所以是无解。转移方程本身不用变但如果从无解状态转移过去得到的结果仍然是负无穷这样最终答案dp[n][W]如果不是负无穷就说明存在恰好装满的方案否则说明无解。放一个具体的例子说明假设背包容量W4有3件物品物品1重量2价值3 物品2重量2价值4 物品3重量3价值5不超过容量的普通0-1背包最优值是7物品12总重4或5物品3重量3。恰好装满容量4时最优值仍然是7因为物品12的总重正好是4。如果这时加入一件重量1、价值2的物品情况就不一样了普通背包可以考虑物品124重量5超了物品12总重4价值7或者物品34总重4价值7。恰好装满容量4的最优解也是7。但如果物品里没有总重正好等于4的组合比如物品只有重量3、价值5这一件那么普通背包的最优值是5容量4装了重量3而恰好装满时答案是无解因为没有任何组合能正好凑出重量4。再往深走一步还有一类“求最小价值/最小成本”的背包变形。比如把价值v[i]换成“成本”问恰好装满容量为W的最小总成本。这时候转移方程要改成min初始化也变成dp[0][0]0其余dp[0][j]正无穷理由和“最大价值恰好装满”对称只不过无解标记换成正无穷。关于“恰好装满”还有一个很经典的推论就是普通背包中如果所有物品重量都大于W答案是0什么都不装这是合法方案但在恰好装满的设定下答案是“无解”或者“不存在合法方案”这两个答案的含义完全不同。审题不清就把这两种情况搞混是这类题丢分的最常见原因。7. 从考试到实战易错点、Python实现细节与后续迁移0-1背包的动态规划解法讲到这里核心内容已经全部覆盖了。但这个题目在考试和面试里出现的频率实在太高我把平时实操中容易踩的坑和可以迁移的思维再集中整理一遍。第一个高频易错点是下标问题。很多教材和博文的代码里物品编号都是从1开始的weight[0]和value[0]通常浪费不用这样dp[i]对应第i件物品代码读起来很顺。也有一些代码从0开始下标那转移方程就要变成dp[i][j]和dp[i-1][j-w[i]]需要把weight[i-1]对应到第i件物品。我个人强烈建议实现时统一用从1开始的下标能省不少脑力也不容易写错边界。第二个易错点是Python里range的边界。逆序更新的写法是for j in range(W, weight[i] - 1, -1): dp[j] max(dp[j], dp[j - weight[i]] value[i])这里的range()是左闭右开区间所以要写成weight[i]-1才能保证j能取到weight[i]这个值。我见过不少同学在这里写错成weight[i]导致容量刚好等于物品重量的那一格永远没被更新答案偏小。这个小细节遇到一次就会记住一辈子。第三个易错点是输入数据的处理。如果从文件或标准输入读数据题目通常第一行给n和W接下来n行每行两个整数代表重量和价值。如果物品顺序跟题目描述不一致记得先按题目要求排好序再进入dp流程。特别是当题目有特殊输出要求比如输出字典序最小的方案时排序必须在dp之前完成否则回溯出来的方案可能出现偏差。第四个易错点是“贪心方案”的干扰。有的同学看到重量小、价值高的物品很容易想到先按单位重量价值排序然后贪心选但0-1背包是不能用贪心的。为什么因为物品不可分割贪心只考虑局部最优不一定能得到全局最优。举例W10物品A重量6价值12物品B重量5价值10物品C重量5价值10。按单位价值A最优先选A剩下4装不下别的总价值12实际上选B和C总价值20是更好的方案。这个例子我每届都会给学生讲但每次还是有同学在合卷时犯同样的错误。从0-1背包往外延伸它其实是整个背包问题家族的基础也是动态规划思想的经典范本。搞懂了0-1背包后面遇到完全背包、多重背包、分组背包思路是相通的。完全背包里每件物品可以选无限次代码上只需要把内层循环改成正序其他都不用动。理解这个变化的钥匙就在于一维滚动数组的更新顺序这也是我把“逆序更新”单独拿出来讲一整节的原因。多重背包是每件物品有有限个数量常见做法是二进制拆分把若干个相同物品打包成不同的物品组然后转换成0-1背包来解。分组背包把物品分到若干组每组最多选一件状态转移时要加一层枚举组内物品的循环。背包问题还能和很多其他考点结合。求方案数时转移方程里的max改成累加初始化时dp[0]1求最小价值时max改成min初始化用正无穷求具体方案时用二维表回溯求字典序最小方案时物品要先排序回溯时优先选择编号小的物品。我在实际做算法题和带新人的时候最大的体会是不要试图记住每一种背包问题的代码模板只要抓住“状态定义”“转移方程”“初始化”“遍历顺序”这四个分析维度遇到问题先想清楚这四件事大部分题目都能自己推出来。0-1背包之所以被当作经典中的经典就是因为它把这四个维度的每一种变化都体现得很充分。如果你正在准备《算法设计与分析》的期末考试或者找实习的算法面试我建议你拿一张A4纸把今天这个4物品5容量的例子重新手算一遍从二维表到一维滚动数组再到回溯方案每一步都不要跳过。这种“手算一遍胜过看十遍”的事情可能是我在算法学习上分享的最有价值的经验了。等你能不假思索地把这些步骤写出来你的动态规划基础就已经非常扎实了。