01背包问题

01 背包问题

是动态规划入门的经典题目，这个问题涉及的内容并不简单，这篇文章并不直接讲状态转移，而是通过“继承”来讲“状态转移”。

注意：动态规划（Dynamic Programming）在后续称为 dp 或 DP

一、问题：登山装备选择

想象你是一名登山者，准备征服一座高峰。你有一个限重 10kg 的背包，面前有多种装备可以选择。每种装备都有重量和重要程度（价值），但背包容量有限。你会如何选择装备，让这次登山之旅获得最大价值？

graph TD A[有一个背包] --> B[容量限制: 10kg] C[有多种装备] --> D[每种装备有重量wi] C --> E[每种装备有价值vi] B --> F[选择问题] D --> F E --> F F --> G[目标: 最大化总价值] F --> H[约束: 总重量 ≤ 10kg] G --> I[每种装备只能选0次或1次] H --> I

装备清单：

装备	重量	价值	性价比(价值/重量)
水壶	2kg	6元	3.0
食物	3kg	8元	2.67
帐篷	4kg	9元	2.25
睡袋	5kg	10元	2.0

这就是经典的

01背包问题

：每种装备只能选择0次或1次。

二、为什么简单策略会失败？

1. 按价值排序选择

睡袋(10元) → 帐篷(9元) → 食物(8元)
重量：5+4+3=12kg > 10kg，超重了！
只能选睡袋+帐篷：价值19元，重量9kg

2. 按性价比排序选择

水壶(3.0) → 食物(2.67) → 帐篷(2.25) → 睡袋(2.0)
水壶+食物+帐篷：重量 2+3+4=9kg，价值 6+8+9=23元
剩余1kg装不下睡袋

但真的是最优吗？

如果选择 水壶+睡袋 呢？

重量：2+5=7kg，价值：6+10=16元，还剩 3kg
再加食物：总重量10kg，总价值24元！

这说明

贪心策略不能保证全局最优

，我们需要考虑所有可能的组合。

graph LR A[贪心策略的问题] --> B[按价值选择] A --> C[按重量选择] A --> D[按性价比选择] B --> E[可能超重或浪费空间] C --> F[可能总价值很低] D --> G[局部最优≠全局最优] E --> H[需要全局视角] F --> H G --> H

三、一个更聪明的解决方案

我们可以使用动态规划来解决！这个名字咋听上去很夸张，实际上就是

把大问题拆成一串小问题，把小问题的答案记下来，省得重复算。

怎么理解呢？

相信你小学的时候做过这样一道题：

小明想买 18 元的书，手里有 5 元、6 元、7 元的零钱各若干张，
最少需要几张
？

那时候你不懂任何算法，但是你却能做出来，原因是穷举所有可能。

先列出所有可能（从少到多试）。
- 只用 1 张？5、6、7 都不够 18，不行。
- 用 2 张？
  5+5=10，不够
  5+6=11，不够
  …
  7+7=14，还是不够 → 2 张不行。
用 3 张？
把 5、6、7
像积木一样加 3 次
，找到正好 18 的组合：
6 + 6 + 6 = 18 ✔️
其它 3 张组合都不是 18。

现在已经没有必要计算更多张了，三张 6 就是最优解。

以上就是最简单的穷举。

但是你可能也会用面额反推张数的方法：

6 元需要一张 6 元，
7 元需要一张 7 元，
8 元不能计算
9 月不能计算
10 元不能计算
11 元需要 5 + 6 元
12 元需要 6 + 6 元
13 元需要 6 + 7 元
14 元需要 7 + 7 元，这里已经使用了最大面额两张，意味着下一个数额必须增加一张。
15 元需要 5 + 5 + 5 元
16 元需要 5 + 5 + 6 元
17 元需要 5 + 6 + 6 元
18 元需要 6 + 6 + 6 元

这就是动态规划！

动态规划

简单来说就是记小答案：

先算 1 元最少几张，2 元最少几张……直到 18 元，每一步都把答案写在小纸条上。
算 13 元时，直接看「13-5」「13-6」「13-7」这三张纸条的最小值 +1 即可，
不用重新算
。
最后纸条上 18 元的位置写着
3
（6+6+6）。

1. 核心思想

如果我们已经知道了"前 i-1种装备的最优解"，能否推导出"前 i 种装备的最优解"？

我们只需要知道当前这个装备是不是能装下：

如果不能，那之前的就是最优解。
如果能，那么再看价值是哪个高：
- 如果选的价值高，就装下。
- 如果不选的价值高，就不装。

如此反复计算即可。关于这个方法的完备性（是否为全局最优解），马上会解释。

graph TD A[面对第i种装备] --> B{背包装得下吗?} B -->|装不下| C["dp[i][w] = dp[i-1][w]"] B -->|装得下| D[两个选择比较] D --> E["不选：dp[i-1][w]"] D --> F["选择：dp[i-1][w-重量[i]] + 价值[i]"] E --> G[取最大值] F --> G G --> H["dp[i][w] = max(不选, 选择)"]

状态定义：

dp[i][w] = 考虑前 i 种装备，背包容量为 w 时的最大价值

dp 表示动态规划的表格，关于这个表格可以先查看后面的填表部分

状态转移方程：

如果 重量[i] > w： dp[i][w] = dp[i-1][w] // 装不下，只能不选 否则： dp[i][w] = max( dp[i-1][w], // 不选第i种装备 dp[i-1][w-重量[i]] + 价值[i] // 选第i种装备 )

2. 关于完备性的疑问

在我学习这个算法的时候，心里有很多疑问，比如有没有可能当前物品装不下，但是当前的物品和之前的某个物品构成最优解，在算法中却被忽略的情况，即是否满足数学上的完备性？这个问题我们在这里解释。

我们可以通过归纳来理解：

首先我们画个图表，你也可以查看详细的填表过程：

装备\容量	2	3	4	5	6	7	8	9	10
无装备 - 0kg - 0v	0	0	0	0	0	0	0	0	0
水壶 - 2kg - 6v	6	6	6	6	6	6	6	6	6
食物 - 3kg - 8v	6	8	8	14	14	14	14	14	14
帐篷 - 4kg - 9v	6	8	9	14	15	17	17	23	23
睡袋 - 5kg - 10v	6	8	9	14	16	17	18	23	24

我们和算法填表的方向要么是从上往下，要么是从左往右，这样的方式保证了下一个值将继承上一个值，什么意思呢？

比如我们背包容量（kg）为 0、1、2、3、10 的时候，我们选择的过程是怎样的？

背包容量为 0kg 的时候，不能装任何东西，但是需要注意，不装任何东西就是最优解。

背包容量为 1kg 的时候，也不能装任何东西，也是最优解。

背包容量为 2kg 的时候，只可以装水壶，是最优解。

背包容量为 3kg 的时候，可以装食物，那么要不要装呢？

之前的最优解是水壶，价值为 6v，现在可以选择的是食物，价值为 8v，相比之下，食物的价值高于水壶，所以选择食物。
装食物是最优解。

背包容量为 10，的时候，我们可以推断背包容量为 9 的时候，前一个背包容量所标记的价值数是最优解。

但是，真的是这样吗？

这是水平继承和垂直继承的根本区别，水平继承是贪心算法，即：当前选什么只与上一个背包容量有关。

它通过在每一步选择当前状态下看起来最优的解，逐步推导出问题的解。贪心算法的核心思想是局部最优选择，即每一步都做出当前最优的决策，而不考虑全局最优解的整体情况。

比如在计算 dp[2][5] 的时候，背包容量为 5，可以放下食物。所以基于水平继承，要放食物，但是放下食物之余还可以放水壶。水平继承不能考虑到这个问题。

基于以上，可以发现贪心算法解决这个问题的时候，存在两个问题：

忽略组合可能性
：这个方法会用食物“替换”水壶，但实际上3kg容量下最优解应该是
只选食物
，而 5kg 容量下最优解是
水壶+食物
的组合！
局部最优 ≠ 全局最优
：每次只考虑"当前最好的单个物品"，忽略了物品组合的情况。

在动态规划中，问题不是这样解的。

动态规划是垂直继承的。

为了更好地理解动态规划，需要先理解

继承

问题。

2.1 动态规划中的 “继承” 问题

我们选或者不选都是在考虑继承问题。

如果我们不选当前的物品：

继承上一行相同容量下的最大价值。

dp[i][w] = dp[i-1][w]

所以表格表现的位置是当前背包容量下，上一个物品的位置。

以 dp[3][2] 为例，物品为帐篷，背包容量为 2，背包容量不能放下当前的物品，所以继承上一个选择。

又以 dp[3][5]为例，物品为帐篷，背包容量为 5，背包容量可以放下当前的物品，但是当前物品的价值不如继承上一个选择的的价值，所以继承上一个选择。

如果我们选择当前的物品：

继承上一行

减去当前物品重量

的容量下的最大价值，

再加上当前物品的价值

dp[i][w] = dp[i-1][w - weight[i]] + value[i]

以dp[4][8] 为例，物品为睡袋，背包容量为 8，背包容量可以放下当前物品，所以进行决策：

考虑不选睡袋：继承dp[3][8] 即 dp[4][8] = 17
考虑选睡袋：
1. 睡袋占用 5kg 空间，剩余容量 = 8 - 5 = 3kg，需要注意的是，这个 3kg 是过去已经查出来了的，因为最开始是从 0 开始算的，所以这个数一定存在。
  
  初学者卡在这里：我们上一个背包容量获得了一个最优解，那为什么要从当前背包容量要减去当前物品的重量？
  
  我们捋一下：
  
  首先是有背包容量我们才能放物品；
  
  其次，由于我们是从 0 开始计算的，
  
  所以可以得出，结论一：当前背包容量以前的任何背包容量都是有最优解的；
  
  因为我们要放入一个物品，
  
  所以要从当前背包容量减去当前物品的重量，获得一个在放入这个新的物品之前能够占用的重量。
  
  但是由于结论一，我们可以保证获得的这个数仍然是最优解。再次说明：这个数字是
  不加
  新物品的最优解，并且有空间放入新物品。
  
  所以现在放入新的物品，检查新的价值是不是比之前更优，如果是就放入，如果不是就不放，保留上一步的解。
2. 查找 dp[3][3] = 8（前 3 个装备在 3kg 容量下的最优值），找出来之后我们加上当前物品的价值就可以了。
3. 总价值 = 8 + 10 = 18
选择更优方案：max(17, 18) = 18

你能发现，实际上动态规划特殊性在于不关心具体的组合内容，我们只需要知道最优解是多少。

或者说，无论怎么选择，要么是考虑上一次的解（价值）dp[i][w] = dp[i-1][w]，要么是之前某个特定位置的解（价值）加上现在的价值作为解 dp[i][w] = dp[i-1][w - weight[i]] + value[i]。

在之前那个特定的位置，包含了以下信息：

这个位置的解是考虑所有组合，而不在乎具体的选择。
这个位置不包含新的物品

在动态规划填表过程中，每个格子 dp[i][w] 的值都不是凭空产生的，而是从之前计算的格子"继承"而来。这种继承有两种形式：

2.1.1

垂直继承

（直接继承）

来源
: dp[i-1][w] → dp[i][w]
含义
: 在相同容量下，不选择当前物品i，直接继承前面的最优解
位置关系
: 正上方的格子
决策
: "我不要第i个物品，保持原来的最优解"

2.1.2

斜向继承

（选择继承）

来源
: dp[i-1][w-weight[i]] → dp[i][w]
含义
: 选择当前物品i，从"减去物品重量后的容量"的最优解继承
位置关系
: 左上方向的格子（向左移动weight[i]个位置）
决策
: "我要第i个物品，从能装下它的最优状态继承"

2.1.3

继承的选择机制

每个格子都面临一个选择：

dp[i][w] = max( dp[i-1][w], // 垂直继承（不选） dp[i-1][w-weight[i]] + value[i] // 斜向继承（选择） )

2.1.4 为什么叫“继承”？

状态延续
: 每个格子都建立在前面格子的基础上
最优性保持
: 继承的都是子问题的最优解
无后效性
: 一旦确定继承关系，不会被后续决策影响

2.1.5 “继承”与状态转移？

在这里我用继承来帮助理解，实际上上面的描述完全是状态转移的过程。

动态规划里说的“状态转移”是

用已算出的较小子问题的最优值，按照公式推出更大子问题的最优值

。
形象地说：

把 dp[i] 看成一张小纸条，上面记着 “到 i 为止的最优结果”；

dp[i+1] 这张新纸条，只是把之前若干张小纸条上的数拿来

加一加、比一比

后写上去——这就是

状态转移

，

2.2 最优性原理（贝尔曼原理 Bellman Principle of Optimality）

动态规划基于贝尔曼原理（最优性原理）：

一个整体最优的决策序列，它的
任何一段子序列
也必须是对应子问题的最优决策。简单来说就是“
一个问题的最优解包含其子问题的最优解
”

比如从北京到上海开车最快路线 = 北京 → 济南 → 南京 → 上海，那么其中的

北京 → 济南

这一段，

必须是“北京到济南”这一子问题的最快路线

；

是否可能存在另一条更短的北京 → 济南路线呢？

答案是不存在，如果存在，它就与“整体最快”矛盾。

其核心是：

把大问题拆成
重叠子问题
（Overlapping Subproblems）。
利用子问题的最优解
递推
或
记忆化
得到原问题最优解。
这正是动态规划（DP）的理论基石：只要满足“最优子结构 + 无后效性”，就能用贝尔曼原理写出状态转移方程。

这保证了：

当我们计算dp[i][w]时，所依赖的dp[i-1][...]都已经是最优解
不管这些子问题对应什么具体的物品组合，它们都是最优的
因此基于它们计算出的 dp[i][w] 也必然是最优的

四、详细填表过程

初始化DP表格

装备\容量	0	1	2	3	4	5	6	7	8	9	10
0(无装备)	0	0	0	0	0	0	0	0	0	0	0

第1行：只考虑水壶(2kg, 6元)

对于每个容量位置，判断是否能装下水壶：

容量0-1kg：装不下 → 价值0
容量2-10kg：能装下 → 价值6

装备\容量	0	1	2	3	4	5	6	7	8	9	10
0(无装备)	0	0	0	0	0	0	0	0	0	0	0
1(水壶)	0	0	6	6	6	6	6	6	6	6	6

第2行：考虑水壶+食物(3kg, 8元)

关键决策点分析：

`dp[2][3]`：容量3kg

不选食物：
dp[1][3] = 6元（只选水壶）
选食物：
dp[1][3-3] + 8 = dp[1][0] + 8 = 0 + 8 = 8 元
结论：
dp[2][3] = max(6, 8) = 8元（选食物更好）

`dp[2][5]`：容量5kg

不选食物：
dp[1][5] = 6元
选食物：
dp[1][5-3] + 8 = dp[1][2] + 8 = 6 + 8 = 14 元
结论：
dp[2][5] = max(6, 14) = 14 元（水壶+食物组合）

继续填充第2行：

装备\容量	2	3	4	5	6	7	8	9	10
0(无装备)	0	0	0	0	0	0	0	0	0
1(水壶)	6	6	6	6	6	6	6	6	6
2(+食物)	6	8	8	14	14	14	14	14	14

第3行：考虑水壶+食物+帐篷(4kg, 9元)

`dp[3][4]`：容量4kg

不选帐篷：
dp[2][4] = 8 元
选帐篷：
dp[2][4-4] + 9 = dp[2][0] + 9 = 0 + 9 = 9 元
结论：
dp[3][4] = max(8, 9) = 9 元（只选帐篷）

`dp[3][7]`：容量7kg

不选帐篷：
dp[2][7] = 14 元（水壶+食物）
选帐篷：
dp[2][7-4] + 9 = dp[2][3] + 9 = 8 + 9 = 17 元
结论：
dp[3][7] = max(14, 17) = 17 元（食物+帐篷）

`dp[3][9]`：容量9kg

不选帐篷：
dp[2][9] = 14元
选帐篷：
dp[2][9-4] + 9 = dp[2][5] + 9 = 14 + 9 = 23 元
结论：
dp[3][9] = max(14, 23) = 23 元（水壶+食物+帐篷）

装备\容量	2	3	4	5	6	7	8	9	10
0(无装备)	0	0	0	0	0	0	0	0	0
1(水壶)	6	6	6	6	6	6	6	6	6
2(+食物)	6	8	8	14	14	14	14	14	14
3(+帐篷)	6	8	9	14	15	17	17	23	23

第4行：考虑所有装备+睡袋(5kg, 10元)

`dp[4][5]`：容量5kg

不选睡袋：
dp[3][5] = 14 元
选睡袋：
dp[3][5-5] + 10 = dp[3][0] + 10 = 0 + 10 = 10 元
结论：
dp[4][5] = max(14, 10) = 14 元

`dp[4][7]`：容量7kg

不选睡袋：
dp[3][7] = 17 元（食物+帐篷）
选睡袋：
dp[3][7-5] + 10 = dp[3][2] + 10 = 6 + 10 = 16 元
结论：
dp[4][7] = max(17, 16) = 17 元

`dp[4][10]`：容量10kg（最终答案！）

不选睡袋：
dp[3][10] = 23元（水壶+食物+帐篷）
选睡袋：
dp[3][10-5] + 10 = dp[3][5] + 10 = 14 + 10 = 24 元
结论：
dp[4][10] = max(23, 24) = 24 元

最终DP表格

装备\容量	2	3	4	5	6	7	8	9	10
0(无装备)	0	0	0	0	0	0	0	0	0
1(水壶)	6	6	6	6	6	6	6	6	6
2(+食物)	6	8	8	14	14	14	14	14	14
3(+帐篷)	6	8	9	14	15	17	17	23	23
4(+睡袋)	6	8	9	14	16	17	18	23	24

🔙 回溯找出具体方案

从 dp[4][10] = 24开始回溯：

graph TB A["dp[4][10] = 24"] --> B{"24 == dp[3][10]?"} B -->|否: 24≠23| C[选了睡袋] C --> D[剩余容量: 10-5=5kg] D --> E["dp[3][5] = 14"] --> F{"14 == dp[2][5]?"} F -->|是: 14==14| G[没选帐篷] G --> H["dp[2][5] = 14"] --> I{"14 == dp[1][5]?"} I -->|否: 14≠6| J[选了食物] J --> K["剩余容量: 5-3=2kg"] K --> L["dp[1][2] = 6"] --> M{"6 == dp[0][2]?"} M -->|否: 6≠0| N[选了水壶] N --> O["最优方案: 水壶+食物+睡袋"]

最优解：

选择装备：水壶(2kg,6元) + 食物(3kg,8元) + 睡袋(5kg,10元)
总重量：2 + 3 + 5 = 10kg（正好装满）
总价值：6 + 8 + 10 = 24 元

五、算法复杂度分析

graph TD A[算法复杂度] --> B["时间复杂度: O(n×W)"] A --> C["空间复杂度: O(n×W)"] B --> D["n=4, W=10 → 40次计算"] C --> E["可优化为O(W)滚动数组"] F[对比其他方法] --> G["暴力穷举: O(2^n)"] F --> H["贪心算法: O(n log n)"] G --> I["n=4时: 16种组合"] G --> J["n=20时: 100万种组合"] H --> K["但不能保证最优解"]

空间优化：

由于 dp[i] 只依赖 dp[i-1]，可以压缩为一维数组：

for i in range(n): for w in range(W, weight[i]-1, -1): # 倒序遍历 dp[w] = max(dp[w], dp[w-weight[i]] + value[i])

六、实际应用场景

应用领域

mindmap root((01背包应用)) 资源配置投资组合优化项目预算分配人员任务分配工程优化货物装载问题存储空间分配网络带宽分配游戏AI 装备选择策略技能点分配道具组合优化机器学习特征选择模型压缩样本选择

具体案例

案例1：投资组合优化

背包容量：总投资金额
物品：各种投资项目
重量：每个项目的投资金额
价值：预期收益

案例2：云服务器资源分配

背包容量：总计算资源
物品：不同的计算任务
重量：任务所需资源
价值：任务的重要程度

🧮 算法扩展

背包问题家族

graph TD A[背包问题] --> B[01背包] A --> C[完全背包] A --> D[多重背包] A --> E[分组背包] B --> F[每个物品选0或1次] C --> G[每个物品可选无限次] D --> H[每个物品有数量限制] E --> I[物品分组，每组只能选一个] J[高级变种] --> K[二维背包] J --> L[依赖背包] J --> M[泛化物品] K --> N[重量+体积两个约束] L --> O[物品间有依赖关系] M --> P[物品可以是其他背包问题]