1. 引言为什么背包问题如此重要在动态规划Dynamic Programming, DP的学习历程中背包问题Knapsack Problem是一个绕不开的经典模型。它不仅是算法竞赛如ACM、蓝桥杯的基础考点更是面试中尤其是字节、腾讯、阿里等大厂高频出现的题型。为什么重要因为背包问题的本质是“有限资源下的最优选择”。我们有一个容量有限的背包资源限制。我们有若干物品每个物品有重量成本和价值收益。我们要决定“选”还是“不选”每个物品使得总价值最大。这种“在约束条件下做决策”的思想可以抽象出无数实际问题预算分配、任务调度、投资组合、甚至文字排版。0-1背包01 Knapsack是其中最基础的一种它的核心特征是每种物品最多只能拿一次要么拿0个要么拿1个。2. 0-1背包问题的定义与模型我们先用数学语言定义一下有N件物品编号从 1 到 N。背包的最大容量为V。第i件物品的重量体积为w[i]价值为v[i]。目标在总重量不超过V的前提下选择若干物品使得总价值最大。约束条件对于每一件物品要么选1要么不选0。不能选一部分也不能选多次。输入示例textN 4, V 8 物品1: 重量2价值3 物品2: 重量3价值4 物品3: 重量4价值5 物品4: 重量5价值8最优解选物品2和物品4总重量358总价值4812。或者选物品1和物品3重量246价值358不是最优。3. 初识动态规划核心思想动态规划的核心是“状态定义”和“状态转移”。我们通过解决子问题逐步推导出最终答案。3.1 状态定义二维数组定义dp[i][j]表示只考虑前i个物品背包容量为j时能够获得的最大价值。i的范围0 到 N。j的范围0 到 V。最终答案dp[N][V]。这里有一个非常重要的点i0表示没有物品可选此时无论背包容量多大价值都是0。所以dp[0][j] 0。3.2 递推公式状态转移方程当我们面对第i个物品重量w[i]价值v[i]时只有两种选择不选或者选。不选第i个物品那么当前状态的价值就完全由前i-1个物品决定且背包容量不变。dp[i][j] dp[i-1][j]选第i个物品前提是当前背包容量j至少能放下这个物品j w[i]。既然选了它我们就需要先给这个物品腾出w[i]的空间然后在前i-1个物品中用容量j - w[i]去装最后加上当前物品的价值v[i]。dp[i][j] 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]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]。3.3 初始化细节对于二维数组我们通常初始化dp[0][j] 00个物品价值为0。dp[i][0]表示容量为0放不下任何物品也为0。在实际编程中我们通常从i1开始遍历物品因为i0是边界。3.4 遍历顺序对于二维DP遍历顺序可以是先物品后容量也可以先容量后物品甚至是混合。因为dp[i][j]只依赖于上一行dp[i-1][...]的数据不依赖于本行已经计算的数据。通常我们采用外层遍历物品内层遍历容量这样符合人的思维习惯一个一个物品考虑对于每个物品尝试所有可能的容量。3.5 二维DP代码实现与模拟pythondef knapsack_2d(N, V, w, v): # dp[i][j]: 前i个物品容量j下的最大价值 dp [[0] * (V 1) for _ in range(N 1)] for i in range(1, N 1): # 遍历物品 for j in range(1, V 1): # 遍历容量 if j w[i-1]: # 注意w和v列表索引从0开始 dp[i][j] dp[i-1][j] else: dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i-1]] v[i-1]) return dp[N][V] # 测试 N, V 4, 8 w [2, 3, 4, 5] v [3, 4, 5, 8] print(knapsack_2d(N, V, w, v)) # 输出: 12模拟过程部分以物品1w2,v3为例j1: 放不下dp[1][1]dp[0][1]0j2: max(dp[0][2]0, dp[0][0]33) 3j3...8: 同理都是3物品2w3,v4j3: max(dp[1][3]3, dp[1][0]44) 4j5: max(dp[1][5]3, dp[1][2]4347) 7最终dp[4][8]为12。4. 空间优化一维DP滚动数组4.1 原理分析观察二维递推公式dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])我们发现当前层i的状态只依赖于上一层i-1的状态。因此我们不需要保存所有i层的数据只需要一个一维数组dp[j]来表示“当前考虑前若干个物品时容量为 j 的最大价值”。但这里有一个关键点如果我们在内层循环中正序遍历j会发生什么假设dp[j]正在被更新它依赖的是dp[j - w[i]]较小容量。如果j从小到大遍历那么当计算到较大的j时dp[j - w[i]]可能已经被本轮的物品i更新过了即已经使用了该物品这就导致了物品被重复使用违反了01背包的“每个物品最多取一次”原则。4.2 为什么需要逆序遍历为了防止同一物品被重复使用我们必须保证在计算dp[j]时dp[j - w[i]]还没有被当前物品更新过即它仍然是上一轮前i-1个物品的状态。解决方案内层循环对j从V到w[i]逆序遍历。当j较大时j - w[i]较小。逆序保证了j - w[i]一定小于j且因为我们是逆序j - w[i]在本轮循环中还没有被处理它仍然是上一轮的结果。这就是滚动数组的精髓。4.3 一维DP代码实现pythondef knapsack_1d(N, V, w, v): dp [0] * (V 1) for i in range(N): # 遍历物品 # 逆序遍历容量确保每个物品只使用一次 for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[V] # 测试 print(knapsack_1d(N, V, w, v)) # 输出: 12注意一维DP中初始化依然是dp[0] 0其他为0代表没放物品时价值为0。但如果题目要求“恰好装满”初始化会不同后面会讲到。5. 进阶变种01背包问题的延伸5.1 恰好装满背包问题描述要求背包恰好装满求最大价值若无法恰好装满则输出0或-1。核心变化初始化在普通01背包中dp[j]可以代表“容量不超过 j 时的最大价值”不要求恰好。但要求恰好装满时我们定义dp[j]为“容量恰好为 j 时的最大价值”。初始化dp[0] 0容量0恰好装满价值0。其他dp[j]初始化为负无穷如-inf表示无法恰好装满的状态。状态转移不变但只有从非负无穷的状态转移过来才有意义。pythondef knapsack_exact(N, V, w, v): INF -10**9 dp [INF] * (V 1) dp[0] 0 for i in range(N): for j in range(V, w[i] - 1, -1): if dp[j - w[i]] ! INF: dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[V] if dp[V] ! INF else 0 # 或返回-1表示无解5.2 求最大价值与求方案数有时我们需要求出达到最大价值的方案数。状态定义dp[j]容量为 j 时的最大价值。cnt[j]达到dp[j]的方案数。初始化dp[0] 0,cnt[0] 1什么也不选是一种方案其他dp[j] 0价值0cnt[j] 1还是0通常初始为0但要根据具体题目分析。转移时如果dp[j] dp[j - w[i]] v[i]说明选当前物品得到更优价值则更新dp[j]并设置cnt[j] cnt[j - w[i]]。如果dp[j] dp[j - w[i]] v[i]说明两种选择价值相同则方案数相加cnt[j] cnt[j - w[i]]。注意需要处理数据范围可能取模。5.3 求字典序最小的方案当存在多个最优解时题目可能要求输出字典序最小的物品编号序列即选中的物品编号按升序排列后字典序最小。思路由于字典序比较是优先比较第一个物品再比较第二个……因此我们应该从最后一个物品向前遍历这样在DP过程中当价值相同时优先选择编号较小的物品即当前物品。具体做法用二维DP记录所有状态或倒序一维DP以便回溯。物品从 N 到 1 遍历逆序。这样dp[i][j]表示从第 i 个到第 N 个物品中选的最大价值。回溯时从dp[1][V]开始如果dp[i][j] dp[i1][j]且dp[i][j] dp[i1][j - w[i]] v[i]为了字典序最小优先选择当前物品因为编号小。另一种常见技巧在DP比较时价值相等的情况下优先保留选择当前物品的状态因为物品编号从小到大选当前的比不选的要小。5.4 二维费用的背包问题问题描述每个物品有两种不同的成本如重量和体积背包有两个容量限制。状态定义dp[i][j]表示第一维成本为 i第二维成本为 j 时的最大价值。转移dp[j][k] max(dp[j][k], dp[j - w1[i]][k - w2[i]] v[i])。遍历顺序依然是逆序且两层内循环都是逆序。5.5 分组背包与01背包的关系分组背包物品被分成若干组每组内最多只能选一个物品。这其实就是01背包的扩展把每组看作一个“超级物品”但这个超级物品在组内需要选择最优的那一个。解法外层遍历组内层遍历容量最内层遍历组内物品即对于每个容量比较组内所有物品。6. 实战演练LeetCode题目精讲6.1 LeetCode 416. 分割等和子集题目给定一个非空的正整数数组nums判断是否可以分割成两个子集使得两个子集的元素和相等。分析如果总和sum是奇数直接返回 False。否则问题转化为能否从数组中选出若干个数使其和为sum/2这就是一个典型的“恰好装满”的01背包问题只不过这里重量和价值都是数字本身。解法dp[j]表示能否达到容量 j。初始化dp[0]True。pythonclass Solution: def canPartition(self, nums: List[int]) - bool: total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num - 1, -1): if dp[j - num]: dp[j] True return dp[target]6.2 LeetCode 1049. 最后一块石头的重量 II题目有一堆石头每次选两块相撞重量差为新石头。求最后剩下的最小可能重量。分析本质上我们试图将石头分成两堆使得两堆的重量差最小。设总和为sum若一堆重量为x则另一堆为sum-x差值为|sum - 2x|。要最小化差值就要最大化x且x sum/2。所以问题转化为在不超过sum/2的情况下选石头使总重量最大最接近sum/2。这就是一个普通的01背包不要求恰好装满。pythonclass Solution: def lastStoneWeightII(self, stones: List[int]) - int: total sum(stones) target total // 2 dp [0] * (target 1) for stone in stones: for j in range(target, stone - 1, -1): dp[j] max(dp[j], dp[j - stone] stone) return total - 2 * dp[target]6.3 LeetCode 494. 目标和题目给数组每个数字前添加或-使得结果为 S。求方案数。分析设所有正数的和为pos负数的和为neg总和为sum则有pos - neg S且pos neg sum。解得pos (sum S) / 2。因此问题转化为从数组中选若干个数使其和为pos的方案数因为选了就是正数没选就是负数。这是一个“恰好装满”的方案数问题。注意sum S必须为非负偶数否则无解。pythonclass Solution: def findTargetSumWays(self, nums: List[int], target: int) - int: total sum(nums) if (total target) % 2 ! 0 or abs(target) total: return 0 pos (total target) // 2 dp [0] * (pos 1) dp[0] 1 for num in nums: for j in range(pos, num - 1, -1): dp[j] dp[j - num] return dp[pos]6.4 LeetCode 474. 一和零题目给定一个字符串数组每个字符串由0和1组成。最多有 m 个0和 n 个1问最多能选多少个字符串。分析每个字符串消耗一定数量的0和1相当于有两个维度的成本。这就是二维费用的01背包。状态dp[i][j]表示使用 i 个0和 j 个1时最多能选的字符串数量。pythonclass Solution: def findMaxForm(self, strs: List[str], m: int, n: int) - int: dp [[0] * (n 1) for _ in range(m 1)] for s in strs: zeros s.count(0) ones s.count(1) for i in range(m, zeros - 1, -1): for j in range(n, ones - 1, -1): dp[i][j] max(dp[i][j], dp[i - zeros][j - ones] 1) return dp[m][n]7. 与其他算法的对比7.1 贪心算法为什么不行有人可能会想按“性价比”价值/重量排序优先选性价比高的行吗不行。贪心算法在背包问题中只适用于可分割的背包分数背包。对于01背包贪心会导致错误。例如容量 V4物品 A: w3, v4 (性价比1.33)物品 B: w2, v3 (性价比1.5)物品 C: w2, v2 (性价比1)贪心选性价比高的 B 和 C总重4价值5但实际最优是选 A价值4不对最优是选 B 和 C5这里贪心恰好对了。换一组V3A: w2, v3 (1.5)B: w3, v4 (1.33)贪心选 A价值3但选 B 价值4更优。所以贪心不可靠。7.2 与完全背包的区别完全背包每种物品可以选无限次。状态转移dp[i][j] max(dp[i-1][j], dp[i][j - w[i]] v[i])。一维实现时内层循环正序因为允许重复使用。而01背包必须逆序。8. 总结与练习建议核心要点回顾01背包定义每个物品最多选一次求容量限制下的最大价值。二维DPdp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])空间O(NV)。一维DP滚动数组dp[j] max(dp[j], dp[j-w[i]] v[i])内层容量逆序空间O(V)。变种恰好装满初始化负无穷dp[0]0。求方案数额外数组计数。二维费用两层逆序循环。分组背包外层组内层容量最内层组内物品。练习建议手推状态转移表对于小规模数据在纸上画出二维DP表理解每一步的来源。多刷LeetCode416. 分割等和子集最后一块石头的重量 II目标和一和零盈利计划二维费用方案数打家劫舍本质是01背包在序列上的应用进阶挑战尝试解决「背包九讲」中的其他变种如依赖背包、泛化物品等。最后请记住背包问题的核心是抽象。当你看到“有限资源下的取舍”问题时第一时间就应该联想到动态规划并尝试用背包模型的思维去定义状态。