动态规划算法
一 动态规划算法
动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。
动态规划算法与分治算法类似。其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解。
动态规划可以通过填表的方式来逐步推进，得到最优解。
二 背包问题
背包问题可以通过动态规划算法来实现。
背包问题：
有一个背包，容量为4磅，现有如下物品。
1 要求达到的目标为装入的背包的总价值最大，并且重量不超出。
2 要求装入的物品不能重复。
三 用填表法解决背包问题
物品 | 0 磅 | 1 磅 | 2 磅 | 3 磅 | 4 磅 |
0 | 0 | 0 | 0 | 0 | |
吉他 (G) | 0 | 1500(G) | 1500(G) | 1500(G) | 1500(G) |
音响 (S) | 0 | 1500(G) | 1500(G) | 1500(G) | 3000(S) |
电脑 (L) | 0 | 1500(G) | 1500(G) | 2000(L) | 3500(L+G) |
说明
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个公式相互印证，可以结合起来理解。
深藏阁楼爱情的钟
浅浅的花香味﹌
爱被打了一巴掌
怼烎@
╰+哭是因爲堅強的太久メ
还没有评论，来说两句吧...