LeetCode刷题必备0-1背包问题从暴力回溯到动态规划的完整优化思路每次看到算法面试中出现的背包问题不少同学的第一反应都是这个题目我见过但具体解法想不起来了。0-1背包作为动态规划领域的经典问题其重要性不亚于排序算法中的快速排序。今天我们就从最基础的暴力回溯开始一步步推导到空间优化的动态规划解法让你彻底掌握这个算法面试中的常客。1. 从暴力回溯开始理解问题本质在解决任何算法问题时理解问题本质都是第一步。0-1背包问题的描述很简单给定一组物品每个物品有重量和价值在不超过背包承重的情况下如何选择物品使总价值最大。这里的0-1意味着每个物品要么完整放入要么完全不放入。1.1 回溯法的基本思路回溯法本质上是一种暴力穷举的优化版本它通过递归尝试所有可能的组合def backtrack(weights, values, capacity, index, current_weight, current_value): if index len(weights): return current_value # 不选当前物品 max_value backtrack(weights, values, capacity, index1, current_weight, current_value) # 选当前物品前提是不超重 if current_weight weights[index] capacity: max_value max(max_value, backtrack(weights, values, capacity, index1, current_weight weights[index], current_value values[index])) return max_value这种解法的时间复杂度是O(2^n)因为每个物品都有选或不选两种可能。当n20时需要处理约100万种组合n30时这个数字会暴涨到10亿级别。1.2 回溯法的优化空间虽然回溯法能解决问题但效率太低。我们可以通过以下方式优化记忆化搜索记录已经计算过的状态剪枝提前终止不可能得到更优解的分支但即便如此回溯法在大规模问题上仍然力不从心。这就引出了我们需要更高效的解法——动态规划。2. 动态规划的标准解法动态规划通过将问题分解为子问题并存储子问题的解来避免重复计算。对于0-1背包问题最直观的是二维DP解法。2.1 二维DP数组的定义我们定义dp[i][j]表示考虑前i个物品背包容量为j时的最大价值。这个定义是理解整个问题的关键。2.2 状态转移方程对于每个物品我们有两种选择不放入dp[i][j] dp[i-1][j]放入如果不超过容量dp[i][j] dp[i-1][j-weight[i]] value[i]因此状态转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])2.3 完整实现示例def knapsack_2d(weights, values, capacity): n len(weights) dp [[0]*(capacity1) for _ in range(n1)] for i in range(1, n1): for j in range(1, capacity1): if j weights[i-1]: dp[i][j] max(dp[i-1][j], dp[i-1][j-weights[i-1]] values[i-1]) else: dp[i][j] dp[i-1][j] return dp[n][capacity]这种解法的时间复杂度是O(ncapacity)空间复杂度也是O(ncapacity)。对于大多数实际问题这已经比回溯法高效得多。3. 空间优化一维DP滚动数组仔细观察二维DP的实现我们会发现dp[i][j]只依赖于dp[i-1][...]这意味着我们可以将空间复杂度优化到O(capacity)。3.1 一维DP的实现关键使用一维数组dp[j]表示容量为j时的最大价值。关键点在于倒序遍历容量防止同一物品被多次计算状态转移简化dp[j] max(dp[j], dp[j-weight[i]] value[i])3.2 优化后的实现def knapsack_1d(weights, values, capacity): dp [0]*(capacity1) for i in range(len(weights)): for j in range(capacity, weights[i]-1, -1): dp[j] max(dp[j], dp[j-weights[i]] values[i]) return dp[capacity]这种实现不仅节省了空间代码也更加简洁。在实际面试中推荐使用这种写法。4. 背包问题的变种与应用掌握了标准0-1背包问题后我们可以解决LeetCode上的许多变种问题。以下是几个典型例子4.1 分割等和子集LeetCode 416这个问题可以转化为是否能找到一些数使它们的和等于总和的一半。def canPartition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False]*(target1) dp[0] True for num in nums: for j in range(target, num-1, -1): dp[j] dp[j] or dp[j-num] return dp[target]4.2 目标和LeetCode 494这个问题需要计算通过加减得到目标值的所有方法数。def findTargetSumWays(nums, target): total sum(nums) if (total target) % 2 ! 0 or abs(target) total: return 0 pos (total target) // 2 dp [0]*(pos1) dp[0] 1 for num in nums: for j in range(pos, num-1, -1): dp[j] dp[j-num] return dp[pos]4.3 最后一块石头的重量 IILeetCode 1049这个问题可以转化为将石头分成两堆使两堆的重量差最小。def lastStoneWeightII(stones): total sum(stones) target total // 2 dp [False]*(target1) dp[0] True for stone in stones: for j in range(target, stone-1, -1): dp[j] dp[j] or dp[j-stone] max_weight max([i for i in range(target1) if dp[i]]) return total - 2*max_weight5. 实战技巧与常见错误在解决背包问题时有几个常见陷阱需要注意遍历顺序错误在一维DP中内层循环必须倒序初始化不当dp[0]通常需要初始化为0或1边界条件处理特别是当背包容量小于物品重量时问题转化错误不是所有看似背包的问题都能直接套用模板建议在面试前至少亲手实现3-5个不同变种的背包问题确保对各种情况都有清晰的理解。