知识梯度浅背包问题概念→ 浅中0-1 背包二维 DP→ 中滚动数组优化→ 中深416 分割等和子集→ 深完全背包→322 零钱兑换→ 升华背包问题总结目录引言从五步法到背包问题0-1 背包理论基础滚动数组优化416 分割等和子集完全背包理论基础322 零钱兑换背包问题总结结语参考文献引言从五步法到背包问题在上一篇中我们用 DP 五步法拆解了 70 爬楼梯和 198 打家劫舍掌握了计数型 DP和最值型 DP的基本框架。结尾我们预告了——背包问题。如果你刷过 LeetCode 上的 DP 题会发现一个现象背包问题几乎占据了 DP 中等题的半壁江山。416 分割等和子集、322 零钱兑换、518 零钱兑换 II、474 一和零、494 目标和……这些题看似各不相同但底层都共享同一个背包模板。思考为什么背包问题如此重要因为有限资源下的最优分配是计算机科学中最基础的问题模型之一——从内存分配到预算规划本质都是背包问题。背包问题体系庞大但入门的核心只有两个0-1 背包每个物品最多选一次和完全背包每个物品可以选无限次。掌握了这两个背包问题的半壁江山就属于你了。本文将以 DP 五步法为主线从 0-1 背包理论基础出发到滚动数组优化再到 416 分割等和子集0-1 背包应用接着是 322 零钱兑换完全背包应用最后做背包问题的系统总结。0-1 背包理论基础问题描述有 N 件物品和一个容量为 W 的背包。第 i 件物品的重量为w[i]价值为v[i]。每件物品只能用一次选或不选问在不超过背包容量的前提下装入哪些物品能使总价值最大这就是经典的0-1 背包问题——0-1的含义就是每个物品要么选1要么不选0没有中间选项。二维 dp 数组定义Step 1确定 dp 数组以及下标的含义dp[i][j]表示从下标为 [0, i] 的物品中任意取放入容量为 j 的背包能获得的最大价值。递推公式Step 2确定递推公式dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])不选物品 idp[i][j] dp[i-1][j]选物品 idp[i][j] dp[i-1][j - w[i]] v[i]思考为什么是 dp[i-1][j - w[i]] 而不是 dp[i][j - w[i]]因为每件物品只能选一次dp[i-1] 确保在考虑物品 i 之前的状态。如果是 dp[i][j - w[i]]那就意味着物品 i 可能被选了多次——这正是 0-1 背包和完全背包的分水岭。初始化Step 3dp 数组初始化dp[i][0] 0背包容量为 0什么都装不了dp[0][j]当j w[0]时dp[0][j] v[0]否则dp[0][j] 0其余元素可以初始化为 0遍历顺序Step 4确定遍历顺序两层 for 循环先遍历物品再遍历背包容量for i in range(N): # 遍历物品 for j in range(W1): # 遍历背包容量 if j w[i]: dp[i][j] dp[i-1][j] else: dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])打印 dp 验证Step 5举例推导 dp 数组假设物品w [1, 3, 4]v [15, 20, 30]背包容量 W 4。物品\容量 0 1 2 3 4 ----------------------------- 物品0(w1) 0 15 15 15 15 物品1(w3) 0 15 15 20 35 物品2(w4) 0 15 15 20 35最终dp[2][4] 35✅三语言代码二维 DP# Python 0-1 背包二维 DP def knapsack_2d(w, v, W): N len(w) dp [[0] * (W 1) for _ in range(N)] for j in range(w[0], W 1): dp[0][j] v[0] for i in range(1, N): for j in range(1, W 1): if j w[i]: dp[i][j] dp[i - 1][j] else: dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]) return dp[N - 1][W]// Java 0-1 背包二维 DP public int knapsack2D(int[] w, int[] v, int W) { int N w.length; int[][] dp new int[N][W 1]; for (int j w[0]; j W; j) { dp[0][j] v[0]; } for (int i 1; i N; i) { for (int j 1; j W; j) { if (j w[i]) { dp[i][j] dp[i - 1][j]; } else { dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]); } } } return dp[N - 1][W]; }// C 0-1 背包二维 DP int knapsack2D(vectorint w, vectorint v, int W) { int N w.size(); vectorvectorint dp(N, vectorint(W 1, 0)); for (int j w[0]; j W; j) { dp[0][j] v[0]; } for (int i 1; i N; i) { for (int j 1; j W; j) { if (j w[i]) { dp[i][j] dp[i - 1][j]; } else { dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w[i]] v[i]); } } } return dp[N - 1][W]; }二维 DP 表格填充过程滚动数组优化为什么可以优化当前行 i 只依赖上一行 i-1不需要保留所有行的数据用一维数组滚动更新即可。一维 dp 数组递推公式dp[j] max(dp[j], dp[j - w[i]] v[i])关键背包容量必须倒序遍历for i in range(N): for j in range(W, w[i] - 1, -1): # 倒序 dp[j] max(dp[j], dp[j - w[i]] v[i])思考为什么必须倒序因为一维 dp 中dp[j] 依赖 dp[j - w[i]]如果正序遍历dp[j - w[i]] 可能已经被当前物品 i 更新过了——这就相当于物品 i 被选了多次违反了 0-1 背包的约束。三语言代码一维 DP# Python 0-1 背包一维 DP def knapsack_1d(w, v, W): dp [0] * (W 1) for i in range(len(w)): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]// Java 0-1 背包一维 DP public int knapsack1D(int[] w, int[] v, int W) { int[] dp new int[W 1]; for (int i 0; i w.length; i) { for (int j W; j w[i]; j--) { dp[j] Math.max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }// C 0-1 背包一维 DP int knapsack1D(vectorint w, vectorint v, int W) { vectorint dp(W 1, 0); for (int i 0; i w.size(); i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }二维 vs 一维对比表维度二维 DP一维 DP空间复杂度O(N×W)O(W)代码行数较长极简理解难度直观需要理解倒序原因适用场景教学/推导过程面试/竞赛416 分割等和子集Medium题目描述给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。示例nums [1, 5, 11, 5]输出true[1, 5, 5] 和 [11]如何转换为 0-1 背包计算总和 sum如果 sum 为奇数直接返回 falsetarget sum / 2问题转化为能否从数组中选出一些数使它们的和恰好等于 target这就是一个 0-1 背包问题——每个数选或不选背包容量为 target问能否恰好装满五步法拆解Step 1dp[j] 的含义——dp[j]表示容量为 j 的背包是否能被装满true / falseStep 2递推公式——dp[j] dp[j] || dp[j - nums[i]]Step 3初始化——dp[0] true其余为 falseStep 4遍历顺序——先物品后背包背包容量倒序0-1 背包模板Step 5打印 dp 验证——以nums [1, 5, 11, 5]target 11为例初始化: dp [T, F, F, F, F, F, F, F, F, F, F, F] i0, nums[0]1: dp[1] T i1, nums[1]5: dp[5] T, dp[6] T i2, nums[2]11: dp[11] T i3, nums[3]5: dp[10] T, dp[11] 已是 T 最终 dp[11] true ✅三语言代码# Python 416 分割等和子集 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): dp[j] dp[j] or dp[j - num] return dp[target]// Java 416 分割等和子集 public boolean canPartition(int[] nums) { int total 0; for (int num : nums) total num; if (total % 2 ! 0) return false; int target total / 2; boolean[] dp new boolean[target 1]; dp[0] true; for (int num : nums) { for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; }// C 416 分割等和子集 bool canPartition(vectorint nums) { int total 0; for (int num : nums) total num; if (total % 2 ! 0) return false; int target total / 2; vectorbool dp(target 1, false); dp[0] true; for (int num : nums) { for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; }复杂度分析时间复杂度O(n × target)空间复杂度O(target)易错点sum 为奇数直接返回 falsedp 是 boolean 类型递推公式是||不是max背包容量从 target 倒序遍历完全背包理论基础与 0-1 背包的唯一区别完全背包和 0-1 背包的唯一区别是每个物品可以无限次选取。递推公式dp[j] max(dp[j], dp[j - w[i]] v[i])关键区别背包容量必须正序遍历for i in range(N): for j in range(w[i], W 1): # 正序 dp[j] max(dp[j], dp[j - w[i]] v[i])思考为什么正序遍历就变成了完全背包因为正序遍历时dp[j - w[i]] 可能已经被当前物品 i 更新过了——这意味着物品 i 可以被多次选取。遍历顺序的深意遍历顺序结果说明先物品后背包正序组合数不考虑顺序先背包后物品正序排列数考虑顺序三语言代码# Python 完全背包 def complete_knapsack(w, v, W): dp [0] * (W 1) for i in range(len(w)): for j in range(w[i], W 1): # 正序 dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]// Java 完全背包 public int completeKnapsack(int[] w, int[] v, int W) { int[] dp new int[W 1]; for (int i 0; i w.length; i) { for (int j w[i]; j W; j) { // 正序 dp[j] Math.max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }// C 完全背包 int completeKnapsack(vectorint w, vectorint v, int W) { vectorint dp(W 1, 0); for (int i 0; i w.size(); i) { for (int j w[i]; j W; j) { // 正序 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }0-1 背包 vs 完全背包对比表维度0-1 背包完全背包物品选取次数最多 1 次无限次一维 dp 内层遍历倒序正序内层循环起始j W到w[i]j w[i]到W先物品后背包组合数组合数先背包后物品排列数较少用排列数322 零钱兑换Medium题目描述给定不同面额的硬币coins和一个总金额amount计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。每种硬币的数量是无限的。示例coins [1, 2, 5], amount 11输出3551完全背包变体物品硬币每种无限量重量硬币面额价值1每个硬币计数为 1背包容量amount目标装满背包所需的最小物品个数五步法拆解Step 1dp[j] 的含义——dp[j]表示凑成金额 j 所需的最少硬币个数Step 2递推公式——dp[j] min(dp[j], dp[j - coins[i]] 1)Step 3初始化——dp[0] 0其余初始化为amount 1Step 4遍历顺序——先遍历硬币再遍历金额正序完全背包模板Step 5打印 dp 验证——以coins [1, 2, 5], amount 11为例初始化: dp [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] i0, coin1: dp[1]1, dp[2]2, ..., dp[11]11 i1, coin2: dp[2]1, dp[4]2, ..., dp[11]6 i2, coin5: dp[5]1, dp[10]2, dp[11]min(6, dp[6]1)3 最终 dp[11] 3 ✅递推过程 mermaid 图三语言代码# Python 322 零钱兑换 def coinChange(self, coins: List[int], amount: int) - int: dp [amount 1] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1// Java 322 零钱兑换 public int coinChange(int[] coins, int amount) { int[] dp new int[amount 1]; Arrays.fill(dp, amount 1); dp[0] 0; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] Math.min(dp[j], dp[j - coin] 1); } } return dp[amount] amount ? -1 : dp[amount]; }// C 322 零钱兑换 int coinChange(vectorint coins, int amount) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int coin : coins) { for (int j coin; j amount; j) { dp[j] min(dp[j], dp[j - coin] 1); } } return dp[amount] amount ? -1 : dp[amount]; }复杂度分析时间复杂度O(n × amount)空间复杂度O(amount)易错点初始化填最大值dp[0] 0其余填amount 1避免Integer.MAX_VALUE溢出无解返回 -1不是返回 0正序遍历完全背包背包问题总结0-1 背包 vs 完全背包维度0-1 背包完全背包每个物品选取次数最多 1 次无限次一维 dp 内层遍历倒序正序典型应用416 分割等和子集322 零钱兑换求组合数先物品后背包倒序先物品后背包正序求排列数先背包后物品倒序先背包后物品正序遍历顺序规律0-1 背包一维 for 物品: for 容量 in 倒序: ← 防止重复选取 完全背包一维求组合数 for 物品: for 容量 in 正序: ← 允许重复选取 完全背包一维求排列数 for 容量 in 正序: for 物品: ← 交换遍历顺序家族题一览题目类型核心思路416 分割等和子集0-1 背包是否存在target sum/2dp[j] dp[j] || dp[j-nums[i]]322 零钱兑换完全背包最小个数dp[j] min(dp[j], dp[j-coins[i]] 1)518 零钱兑换 II完全背包组合数dp[j] dp[j - coins[i]]377 组合总和 Ⅳ完全背包排列数先背包后物品474 一和零0-1 背包二维容量两个容量维度494 目标和0-1 背包方案数转换为 left - right target结语本期核心收获0-1 背包理论基础——二维 dp 数组、递推公式、五步法拆解滚动数组优化——从二维到一维理解倒序遍历原因416 分割等和子集——0-1 背包应用boolean 类型 dp完全背包理论基础——正序遍历允许重复选取322 零钱兑换——完全背包应用求最小个数背包问题总结——遍历顺序规律、家族题一览背包问题的本质就是在选与不选之间做最优决策。下期预告DP 进阶第二弹——打家劫舍系列213 打家劫舍 II 337 打家劫舍 III。参考文献力扣官方题解 - 416. 分割等和子集. 416. 分割等和子集 - 力扣LeetCode力扣官方题解 - 322. 零钱兑换. 322. 零钱兑换 - 力扣LeetCode代码随想录 - 背包理论基础二维 DP. 动态规划01背包理论基础 | 动态规划 | 01背包 | 二维dp数组 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源代码随想录 - 背包理论基础滚动数组. 动态规划01背包理论基础滚动数组 | 动态规划 | 滚动数组 | 01背包 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源代码随想录 - 完全背包理论基础. 完全背包理论基础-二维DP数组 | 完全背包 | 二维DP数组 | 状态转移 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源代码随想录 - 416. 分割等和子集. 416. 分割等和子集 | 01 背包 | 动态规划 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源代码随想录 - 322. 零钱兑换. 322. 零钱兑换 | 动态规划 | 完全背包 | 状态转移 | 代码随想录-全网最全算法数据结构刷题学习路线|图文视频教程|免费开源labuladong - 背包问题框架. https://labuladong.github.io/algo/di-ling-zh-bfe1b/bei-bao-yt-0e06a/