Answer 1

三、动态规划

背包问题

首先我们从背包问题开始。

一个背包可以装4kg的物品，现有物品音响（3000元|4kg）笔记本电脑（2000元|3kg）、吉他（1500元|1kg），那么我们怎么拿可以使物品价值最高？

1、 最简单的方法：罗列所有组合，选取符合条件的最高的那个。

物品是1个的时候，我们可以拿或不拿，即2种选择；物品3个的时候，我们有8种选择；物品n种时，我们有 2^n 种选择——时间复杂度 O(2^n)!

2、动态规划

动态规划的核心在于合并两个子问题的解来得到更大问题的解。

那么它的难度就在于怎么把大问题分解成子问题。

在这里的例子里，装入背包的物品价值取决于物品类型和背包容量两个因素，以这两个因素为维度，利用网格来得到问题的解（本质上是当容量更小、物品更少时更容易得到解）。

• 当只有一个物品时，随容量增加，很轻松可以得到容量对应的最大价值（这里作为第一行开始）。
• 当增加物品时（即下一行），那么每个格子的值将由上一行对应格子的值和当前物品价值来决定：
  • 增加物品，价值只可能增长，所以最小值是上一行对应格子的值；
  • 如果当前格子的容量可以放下当前物品，那么可能的最大值是当前物品的价值 + 上一行对应剩余容量格子的值。