文章声明：转载来源：https://blog.csdn.net/chengqiuming/article/details/115310502

一 动态规划算法

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。

动态规划算法与分治算法类似。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。

动态规划可以通过填表的方式来逐步推进，得到最优解。

二 背包问题

背包问题可以通过动态规划算法来实现。

背包问题：

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

1 要求达到的目标为装入的背包的总价值最大，并且重量不超出。

2 要求装入的物品不能重复。

三 用填表法解决背包问题

说明

i：行坐标，代表物品。

j：列坐标，代表物品的容量。

v[i][j]：前 i 个物品中能够装入容量为j的背包中的最大价值。

装入顺序是从上到下，从左到右。

填表过程

1 可以分析出v[i][0]=v[0][j]=0，我们先把这些0填入上面的表格。用红色表示。

2 再考虑放吉他，因为它的容量是1磅，所以1磅，2磅，3磅，4磅的背包都可以将吉他放下，我们将吉他的价值填入。用绿色表示。

3 其次考虑放音响，因为它的容量是4磅，1磅，2磅，3磅的背包是放不下它的，所以它们对应的最大价值从上一行拷贝过来，我们用天蓝色表示。4磅的背包可以放下音响，放下音响后，就没剩余空间了，不能再放其它物品。因为它的价值3000大于吉他的价值1500，所以这里就放3000，我们依然用黑色表示。

4 最后我们考虑放电脑，因为它的容量是3磅，1磅，2磅的背包是放不下它的，它们对应的最大价值从上一行拷贝过来，我们用天蓝色表示。3磅的背包可以放下电脑，放下电脑后，就没剩余空间了，不能再放其它物品。因为它的价值2000大于吉他的价值1500，所以这里就放2000，我们依然用黑色表示。

5 4磅的背包可以放下电脑，放完电脑后，背包剩下的空间是1磅，1磅的空间最大可以放价值为1500的吉他，两个加起来是3500，大于上1行的3000，所以这里填写3500，我们用桔色表示。

 四 背包问题的思路

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。

其中又分01背包和完全背包。

完全背包：每种物品可以放多次。
01背包：每个物品最多放一个。

无限背包可以转化为01背包。

算法的主要思想

利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。

令v[i][j]表示在前 i 个物品中能够装入容量为j的背包中的最大价值。

可以推出下面的结论：

1 v[i][0]=v[0][j]=0;
表示填入表第一行和第一列是0。

2 当w[i] > j 时：v[i][j]=v[i-1][j]
该公式描述的是：当准备加入商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略。

3 当j >=w[i]时：v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
该公式描述的是：当准备加入的商品的容量小于等于当前背包的容量的装入的策略。

v[i-1][j]：就是上一个单元格的装入的最大值。

v[i]：表示当前要装入商品的价值。

v[i-1][j-w[i]] ：表示在前 i-1 个物品中能够装入容量为 j-w[i] 的背包中的最大价值。

五 点睛

第3步的填表法和第4步的3个公式相互印证，可以结合起来理解。