背包问题是动态规划的基石也是面试中出现频率最高的动态规划题型。几乎所有的动态规划问题最终都可以转化为某种背包问题。这一课我们会彻底搞懂0-1 背包、完全背包这两个最核心的背包类型掌握它们的通用模板以后遇到任何背包问题都能迎刃而解。一、背包问题的本质所有背包问题都可以用一句话概括有一个容量为C的背包和N种物品。每种物品有一定的重量w[i]和价值v[i]。问如何选择物品放入背包使得背包中物品的总价值最大根据物品的选择限制不同背包问题分为三类0-1 背包每种物品只能选0 个或 1 个最基础最重要完全背包每种物品可以选无限个多重背包每种物品最多可以选k[i]个面试出现频率低✅ 记住所有背包问题的解法都是从 0-1 背包演化而来的。只要彻底掌握了 0-1 背包其他背包问题都只是改一改遍历顺序而已。二、0-1 背包最基础也最重要的背包问题描述有N件物品和一个容量为C的背包。第i件物品的重量是w[i]价值是v[i]。每件物品只能使用一次。求解将哪些物品装入背包可使总价值最大。用动态规划四步走拆解步骤 1定义 dp 数组的含义dp[i][j]表示从前 i 件物品中选择放入容量为j的背包中能获得的最大价值。步骤 2找出状态转移方程对于第i件物品我们有两种选择不选它那么最大价值就是dp[i-1][j]前 i-1 件物品放入容量 j 的背包的最大价值选它那么最大价值就是dp[i-1][j - w[i]] v[i]前 i-1 件物品放入容量 j-w [i] 的背包的最大价值加上第 i 件物品的价值所以状态转移方程是plaintextdp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])步骤 3初始化 dp 数组dp[0][j] 0没有物品价值为 0dp[i][0] 0背包容量为 0价值为 0步骤 4确定遍历顺序先遍历物品再遍历背包容量。python运行for i in range(1, N1): for j in range(1, C1): # 状态转移方程二维数组解法代码python运行def knapsack01(w, v, C): N len(w) # 创建dp数组dp[i][j]表示前i件物品放入容量j的背包的最大价值 dp [[0] * (C 1) for _ in range(N 1)] for i in range(1, N 1): for j in range(1, C 1): if j w[i-1]: # 背包容量不够只能不选第i件物品 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][C]空间优化一维滚动数组观察状态转移方程可以发现dp[i][j]只依赖于dp[i-1][...]上一行的结果。所以我们不需要存储整个二维数组只需要存储一行即可这就是滚动数组。优化后的 dp 数组定义dp[j]表示容量为j的背包能获得的最大价值。优化后的状态转移方程plaintextdp[j] max(dp[j], dp[j - w[i]] v[i])⚠️ 最关键的一点背包容量必须从后往前遍历为什么因为如果从前往后遍历那么dp[j - w[i]]会被更新为第 i 件物品的结果而我们需要的是第 i-1 件物品的结果。从后往前遍历可以保证在计算dp[j]的时候dp[j - w[i]]还没有被更新仍然是上一行的结果。一维数组解法代码通用模板必须背下来python运行def knapsack01_optimized(w, v, C): N len(w) dp [0] * (C 1) for i in range(N): # 背包容量从后往前遍历 for j in range(C, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[C]✅ 这就是 0-1 背包的终极模板所有 0-1 背包问题都可以套用这个模板。经典例题LeetCode 416. 分割等和子集题目给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。转化为 0-1 背包问题数组的总和为sum如果sum是奇数直接返回 False问题转化为是否可以从数组中选出一些元素使得它们的和等于sum/2这就是一个 0-1 背包问题物品重量 元素值物品价值 元素值背包容量 sum/2如果最终dp[sum/2] sum/2说明可以分割代码python运行def canPartition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [0] * (target 1) for num in nums: for j in range(target, num - 1, -1): dp[j] max(dp[j], dp[j - num] num) return dp[target] target三、完全背包物品可以选无限个问题描述和 0-1 背包几乎一样唯一的区别是每种物品可以使用无限次。解法完全背包的解法和 0-1 背包几乎一模一样唯一的区别是背包容量从前往后遍历。为什么因为物品可以选无限次所以我们需要在计算dp[j]的时候使用已经更新过的dp[j - w[i]]也就是已经放入了第 i 件物品的结果这样就可以实现多次放入同一件物品。完全背包一维数组通用模板必须背下来python运行def knapsack_complete(w, v, C): N len(w) dp [0] * (C 1) for i in range(N): # 背包容量从前往后遍历这是和0-1背包唯一的区别 for j in range(w[i], C 1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[C]✅ 记住0-1 背包倒着遍历完全背包正着遍历这是两者唯一的区别。经典例题 1LeetCode 518. 零钱兑换 II题目给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。转化为完全背包问题物品 硬币物品重量 硬币面额背包容量 总金额问题有多少种方法可以装满背包状态转移方程dp[j] dp[j - coin]意思是凑成金额 j 的方法数等于凑成金额 j-coin 的方法数之和加上这枚硬币代码python运行def change(amount, coins): 计算可以凑成总金额的硬币组合数 :param amount: 总金额 :param coins: 硬币面额列表 :return: 组合数 # 初始化 dp 数组长度为 amount 1初始值全为 0 dp [0] * (amount 1) # 基准情况凑成金额 0 只有一种方法即不选任何硬币 dp[0] 1 # 外层循环遍历硬币物品 for coin in coins: # 内层循环遍历金额背包容量 # 从 coin 开始遍历因为小于 coin 的金额无法使用当前硬币 for j in range(coin, amount 1): # 状态转移 # 当前金额 j 的组合数 不使用当前硬币的组合数(dp[j]原值) 使用当前硬币的组合数(dp[j-coin]) dp[j] dp[j - coin] return dp[amount] # --- 测试示例 --- if __name__ __main__: # 示例 1 amount1 5 coins1 [1, 2, 5] # 解释 # 55 # 5221 # 52111 # 511111 # 共 4 种 result1 change(amount1, coins1) print(f示例 1: 金额{amount1}, 硬币{coins1} 组合数: {result1}) # 示例 2 amount2 3 coins2 [2] # 解释无法凑成 3因为只有一种面额 2 result2 change(amount2, coins2) print(f示例 2: 金额{amount2}, 硬币{coins2} 组合数: {result2}) # 示例 3 amount3 10 coins3 [10] # 解释只有一种方法 1010 result3 change(amount3, coins3) print(f示例 3: 金额{amount3}, 硬币{coins3} 组合数: {result3})经典例题 2LeetCode 322. 零钱兑换这是上一课的例题现在用完全背包的模板重新看一下python运行def coinChange(coins, amount): 计算凑成总金额所需的最少硬币个数 # 1. 初始化 dp 数组 # dp[j] 表示凑成金额 j 所需的最少硬币数 # 初始化为 amount 1 相当于“无穷大”因为即使全用 1 元硬币最多也只需要 amount 个 dp [amount 1] * (amount 1) # 2. 设置初始状态 # 凑成金额 0 需要 0 个硬币 dp[0] 0 # 3. 开始动态规划 # 外层循环遍历每一种硬币 for coin in coins: # 内层循环遍历背包容量金额从 coin 开始直到 amount # 正序遍历表示完全背包硬币可以重复使用 for j in range(coin, amount 1): # 状态转移方程 # 当前金额 j 的最少硬币数 min( # 不使用当前硬币时的数量 dp[j], # 使用当前硬币后的数量 dp[j - coin] 1 # ) dp[j] min(dp[j], dp[j - coin] 1) # 4. 返回结果 # 如果 dp[amount] 仍然是初始的“无穷大”值说明无法凑出返回 -1 if dp[amount] amount: return -1 else: return dp[amount] # --- 测试示例 --- if __name__ __main__: # 示例 1 coins1 [1, 2, 5] amount1 11 # 预期输出: 3 (11 5 5 1) res1 coinChange(coins1, amount1) print(f示例 1: 硬币{coins1}, 目标金额{amount1} - 最少硬币数: {res1}) # 示例 2 coins2 [2] amount2 3 # 预期输出: -1 (无法用 2 凑出 3) res2 coinChange(coins2, amount2) print(f示例 2: 硬币{coins2}, 目标金额{amount2} - 最少硬币数: {res2}) # 示例 3 coins3 [1] amount3 0 # 预期输出: 0 (金额为 0 不需要硬币) res3 coinChange(coins3, amount3) print(f示例 3: 硬币{coins3}, 目标金额{amount3} - 最少硬币数: {res3})✅ 对比零钱兑换和零钱兑换 II求最少硬币数dp[j] min(dp[j], dp[j - coin] 1)求组合数dp[j] dp[j - coin]两者都是完全背包问题只是状态转移方程不同四、多重背包了解即可问题描述每种物品最多可以选k[i]个。解法最朴素的解法是把多重背包转化为 0-1 背包把第 i 种物品拆成k[i]个相同的物品然后用 0-1 背包的解法。优化解法二进制拆分法把k[i]拆成 2 的幂次之和这样可以把时间复杂度从 O (NCk) 降低到 O (NClogk)。面试说明多重背包在面试中出现频率极低几乎不会考。只需要知道它可以转化为 0-1 背包即可。五、背包问题解题技巧总结判断背包类型物品只能选一次 → 0-1 背包倒着遍历容量物品可以选无限次 → 完全背包正着遍历容量物品最多选 k 次 → 多重背包转化为 0-1 背包定义 dp 数组求最大价值dp[j]表示容量 j 的背包能装的最大价值求组合数dp[j]表示装满容量 j 的背包有多少种方法求最少物品数dp[j]表示装满容量 j 的背包最少需要多少个物品初始化求最大价值初始化为 0求组合数dp[0] 1其他为 0求最少物品数初始化为一个很大的数dp[0] 0