0-1背包问题可以说是《算法设计与分析》这门课里最有代表性的动态规划经典题也是算法笔试、期末考和面试环节的老熟人。我第一次在课堂上接触它的时候心里想的是这不就是“每样东西选或者不选”嘛用暴力枚举把所有组合列出来不就行了结果被2的n次方这个指数爆炸狠狠教育了一顿。后来老老实实把动态规划的表格一行一行推完才明白这题真正想教会你的事情不是“怎么枚举得更快”而是怎么把重复计算缓存下来用已知答案推导未知答案这才是动态规划的核心思维。这篇文章我会从问题建模、状态定义、转移方程推导、手工填表、Python代码实现、空间优化到回溯构造解把0-1背包的动态规划解法完整拆开揉碎讲清楚。你只要跟着文章自己动手推一遍表就能彻底搞懂为什么dp数组要这么设计、为什么一维数组必须倒序遍历、为什么贪心在这里不靠谱。无论你是正在复习期末的在校学生还是准备算法面试的开发者这篇文章应该都能让你少走不少弯路。1. 0-1背包问题到底在求解什么1.1 问题定义与名词解释先说人话版本假设你有一个承重能力为W的背包地上有n个物品每个物品有自己的重量w_i和价值v_i。背包要么把整个物品装进去要么完全不装不能像切西瓜一样只带走半个。目标非常直接在不超过背包承重的前提下让装进背包的物品总价值最大。“0-1”这个名称就来自于每个物品只有两种状态0代表不装1代表装。这也是它和完全背包、多重背包最本质的区别。完全背包里每个物品可以无限次取用多重背包里每个物品有一定数量限制而0-1背包每个物品只有一个爱要不要干脆利落。这里有几个默认前提需要先明确重量和价值都是正整数有些题目会给0甚至负数那属于变体背包容量W是整数每个物品之间相互独立没有“选了A就不能选B”这种依赖关系。多数教材和课程里讨论的都是这个最朴素的版本。很多初学者第一反应是“把所有组合列出来比一比”这就是暴力枚举。n个物品的每个组合都是“选/不选”二选一一共2^n种方案。n20时就已经有一百多万种n50时直接是个天文数字更不用说笔试里常见的n1000。所以这题的核心不是“会不会枚举”而是“怎么在多项式时间内找到答案”。1.2 为什么贪心在最优化问题上翻车既然不能暴力枚举很多人又想到贪心先把所有物品按单位重量价值v_i / w_i排个序优先装性价比高的。这个思路听起来非常有道理但一旦遇到反例就崩了。比如背包容量10三个物品分别是物品A重量6价值12性价比2物品B重量5价值10性价比2物品C重量5价值10性价比2按照性价比排序A、B、C的性价比一样贪心策略可能先装A剩下4容量装不下任何东西总价值12。可最优解明明是装B和C重量刚好10总价值20。差距接近一倍直接宣告贪心失效。为什么贪心会翻车因为物品不可分割性价比高的物品可能会把背包的空间占掉一大块反而导致剩余空间凑不满。0-1背包里“容量”和“价值”之间存在一种微妙的权衡局部最优的选择组合在一起不一定能构成全局最优。这个反例值得反复琢磨面试时如果被问到“为什么0-1背包不能用贪心”直接抛这个例子就能说明白。2. 动态规划解法从状态定义到转移方程2.1 状态定义dp[i][j]到底是什么意思动态规划的核心是先设计一个“状态”让大问题可以被拆成小问题并且小问题的答案可以被反复复用。在0-1背包里最经典的定义是dp[i][j]表示“在前i个物品中挑选放入容量为j的背包能获得的最大总价值”。注意这里面有两个维度i表示只考虑前i个物品不关心后面的物品j表示当前背包容量是j。为什么必须两个维度因为单看“前i个物品”不够容量不同能装的组合完全不同。两个维度合起来就能覆盖所有子问题。初始状况也很好理解dp[0][j] 0前面0个物品不管背包容量多大能装的都是0。dp[i][0] 0背包容量是0不管前面多少物品什么都装不下。这两个边界条件就是动态规划的地基后面所有递推都从这一行一列开始。有的教材会把下标从1开始物品编号从1到ndp数组开成(n1)×(W1)目的就是为了让i0这一行表示“没有物品”的初始状态。做算法题时用Python的0索引也没问题关键是转移方程里别把物品下标搞错这个坑后面会专门讲。2.2 转移方程是怎么一步步推出来的现在到了最核心的一步已知dp[0..i-1][0..W]所有值怎么求dp[i][j]面对第i个物品只有两个选择不拿它那么问题退化成“在前i-1个物品里选容量还是j”也就是dp[i-1][j]。拿它首先当前容量j必须大于等于w_i其次拿了这个物品后剩余容量只有j-w_i前面的物品也只能在剩余容量里选所以是dp[i-1][j-w_i] v_i。两种方案里取更大的那个就是dp[i][j]的最优值。写成状态转移方程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[i][j]的定义是在前i个物品里选一组总重量不超过j总价值最大。那么最优解里第i个物品有且只有两种状态它要么在最优解里要么不在。如果在把它拿出来剩下的就是在容量j-w_i中选前i-1个物品的最优解如果不在剩下的就是在容量j中选前i-1个物品的最优解。只要这两种情况都算到就一定能覆盖最优解。可以把第i个物品想象成来面试的最后一位候选人要么录用他剩下的团队在减掉他占据的“预算空间”后选最优要么不录用他原团队直接是最优。这两个方案比大小就是录用决策。这个“做出决策后把问题缩小”的思路几乎贯穿所有动态规划问题后面学最长公共子序列、编辑距离的时候你会发现套路都是相通的。3. 手工推演一张表看懂整个计算过程3.1 准备一个具体的例子光看公式容易晕我带你把整个填表过程手推一遍。用下面这个例子背包容量W 8物品1重量2价值3物品2重量3价值4物品3重量4价值5物品4重量5价值6这个例子的数据不大不小刚好能看出组合装包和最优切换的过程。你拿张纸跟着画一个(n1)×(W1)的表格行代表“前i个物品”列代表“背包容量j从0到8”。先把第0行和第0列全部填0这是初始状态。3.2 逐行填充DP表第一行是物品1重量2价值3。容量0和1都小于2装不下填0。容量2开始j大于等于w_i成立不拿的方案是dp[0][2]0拿的方案是dp[0][0]33取3。容量3到8不拿的方案dp[0][j]全是0拿的方案dp[0][j-2]3全是3所以这一行从容量2开始就全是3。这一行很直观只有一件物品容量够了就是它。第二行是物品2重量3价值4。容量0到2装不下物品2直接复制上一行0、0、3。容量3不带是3带是4取4。容量4不带是3带是dp[1][1]4044取4。容量5开始出现质变不带是3带是dp[1][2]4347取7。这里第一次出现了“组合”的效果物品1和物品2一起装总重量5总价值7。容量6、7、8带上的方案都取7因为无论剩余多少前两件一起装已经是最优。第三行是物品3重量4价值5。容量0到3小于4直接复制上一行。容量4不带是4带是dp[2][0]5055取5。容量5不带是7带是dp[2][1]5055取7。容量6不带是7带是dp[2][2]5358取8。容量7不带是7带是dp[2][3]5459取9。容量8不带是7带是dp[2][4]5459取9。这一行能看出来物品3在容量比较大时很有竞争力但小容量下反而带不动。第四行是物品4重量5价值6。容量0到4都放不下直接复制上一行。容量5不带是7带是dp[3][0]6066取7。容量6不带是8带是6取8。容量7不带是9带是dp[3][2]6369取9。容量8不带是9带是dp[3][3]64610取10。到这里答案已经浮现出来了。完整表格如下物品\容量012345678无物品000000000物品1003333333物品2003447777物品3003457899物品400345789103.3 从表格里读出答案最终答案就是dp[4][8] 10表示在考虑全部4个物品、背包容量为8的情况下最大总价值是10。注意这个10只是最大价值光看表格还看不出选了哪几个物品。想知道具体方案需要从表格右下角倒推回去这就是后面要讲的回溯。这里有个细节值得多说一句每一行的数据都不是凭空来的它代表“决策到某个物品时的所有可能性”而不是“最终选了哪个”。所以你填表的时候没必要焦虑“我是不是漏了某种组合”因为转移方程已经把两种可能都覆盖了。你填的每个格子其实都是在回答一个问题前i件物品容量j最多能装多少价值。4. 代码实现Python版本从二维到一维4.1 二维DP的Python实现先写一个最标准的二维版本思路和刚刚手工推演完全一致方便你对照理解def knapsack_2d(weights, values, capacity): n len(weights) # 行前 i 个物品列容量 j # 多加一行一列是为了让下标从 1 开始方便表示“前 0 个物品” dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w_i weights[i - 1] # Python 从 0 开始第 i 个物品对应下标 i-1 v_i values[i - 1] for j in range(capacity 1): 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] return dp[n][capacity]这个版本的优点是直观跟状态转移方程一一对应也方便后面回溯。缺点是空间复杂度O(nW)当n和W都很大的时候内存会有点吃紧。测试一下weights [2, 3, 4, 5] values [3, 4, 5, 6] capacity 8 print(knapsack_2d(weights, values, capacity)) # 输出 104.2 一维滚动数组优化接下来是重点中的重点。观察转移方程可以发现dp[i][j]只依赖dp[i-1][...]也就是说每一行只跟上一行有关跟更早的行没有任何关系。既然如此我们没必要把整个二维表都存下来只需要维护一行数据每次都在这一行上做更新这就是滚动数组。def knapsack_1d(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(1, n 1): w_i weights[i - 1] v_i values[i - 1] # 关键从后往前遍历避免重复使用同一个物品 for j in range(capacity, w_i - 1, -1): dp[j] max(dp[j], dp[j - w_i] v_i) return dp[capacity]这段代码里最容易被忽略的就是内层循环的range(capacity, w_i - 1, -1)必须从大到小不能反过来。我来解释一下原因。如果内层循环正序遍历比如j从小往大走当更新dp[j]的时候dp[j-w_i]可能已经被本轮循环更新过了。也就是说第i个物品可能被“重复选中”这就不再是0-1背包而变成完全背包的语义了。举刚才的例子就明白了容量8正序遍历第一件物品重量2价值3dp[2] max(dp[2], dp[0]3) 3dp[4] max(dp[4], dp[2]3) 6但dp[2]已经被更新成3了相当于又选了一次物品1dp[6] max(dp[6], dp[4]3) 9又选一次dp[8] max(dp[8], dp[6]3) 12无限循环肉眼可见这不是“一个物品只选一次”的逻辑。所以0-1背包的一维写法内层循环必须倒序这个坑可以说是背包问题的祖传考点笔试面试都爱问。最后再提醒一个细节如果题目要求“恰好装满背包”初始化应该是dp[0]0dp[1..capacity]负无穷如果只是“不超过容量”全部初始化为0就行。两种题意的代码不同先想清楚题目在问什么再动手。4.3 回溯构造最优解很多场景下不仅要最大价值还要知道“选了哪些物品”。这时候就必须用二维表因为回推时需要每一行的信息。回溯的思路是从表底往上推从dp[n][W]开始如果dp[i][j]等于dp[i-1][j]说明第i个物品没有被选因为选它并没有带来更高价值如果dp[i][j]大于dp[i-1][j]说明第i个物品被选中于是把j减去w_i再继续看前i-1个物品。重复直到i0。写成代码def knapsack_with_solution(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w_i, v_i weights[i - 1], values[i - 1] for j in range(capacity 1): 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] # 回溯 selected [] j capacity for i in range(n, 0, -1): if dp[i][j] ! dp[i - 1][j]: selected.append(i) # 物品编号从 1 开始 j - weights[i - 1] return dp[n][capacity], selected[::-1]在这个例子里会输出print(knapsack_with_solution([2, 3, 4, 5], [3, 4, 5, 6], 8)) # (10, [2, 4])也就是选了第2个和第4个物品重量358价值4610正好装满和手工推演完全一致。这里必须强调一个使用限制如果你用了前面的一维dp回溯是做不到的因为一维数组覆盖了历史信息你根本不知道dp[i-1][j]和dp[i][j]是怎么演变过来的。所以凡是题目要求输出具体方案就老老实实开二维表别贪省空间省空间可以理解但省到连方案都丢了就得不偿失。5. 常见问题与排查技巧实录5.1 初始化和边界条件这些坑第一个大坑是Python里二维数组的初始化。很多人会写dp [[0] * (capacity 1)] * (n 1)这一下就坏事了。*复制的是列表的引用不是内容。也就是说dp里的每一行实际上指向同一个列表对象改一个等于改全部。正确写法是[[0] * (capacity 1) for _ in range(n 1)]每一行都是独立的新列表。第二个坑是忘记容量为0的那一列。dp[i][0]应该始终为0因为容量为0什么都装不下。如果你把dp的大小开成capacity而不是capacity 1后面取dp[j-w_i]时很容易越界。第三个坑是物品下标的偏移。算法里习惯1-indexPython里是0-indexweights[i-1]才是第i个物品。写转移方程的时候用它写回溯的时候也要用它这个错位我见过很多次新手尤其容易踩。5.2 遍历顺序为什么不能乱遍历顺序这个问题几乎每次笔试面试都会被问到也是区分“真会”和“背模板”的关键。二维dp的正序或倒序遍历都行因为dp[i][j]读取的是dp[i-1][...]的旧值只要保证在更新dp[i][j]时上一行还没被覆盖就可以。但一维滚动数组不一样它保存的是“上一行”的值如果正序遍历还没用完旧值就已经被新值覆盖了。而完全背包问题恰恰相反它需要每个物品可以被反复选正序遍历反而才是正确的。所以判断遍历顺序前先问自己一个问题这题每个物品是只能选一次还是可以选无数次想清楚了再写循环比硬背代码靠谱得多。5.3 典型错误对照表错误现象可能原因解决方法结果比正确答案大很多一维数组正序遍历物品被重复选内层循环改成从capacity到w_i倒序结果少算了一些组合背包容量数组开小了最后一列没算dp长度设为capacity 1循环到capacity输出的物品方案不满足重量约束回溯时没有把j减去weight[i]确认回溯循环里同步执行j - weights[i-1]修改一个单元格整列都变二维数组使用了乘法复制引用用列表推导式创建二维数组结果一直等于价格最高的单件物品状态转移方程写成了只和当前物品比较检查dp[i][j] max(dp[i-1][j], dp[i-1][j-w_i] v_i)输入物品为空时程序报错忘记处理n0的边界开头加if not weights: return 06. 复杂度分析与应用场景扩展6.1 时间与空间复杂度二维版本时间复杂度O(nW)空间复杂度O(nW)一维版本时间不变空间降为O(W)。这里有个有趣的权衡n是物品个数W是背包容量。当W比较小时DP非常给力可是当W特别大比如10^9dp表根本开不出来这时候只能换思路比如按价值而不是重量来做或者用分支限界、meet in the middle这类技巧。这也是为什么背包问题常被用来考察“算法设计”而不是单纯的“实现能力”——它在教你在时间和空间之间做取舍。很多算法设计与分析期末编程题就是让考生在二维模板和一维优化之间做选择题目通常会明确给出背包容量范围。看到W只有几千时两版都能过看到W达10^6或10^7时就要考虑一维加剪枝了。6.2 从0-1背包延伸到哪些实际问题0-1背包看着简单它其实是很多真实问题的最小模型。常见的方向包括车辆动态规划问题。货车装载、多车调度里的载重分配本质就是“每个包裹要不要上这辆车”的01决策再叠加路径和时间的约束。资源分配问题。预算有限每个项目要投入固定成本并产生收益选哪些项目是典型的0-1背包。等和子集分割、最小差值分割。判断能不能把数组分成两个和相等的子集转换成背包容量为sum/2的可达性问题。完全背包与多重背包。完全背包的物品可以无限取内层循环改成正序多重背包有数量限制可以用二进制拆分转换成0-1背包。树上依赖背包。物品之间有依赖关系比如必须先选A才能选B就得用树形DP结合背包的思路。很多人学到背包九讲系列会觉得脑子装不下我的建议是先吃透0-1背包这一讲把状态定义、方程推导和滚动数组优化搞明白后面全是它的变体。你把这个模板理解透了面对一堆变体时会发现顺着思路走原来都是一个套路。最后说一点期末和面试的考试心得。这类题最常见的考法是判断能不能用贪心手推状态的转移过程给出dp表写出状态转移方程并说明时间复杂度在给定代码里补全循环的遍历方向让你解释为什么一维数组要倒序。这五个点如果你都能自己讲清楚那0-1背包这道题就算真正拿下了。我自己带过的学生里凡是能把表格亲手完整推一遍再写代码的人后续遇到完全背包、多重背包、分组背包这些升级版上手都特别快因为最底层的那根弦已经通了。
0-1背包问题可以说是《算法设计与分析》这门课里最有代表性的动态规划经典题也是算法笔试、期末考和面试环节的老熟人。我第一次在课堂上接触它的时候心里想的是这不就是“每样东西选或者不选”嘛用暴力枚举把所有组合列出来不就行了结果被2的n次方这个指数爆炸狠狠教育了一顿。后来老老实实把动态规划的表格一行一行推完才明白这题真正想教会你的事情不是“怎么枚举得更快”而是怎么把重复计算缓存下来用已知答案推导未知答案这才是动态规划的核心思维。这篇文章我会从问题建模、状态定义、转移方程推导、手工填表、Python代码实现、空间优化到回溯构造解把0-1背包的动态规划解法完整拆开揉碎讲清楚。你只要跟着文章自己动手推一遍表就能彻底搞懂为什么dp数组要这么设计、为什么一维数组必须倒序遍历、为什么贪心在这里不靠谱。无论你是正在复习期末的在校学生还是准备算法面试的开发者这篇文章应该都能让你少走不少弯路。1. 0-1背包问题到底在求解什么1.1 问题定义与名词解释先说人话版本假设你有一个承重能力为W的背包地上有n个物品每个物品有自己的重量w_i和价值v_i。背包要么把整个物品装进去要么完全不装不能像切西瓜一样只带走半个。目标非常直接在不超过背包承重的前提下让装进背包的物品总价值最大。“0-1”这个名称就来自于每个物品只有两种状态0代表不装1代表装。这也是它和完全背包、多重背包最本质的区别。完全背包里每个物品可以无限次取用多重背包里每个物品有一定数量限制而0-1背包每个物品只有一个爱要不要干脆利落。这里有几个默认前提需要先明确重量和价值都是正整数有些题目会给0甚至负数那属于变体背包容量W是整数每个物品之间相互独立没有“选了A就不能选B”这种依赖关系。多数教材和课程里讨论的都是这个最朴素的版本。很多初学者第一反应是“把所有组合列出来比一比”这就是暴力枚举。n个物品的每个组合都是“选/不选”二选一一共2^n种方案。n20时就已经有一百多万种n50时直接是个天文数字更不用说笔试里常见的n1000。所以这题的核心不是“会不会枚举”而是“怎么在多项式时间内找到答案”。1.2 为什么贪心在最优化问题上翻车既然不能暴力枚举很多人又想到贪心先把所有物品按单位重量价值v_i / w_i排个序优先装性价比高的。这个思路听起来非常有道理但一旦遇到反例就崩了。比如背包容量10三个物品分别是物品A重量6价值12性价比2物品B重量5价值10性价比2物品C重量5价值10性价比2按照性价比排序A、B、C的性价比一样贪心策略可能先装A剩下4容量装不下任何东西总价值12。可最优解明明是装B和C重量刚好10总价值20。差距接近一倍直接宣告贪心失效。为什么贪心会翻车因为物品不可分割性价比高的物品可能会把背包的空间占掉一大块反而导致剩余空间凑不满。0-1背包里“容量”和“价值”之间存在一种微妙的权衡局部最优的选择组合在一起不一定能构成全局最优。这个反例值得反复琢磨面试时如果被问到“为什么0-1背包不能用贪心”直接抛这个例子就能说明白。2. 动态规划解法从状态定义到转移方程2.1 状态定义dp[i][j]到底是什么意思动态规划的核心是先设计一个“状态”让大问题可以被拆成小问题并且小问题的答案可以被反复复用。在0-1背包里最经典的定义是dp[i][j]表示“在前i个物品中挑选放入容量为j的背包能获得的最大总价值”。注意这里面有两个维度i表示只考虑前i个物品不关心后面的物品j表示当前背包容量是j。为什么必须两个维度因为单看“前i个物品”不够容量不同能装的组合完全不同。两个维度合起来就能覆盖所有子问题。初始状况也很好理解dp[0][j] 0前面0个物品不管背包容量多大能装的都是0。dp[i][0] 0背包容量是0不管前面多少物品什么都装不下。这两个边界条件就是动态规划的地基后面所有递推都从这一行一列开始。有的教材会把下标从1开始物品编号从1到ndp数组开成(n1)×(W1)目的就是为了让i0这一行表示“没有物品”的初始状态。做算法题时用Python的0索引也没问题关键是转移方程里别把物品下标搞错这个坑后面会专门讲。2.2 转移方程是怎么一步步推出来的现在到了最核心的一步已知dp[0..i-1][0..W]所有值怎么求dp[i][j]面对第i个物品只有两个选择不拿它那么问题退化成“在前i-1个物品里选容量还是j”也就是dp[i-1][j]。拿它首先当前容量j必须大于等于w_i其次拿了这个物品后剩余容量只有j-w_i前面的物品也只能在剩余容量里选所以是dp[i-1][j-w_i] v_i。两种方案里取更大的那个就是dp[i][j]的最优值。写成状态转移方程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[i][j]的定义是在前i个物品里选一组总重量不超过j总价值最大。那么最优解里第i个物品有且只有两种状态它要么在最优解里要么不在。如果在把它拿出来剩下的就是在容量j-w_i中选前i-1个物品的最优解如果不在剩下的就是在容量j中选前i-1个物品的最优解。只要这两种情况都算到就一定能覆盖最优解。可以把第i个物品想象成来面试的最后一位候选人要么录用他剩下的团队在减掉他占据的“预算空间”后选最优要么不录用他原团队直接是最优。这两个方案比大小就是录用决策。这个“做出决策后把问题缩小”的思路几乎贯穿所有动态规划问题后面学最长公共子序列、编辑距离的时候你会发现套路都是相通的。3. 手工推演一张表看懂整个计算过程3.1 准备一个具体的例子光看公式容易晕我带你把整个填表过程手推一遍。用下面这个例子背包容量W 8物品1重量2价值3物品2重量3价值4物品3重量4价值5物品4重量5价值6这个例子的数据不大不小刚好能看出组合装包和最优切换的过程。你拿张纸跟着画一个(n1)×(W1)的表格行代表“前i个物品”列代表“背包容量j从0到8”。先把第0行和第0列全部填0这是初始状态。3.2 逐行填充DP表第一行是物品1重量2价值3。容量0和1都小于2装不下填0。容量2开始j大于等于w_i成立不拿的方案是dp[0][2]0拿的方案是dp[0][0]33取3。容量3到8不拿的方案dp[0][j]全是0拿的方案dp[0][j-2]3全是3所以这一行从容量2开始就全是3。这一行很直观只有一件物品容量够了就是它。第二行是物品2重量3价值4。容量0到2装不下物品2直接复制上一行0、0、3。容量3不带是3带是4取4。容量4不带是3带是dp[1][1]4044取4。容量5开始出现质变不带是3带是dp[1][2]4347取7。这里第一次出现了“组合”的效果物品1和物品2一起装总重量5总价值7。容量6、7、8带上的方案都取7因为无论剩余多少前两件一起装已经是最优。第三行是物品3重量4价值5。容量0到3小于4直接复制上一行。容量4不带是4带是dp[2][0]5055取5。容量5不带是7带是dp[2][1]5055取7。容量6不带是7带是dp[2][2]5358取8。容量7不带是7带是dp[2][3]5459取9。容量8不带是7带是dp[2][4]5459取9。这一行能看出来物品3在容量比较大时很有竞争力但小容量下反而带不动。第四行是物品4重量5价值6。容量0到4都放不下直接复制上一行。容量5不带是7带是dp[3][0]6066取7。容量6不带是8带是6取8。容量7不带是9带是dp[3][2]6369取9。容量8不带是9带是dp[3][3]64610取10。到这里答案已经浮现出来了。完整表格如下物品\容量012345678无物品000000000物品1003333333物品2003447777物品3003457899物品400345789103.3 从表格里读出答案最终答案就是dp[4][8] 10表示在考虑全部4个物品、背包容量为8的情况下最大总价值是10。注意这个10只是最大价值光看表格还看不出选了哪几个物品。想知道具体方案需要从表格右下角倒推回去这就是后面要讲的回溯。这里有个细节值得多说一句每一行的数据都不是凭空来的它代表“决策到某个物品时的所有可能性”而不是“最终选了哪个”。所以你填表的时候没必要焦虑“我是不是漏了某种组合”因为转移方程已经把两种可能都覆盖了。你填的每个格子其实都是在回答一个问题前i件物品容量j最多能装多少价值。4. 代码实现Python版本从二维到一维4.1 二维DP的Python实现先写一个最标准的二维版本思路和刚刚手工推演完全一致方便你对照理解def knapsack_2d(weights, values, capacity): n len(weights) # 行前 i 个物品列容量 j # 多加一行一列是为了让下标从 1 开始方便表示“前 0 个物品” dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w_i weights[i - 1] # Python 从 0 开始第 i 个物品对应下标 i-1 v_i values[i - 1] for j in range(capacity 1): 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] return dp[n][capacity]这个版本的优点是直观跟状态转移方程一一对应也方便后面回溯。缺点是空间复杂度O(nW)当n和W都很大的时候内存会有点吃紧。测试一下weights [2, 3, 4, 5] values [3, 4, 5, 6] capacity 8 print(knapsack_2d(weights, values, capacity)) # 输出 104.2 一维滚动数组优化接下来是重点中的重点。观察转移方程可以发现dp[i][j]只依赖dp[i-1][...]也就是说每一行只跟上一行有关跟更早的行没有任何关系。既然如此我们没必要把整个二维表都存下来只需要维护一行数据每次都在这一行上做更新这就是滚动数组。def knapsack_1d(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(1, n 1): w_i weights[i - 1] v_i values[i - 1] # 关键从后往前遍历避免重复使用同一个物品 for j in range(capacity, w_i - 1, -1): dp[j] max(dp[j], dp[j - w_i] v_i) return dp[capacity]这段代码里最容易被忽略的就是内层循环的range(capacity, w_i - 1, -1)必须从大到小不能反过来。我来解释一下原因。如果内层循环正序遍历比如j从小往大走当更新dp[j]的时候dp[j-w_i]可能已经被本轮循环更新过了。也就是说第i个物品可能被“重复选中”这就不再是0-1背包而变成完全背包的语义了。举刚才的例子就明白了容量8正序遍历第一件物品重量2价值3dp[2] max(dp[2], dp[0]3) 3dp[4] max(dp[4], dp[2]3) 6但dp[2]已经被更新成3了相当于又选了一次物品1dp[6] max(dp[6], dp[4]3) 9又选一次dp[8] max(dp[8], dp[6]3) 12无限循环肉眼可见这不是“一个物品只选一次”的逻辑。所以0-1背包的一维写法内层循环必须倒序这个坑可以说是背包问题的祖传考点笔试面试都爱问。最后再提醒一个细节如果题目要求“恰好装满背包”初始化应该是dp[0]0dp[1..capacity]负无穷如果只是“不超过容量”全部初始化为0就行。两种题意的代码不同先想清楚题目在问什么再动手。4.3 回溯构造最优解很多场景下不仅要最大价值还要知道“选了哪些物品”。这时候就必须用二维表因为回推时需要每一行的信息。回溯的思路是从表底往上推从dp[n][W]开始如果dp[i][j]等于dp[i-1][j]说明第i个物品没有被选因为选它并没有带来更高价值如果dp[i][j]大于dp[i-1][j]说明第i个物品被选中于是把j减去w_i再继续看前i-1个物品。重复直到i0。写成代码def knapsack_with_solution(weights, values, capacity): n len(weights) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w_i, v_i weights[i - 1], values[i - 1] for j in range(capacity 1): 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] # 回溯 selected [] j capacity for i in range(n, 0, -1): if dp[i][j] ! dp[i - 1][j]: selected.append(i) # 物品编号从 1 开始 j - weights[i - 1] return dp[n][capacity], selected[::-1]在这个例子里会输出print(knapsack_with_solution([2, 3, 4, 5], [3, 4, 5, 6], 8)) # (10, [2, 4])也就是选了第2个和第4个物品重量358价值4610正好装满和手工推演完全一致。这里必须强调一个使用限制如果你用了前面的一维dp回溯是做不到的因为一维数组覆盖了历史信息你根本不知道dp[i-1][j]和dp[i][j]是怎么演变过来的。所以凡是题目要求输出具体方案就老老实实开二维表别贪省空间省空间可以理解但省到连方案都丢了就得不偿失。5. 常见问题与排查技巧实录5.1 初始化和边界条件这些坑第一个大坑是Python里二维数组的初始化。很多人会写dp [[0] * (capacity 1)] * (n 1)这一下就坏事了。*复制的是列表的引用不是内容。也就是说dp里的每一行实际上指向同一个列表对象改一个等于改全部。正确写法是[[0] * (capacity 1) for _ in range(n 1)]每一行都是独立的新列表。第二个坑是忘记容量为0的那一列。dp[i][0]应该始终为0因为容量为0什么都装不下。如果你把dp的大小开成capacity而不是capacity 1后面取dp[j-w_i]时很容易越界。第三个坑是物品下标的偏移。算法里习惯1-indexPython里是0-indexweights[i-1]才是第i个物品。写转移方程的时候用它写回溯的时候也要用它这个错位我见过很多次新手尤其容易踩。5.2 遍历顺序为什么不能乱遍历顺序这个问题几乎每次笔试面试都会被问到也是区分“真会”和“背模板”的关键。二维dp的正序或倒序遍历都行因为dp[i][j]读取的是dp[i-1][...]的旧值只要保证在更新dp[i][j]时上一行还没被覆盖就可以。但一维滚动数组不一样它保存的是“上一行”的值如果正序遍历还没用完旧值就已经被新值覆盖了。而完全背包问题恰恰相反它需要每个物品可以被反复选正序遍历反而才是正确的。所以判断遍历顺序前先问自己一个问题这题每个物品是只能选一次还是可以选无数次想清楚了再写循环比硬背代码靠谱得多。5.3 典型错误对照表错误现象可能原因解决方法结果比正确答案大很多一维数组正序遍历物品被重复选内层循环改成从capacity到w_i倒序结果少算了一些组合背包容量数组开小了最后一列没算dp长度设为capacity 1循环到capacity输出的物品方案不满足重量约束回溯时没有把j减去weight[i]确认回溯循环里同步执行j - weights[i-1]修改一个单元格整列都变二维数组使用了乘法复制引用用列表推导式创建二维数组结果一直等于价格最高的单件物品状态转移方程写成了只和当前物品比较检查dp[i][j] max(dp[i-1][j], dp[i-1][j-w_i] v_i)输入物品为空时程序报错忘记处理n0的边界开头加if not weights: return 06. 复杂度分析与应用场景扩展6.1 时间与空间复杂度二维版本时间复杂度O(nW)空间复杂度O(nW)一维版本时间不变空间降为O(W)。这里有个有趣的权衡n是物品个数W是背包容量。当W比较小时DP非常给力可是当W特别大比如10^9dp表根本开不出来这时候只能换思路比如按价值而不是重量来做或者用分支限界、meet in the middle这类技巧。这也是为什么背包问题常被用来考察“算法设计”而不是单纯的“实现能力”——它在教你在时间和空间之间做取舍。很多算法设计与分析期末编程题就是让考生在二维模板和一维优化之间做选择题目通常会明确给出背包容量范围。看到W只有几千时两版都能过看到W达10^6或10^7时就要考虑一维加剪枝了。6.2 从0-1背包延伸到哪些实际问题0-1背包看着简单它其实是很多真实问题的最小模型。常见的方向包括车辆动态规划问题。货车装载、多车调度里的载重分配本质就是“每个包裹要不要上这辆车”的01决策再叠加路径和时间的约束。资源分配问题。预算有限每个项目要投入固定成本并产生收益选哪些项目是典型的0-1背包。等和子集分割、最小差值分割。判断能不能把数组分成两个和相等的子集转换成背包容量为sum/2的可达性问题。完全背包与多重背包。完全背包的物品可以无限取内层循环改成正序多重背包有数量限制可以用二进制拆分转换成0-1背包。树上依赖背包。物品之间有依赖关系比如必须先选A才能选B就得用树形DP结合背包的思路。很多人学到背包九讲系列会觉得脑子装不下我的建议是先吃透0-1背包这一讲把状态定义、方程推导和滚动数组优化搞明白后面全是它的变体。你把这个模板理解透了面对一堆变体时会发现顺着思路走原来都是一个套路。最后说一点期末和面试的考试心得。这类题最常见的考法是判断能不能用贪心手推状态的转移过程给出dp表写出状态转移方程并说明时间复杂度在给定代码里补全循环的遍历方向让你解释为什么一维数组要倒序。这五个点如果你都能自己讲清楚那0-1背包这道题就算真正拿下了。我自己带过的学生里凡是能把表格亲手完整推一遍再写代码的人后续遇到完全背包、多重背包、分组背包这些升级版上手都特别快因为最底层的那根弦已经通了。
