01背包（所有物品不可再分，要么整个装入背包，要么放弃，不允许出现仅选择物品的一半装入背包的情况）是属于动态规划算法的一个体现。
商店中拥有 5 件商品，它们各自的重量和收益分别是：
- 商品 1：重量 1 公斤，收益 1 元；
- 商品 2：重量 2 公斤，收益 6 元；
- 商品 3：重量 5 公斤，收益 17 元；
- 商品 4：重量 6 公斤，收益 20 元；
- 商品 5：重量 8 公斤，收益 26 元。
你只能装11公斤物品，求利益最大化
填入的值按照这个公式来填 f [ i , j ] :f [ i -1, j ] > v [ i ] + j - w [ i ]
这句话用人话来说就是：当你需要填入这个值的时候需要（当前商品的价值加上背包剩余的价值）和 （上一个背包的价值来做比较）
背包剩余的价值：指如果放入这个商品，剩余的空间还能放些什么东西。
画表格来表示
| 商品种类 | 背包承重 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| w1 = 1，v1 = 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| w2 = 2，v2 = 6 | ||||||||||||
| w3 = 5，v3 = 17 | ||||||||||||
| w4 = 6，v4 = 20 | ||||||||||||
| w5 = 8，v5 = 26 | ||||||||||||
| 种类 | 背包承重 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| w1 = 1，v1 = 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| w2 = 2，v2 = 6 | 0 | 1 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| w3 = 5，v3 = 17 | ||||||||||||
| w4 = 6，v4 = 20 | ||||||||||||
| w5 = 8，v5 = 26 | ||||||||||||
| 种类 | 背包承重 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| w1 = 1，v1 = 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| w2 = 2，v2 = 6 | 0 | 1 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| w3 = 5，v3 = 17 | 0 | 1 | 6 | 7 | 7 | 17 | 18 | 23 | 24 | 24 | 24 | 24 |
| w4 = 6，v4 = 20 | ||||||||||||
| w5 = 8，v5 = 26 | ||||||||||||
| 种类 | 背包承重 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| w1 = 1，v1 = 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| w2 = 2，v2 = 6 | 0 | 1 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| w3 = 5，v3 = 17 | 0 | 1 | 6 | 7 | 7 | 17 | 18 | 23 | 24 | 24 | 24 | 24 |
| w4 = 6，v4 = 20 | 0 | 1 | 6 | 7 | 7 | 17 | 20 | 23 | 26 | 27 | 27 | 37 |
| w5 = 8，v5 = 26 | ||||||||||||
这里的23就是最优解：带入公式查看
f [ i , j ] :f [ i -1, j ] > v [ i ] + j - w [ i ]
f [ 4 , 7 ] = f [ 3 , 7 ] > v [ 4 ] +（ 7 - w [ 4 ] ）
= 23 > 20 + 1
原本这里放入的是21但他不是最优解，动态规划的思想是，上一个永远是上一个问题的最优解
| 种类 | 背包承重 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
| w1 = 1，v1 = 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| w2 = 2，v2 = 6 | 0 | 1 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
| w3 = 5，v3 = 17 | 0 | 1 | 6 | 7 | 7 | 17 | 18 | 23 | 24 | 24 | 24 | 24 |
| w4 = 6，v4 = 20 | 0 | 1 | 6 | 7 | 7 | 17 | 20 | 23 | 26 | 27 | 27 | 37 |
| w5 = 8，v5 = 25 | 0 | 1 | 6 | 7 | 7 | 17 | 20 | 23 | 26 | 27 | 31 | 37 |
26，27，37同上面一样
所以该背包的最大价值是37 由商品 3 和 商品 4 组成
版权声明：本文为weixin_51722520原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。