动态规划经典：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ᵢ从大到小贪心选取。我们直接用课件例题验证：背包容量 W=11物品列表：1: w=1, v=1 （比 1.0）2: w=2, v=6 （比 3.0）3: w=5, v=18 （比 3.6）4: w=6, v=22 （比 3.666）5: w=7, v=28 （比 4.0）

贪心选择：优先选比值最高的物品 5（7/28）→ 物品 2（2/6）→ 物品 1（1/1）总重量：7+2+1=10 ≤11总价值：28+6+1=35

最优解：选择物品 3（5/18）+ 物品 4（6/22）总重量：5+6=11 ≤11总价值：18+22=40

✅ 结论：01背包无最优子结构的贪心选择性质，贪心只能得到局部最优，必须用动态规划！

二、DP求解 01 背包

DP算法设计通常按如下步骤进行：

1. 清晰定义子问题
2. 推导递归 / 状态转移方程
3. 自底向上计算子问题（填表）
4. 回溯重构最优方案

2.1 步骤 1：定义子问题

直接采用课件标准答案：OPT (i, w) = 在前 i 个物品中，背包容量限制为 w 时，能获得的最大价值

参数含义：

• i：考虑前 i 件物品（规模缩小的子问题）
• w：当前背包可用容量
• 最终答案：OPT(n, W)（n 个物品，容量 W 的最优值）

2.2 步骤 2：状态转移方程

对第 i 个物品，只有两种互斥决策：

1. 不选第 i 个物品最大价值 = 前 i-1 个物品，容量 w 的最优值即：OPT(i-1, w)

2. 选第 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：没有任何物品，价值为 0
• OPT(i, 0) = 0：背包容量为 0，装不下任何物品，价值为 0

三、DP填表演示

物品：1: w=1, v=12: w=2, v=63: w=5, v=184: w=6, v=225: w=7, v=28背包容量 W=11

3.1 DP 表格含义

行：前 i 个物品列：背包当前容量 w单元格值：OPT (i,w)

表格

3.2 关键单元格计算示例

以 OPT (2,3) 为例：OPT (2,3) = max ( OPT (1,3), 6 + OPT (1, 3-2=1) )= max ( 1, 6+1 ) =7

最终结果：OPT (5,11)=40，对应选物品 3 + 物品 4。

四、正确性证明

DP正确性可用数学归纳法证明：

1. 基例OPT (0,w)=0，OPT (i,0)=0，显然成立。

2. 归纳假设假设对所有 1 ≤ k ≤ i−1，OPT (k,w) 都已正确计算。

3. 归纳步骤对第 i 个物品：

• 装不下：只能继承前 i-1 的结果，正确。
• 装得下：最优解必然是「不选 i」或「选 i」中的较大值，正确。

因此整个 DP 过程正确。

五、复杂度深度分析

5.1 时间复杂度

• 两层循环：物品数 n × 容量 W
• 时间复杂度：O (n・W)

5.2 空间复杂度

• 二维 DP：O(n·W)
• 一维优化：O(W)

5.3 伪多项式算法

• 01 背包的复杂度O(nW)看似是多项式，但 W 是输入数值，不是输入比特长度。
• 当 W 极大（如 1e9）时，算法无法运行。
• 因此 01 背包是伪多项式算法，其判定问题是NP - 完全问题。

5.4 近似算法

存在多项式时间近似方案（PTAS），可得到误差 0.01% 以内的近似解，适合大规模数据。

六、01 背包 vs 完全背包

七、面试 / 考试高频问答

1. 01 背包为什么不能用贪心？因为物品不可分割，贪心无法保证全局最优。
2. 状态定义是什么？dp [i][j] = 前 i 个物品，容量 j 的最大价值。
3. 转移方程怎么写？max (不选 i，选 i)。
4. 空间优化原理？逆序遍历，防止重复选取。
5. 复杂度是什么？O (nW)，伪多项式算法。

八、总结

1. 01 背包：物品仅选一次，动态规划标准解法。
2. 状态：dp [i][j] = 前 i 个物品，容量 j 的最大价值。
3. 转移：dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])。
4. 初始化：dp[0][j]=0，dp[i][0]=0。
5. 答案：dp[n][W]。
6. 优化：一维 DP 逆序遍历，空间 O (W)。
7. 复杂度：O (nW)，伪多项式，NP - 完全。