算法图解 动态规划
🏷️ 《算法图解》
背包问题
假设你是一个小偷，背着一个可装 4 磅东西的背包。
- 音响 3000 美元 4 磅
- 笔记本电脑 2000 美元 3 磅
- 吉他 1500 美元 1 磅
简单算法
列出所有可能的组合，并找出价格最高的组合。
这样可行，但是速度非常慢。算法的运行时间为
动态规划
使用动态规划找出最优解。
每个动态规划都从一个网格开始。
| 1 磅 | 2 磅 | 3 磅 | 4 磅 | |
|---|---|---|---|---|
| 吉他 | ||||
| 音响 | ||||
| 笔记本电脑 |
1. 吉他行
第一行是假设只有吉他可以偷的情况，最大金额为 $1500。
| 1 磅 | 2 磅 | 3 磅 | 4 磅 | |
|---|---|---|---|---|
| 吉他 | $1500 | $1500 | $1500 | $1500 |
| 音响 | ||||
| 笔记本电脑 |
2. 音响行
背包为 4 磅时，可以放入音响，最大金额更新为$3000。
| 1 磅 | 2 磅 | 3 磅 | 4 磅 | |
|---|---|---|---|---|
| 吉他 | $1500 | $1500 | $1500 | $1500 |
| 音响 | $1500 | $1500 | $1500 | $3000 |
| 笔记本电脑 |
3. 笔记本电脑行
1-2 磅时最大金额仍为 $1500。
| 1 磅 | 2 磅 | 3 磅 | 4 磅 | |
|---|---|---|---|---|
| 吉他 | $1500 | $1500 | $1500 | $1500 |
| 音响 | $1500 | $1500 | $1500 | $3000 |
| 笔记本电脑 | $1500 | $1500 |
3 磅时可以选择偷笔记本电脑，最大金额为 $2000。
| 1 磅 | 2 磅 | 3 磅 | 4 磅 | |
|---|---|---|---|---|
| 吉他 | $1500 | $1500 | $1500 | $1500 |
| 音响 | $1500 | $1500 | $1500 | $3000 |
| 笔记本电脑 | $1500 | $1500 | $2000 |
4 磅时的计算非常重要。这是可以选择偷音响，或者偷笔记本电脑之后还剩余 1 磅。而剩余 1 磅的最大金额已经计算过了，是$1500。
$3000 vs $2000 + $1500
| 1 磅 | 2 磅 | 3 磅 | 4 磅 | |
|---|---|---|---|---|
| 吉他 | $1500 | $1500 | $1500 | $1500 |
| 音响 | $1500 | $1500 | $1500 | $3000 |
| 笔记本电脑 | $1500 | $1500 | $2000 | $3500 |
你可能认为计算最后一个单元格的价值时，使用了不同的公式。但其实计算每个单元格的价值时，使用的公式都相同。
公式
CELL[i][j] = max(上一个单元格的值（即 CELL[i-1][j]的值），当前商品的价值 + 剩余空间的价值 (即 CELL[i-1][j-当前商品的重量]))
再增加一个商品时，只要依次往下加行即可。
小结
需要在给定约束条件下优化某种指标时，动态规划很有用
问题可分解为离散子问题时，可使用动态规划来解决
每种动态规划解决方案都涉及网格
单元格中的值通常就是你要优化的值
每个单元格都是一个子问题，因为你需要考虑如何将问题分解为子问题
没有放之四海皆准的计算动态规划解决方案的公式