零基础学习算法：动态规划-01背包问题

1. 原题

假定现有物品：

名称重量价值1. 苹果1152. 香蕉3203. 西瓜430

背包容量为 4 ，求背包能装的最大价值。

2. 牺牲空间换时间的动态规划

1. 想要求解01背包，我们可以先建立一个二维表

容量0容量1容量2容量3容量4考虑前0个考虑前1个考虑前2个考虑前3个

所谓容量x：指该容量下的背包（例如：容量3->指背包容量为3的背包） 所谓考虑前x个：指仅仅考虑该位次以及该位次前的所有物体（例如：考虑前2个->指仅考虑 1. 苹果 2. 香蕉 而不考虑 3. 西瓜）

问：为什么要这样建立一个二维表？ 答：这正是动态规划的精髓所在，牺牲空间换时间。你可以这样理解：我们想要求的是表格右下角的容量5，考虑前3个的格子。 而之前建立的所有表单，都像是为了这一格子做的经验积累，通过以前的经验，得到该情况下的最好结果。

2. 填0

容量0容量1容量2容量3容量4考虑前0个00000考虑前1个0考虑前2个0考虑前3个0

第一步，我们可以很轻松的得出一个结论：没有容量的背包装不下任何东西，没有东西要装再大的背包也没有意义。 因此我们可以将第一行和第一列置为0

3. 填写第二行表单 我们先来填写 容量1 考虑前1个（苹果） 的情况： 物品1（苹果） 的重量为1，那么它当然可以装到容量为1的背包里，因此这个时候背包的最大价值为15（装入苹果）

新表：

容量0容量1容量2容量3容量4考虑前0个00000考虑前1个015考虑前2个0考虑前3个0

而在之后，我们很容易发现：仅考虑 物品1（苹果） 时，再大的背包也没有意义了，因为只有1个 物品1（苹果） 可装，再大的背包也只是1个价值15的物品1（苹果）

新表：

容量0容量1容量2容量3容量4考虑前0个00000考虑前1个015151515考虑前2个0考虑前3个0

3. 填写第三行表单

我们先来填写 容量1 考虑前2个（苹果，香蕉） 的情况： 物品1（苹果） 的重量为1，物品2（香蕉） 的重量为3，那么至少要有3格大的背包才能装入这么大的香蕉，因此我们明白：容量1，容量2的背包最大价值依旧是15

新表：

容量0容量1容量2容量3容量4考虑前0个00000考虑前1个015151515考虑前2个01515考虑前3个0

接下来，有趣的事情发生了： 当背包变成3格大的时候，新的物品 物品2（香蕉） 已经可以被装入背包了，这时候我们有两个选择： a. 不装入香蕉 b. 装入香蕉 我们先来看不装入香蕉的情况： 如果我们不装入香蕉，那么相当于该格子变成了：容量3 考虑前1个（苹果） 的背包，而这样的背包我们已经计算过了。没错，最大价值就是上方的15。 我们再来看装入香蕉的情况： 如果我们装入香蕉，那么该格子必须要腾出3格大的空间让我们放下物品2（香蕉）。这也意味着进行该行为之后，该格子的剩余空间变成了可怜的容量0。 这也相当于变成了：容量0 考虑前1个（苹果） 的背包 + 1个物品2（香蕉），而 容量0 考虑前1个（苹果） 这样的背包我们已经计算过了。没错，最大价值就是左上方的0。 那么该情况下最大价值变成了香蕉的20价值。 最后进行比较： 15