1、应用场景-背包问题

背包问题：有一个背包，容量为4磅 ， 现有如下物品

https://img-blog.csdnimg.cn/50c7c891b02d4b159715ec4da1b0ce47.png

  1. 要求达到的目标为装入的背包的总价值最大，并且重量不超出
  2. 要求装入的物品不能重复

2、动态规划算法介绍

  1. 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
  2. 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
  3. 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
  4. 动态规划可以通过填表的方式来逐步推进，得到最优解.

3、动态规划算法最佳实践-背包问题

背包问题：有一个背包，容量为4磅 ， 现有如下物品

https://img-blog.csdnimg.cn/7adfe084093447adab98a80ce0b83f9b.png

要求达到的目标为装入的背包的

总价值最大，并且重量不超出。

解决类似的问题可以分解成一个个的小问题进行解决，假设存在背包容量大小分为1，2，3，4的各种容量的背包(分配容量的规则为最小重量的整数倍)：

例如:

https://img-blog.csdnimg.cn/af93f34e90da434ab0f2d95e586b2341.png

对于第一行(i=1), 目前只有吉他可以选择，所以

https://img-blog.csdnimg.cn/ed1a0d6440454b9eae01a3c476fdd48c.png