动态规划经典：01 背包问题超详细讲解

本期博客将01背包问题从问题本质、动态规划Dynamic Programming, DP设计思路、手动填表、空间优化、方案回溯、复杂度分析、面试高频考点一次性讲全讲透。一、01背包问题(Knapsack Problem)1.1 问题描述给定n 个物品第 i 个物品重量为wᵢ 0价值为vᵢ 0背包最大承重 W约束条件每个物品只能选 1 次0 不选 / 1 选不可分割不可重复目标在总重量不超过 W的前提下让背包内物品总价值最大化。1.2 同类应用场景01背包问题是资源分配类问题的通用模型现实中大量场景都可转化考试时间有限选题做以获得最高分数预算固定选择投资项目收益最大工厂产能固定分配生产任务利润最高货车装载、集装箱装箱优化1.3 贪心算法失效很多人第一反应按价值重量比 vᵢ/wᵢ从大到小贪心选取。我们直接用课件例题验证背包容量 W11物品列表1: w1, v1 比 1.02: w2, v6 比 3.03: w5, v18 比 3.64: w6, v22 比 3.6665: w7, v28 比 4.0贪心选择优先选比值最高的物品 57/28→ 物品 22/6→ 物品 11/1总重量72110 ≤11总价值286135最优解选择物品 35/18 物品 46/22总重量5611 ≤11总价值182240✅ 结论01背包无最优子结构的贪心选择性质贪心只能得到局部最优必须用动态规划二、DP求解 01 背包DP算法设计通常按如下步骤进行清晰定义子问题推导递归 / 状态转移方程自底向上计算子问题填表回溯重构最优方案2.1 步骤 1定义子问题直接采用课件标准答案OPT (i, w) 在前 i 个物品中背包容量限制为 w 时能获得的最大价值参数含义i考虑前 i 件物品规模缩小的子问题w当前背包可用容量最终答案OPT(n, W)n 个物品容量 W 的最优值2.2 步骤 2状态转移方程对第 i 个物品只有两种互斥决策不选第 i 个物品最大价值 前 i-1 个物品容量 w 的最优值即OPT(i-1, w)选第 i 个物品前提wᵢ ≤ w装得下最大价值 物品 i 的价值 前 i-1 个物品、容量 w−wᵢ 的最优值即vᵢ OPT(i-1, w−wᵢ)综合两种决策取最大值OPT(i,w){OPT(i−1,w)max(OPT(i−1,w), vi​OPT(i−1,w−wi​))​wi​w(装不下只能不选)else​✅ 课件选择题答案验证正确选项max( opt(i−1,w), vᵢ opt(i−1,w−wᵢ) )对应选项 D完全一致2.3 步骤 3初始条件动态规划必须先定义边界OPT(0, w) 0没有任何物品价值为 0OPT(i, 0) 0背包容量为 0装不下任何物品价值为 0三、DP填表演示物品1: w1, v12: w2, v63: w5, v184: w6, v225: w7, v28背包容量 W113.1 DP 表格含义行前 i 个物品列背包当前容量 w单元格值OPT (i,w)表格物品集合 \ 容量 w012345678910110 个物品000000000000{1}011111111111{1,2}016777777777{1,2,3}0167718192425252525{1,2,3,4}0167718222428292940{1,2,3,4,5}01677182228293435403.2 关键单元格计算示例以 OPT (2,3) 为例OPT (2,3) max ( OPT (1,3), 6 OPT (1, 3-21) ) max ( 1, 61 ) 7最终结果OPT (5,11)40对应选物品 3 物品 4。四、正确性证明DP正确性可用数学归纳法证明基例OPT (0,w)0OPT (i,0)0显然成立。归纳假设假设对所有 1 ≤ k ≤ i−1OPT (k,w) 都已正确计算。归纳步骤对第 i 个物品装不下只能继承前 i-1 的结果正确。装得下最优解必然是「不选 i」或「选 i」中的较大值正确。因此整个 DP 过程正确。五、复杂度深度分析5.1 时间复杂度两层循环物品数 n × 容量 W时间复杂度O (n・W)5.2 空间复杂度二维 DPO(n·W)一维优化O(W)5.3 伪多项式算法01 背包的复杂度O(nW)看似是多项式但 W 是输入数值不是输入比特长度。当 W 极大如 1e9时算法无法运行。因此 01 背包是伪多项式算法其判定问题是NP - 完全问题。5.4 近似算法存在多项式时间近似方案PTAS可得到误差 0.01% 以内的近似解适合大规模数据。六、01 背包 vs 完全背包类型物品数量容量遍历顺序核心区别01 背包每个只能选 1 次逆序遍历不可重复选完全背包可无限选正序遍历可重复选七、面试 / 考试高频问答01 背包为什么不能用贪心因为物品不可分割贪心无法保证全局最优。状态定义是什么dp [i][j] 前 i 个物品容量 j 的最大价值。转移方程怎么写max (不选 i选 i)。空间优化原理逆序遍历防止重复选取。复杂度是什么O (nW)伪多项式算法。八、总结01 背包物品仅选一次动态规划标准解法。状态dp [i][j] 前 i 个物品容量 j 的最大价值。转移dp[i][j] max(dp[i-1][j], v[i]dp[i-1][j-w[i]])。初始化dp[0][j]0dp[i][0]0。答案dp[n][W]。优化一维 DP 逆序遍历空间 O (W)。复杂度O (nW)伪多项式NP - 完全。