算法之动态规划法
浏览数：56 /
时间：2015年06月08日
动态规划算法其实就是一种优化的算法，其基本思想就是将待求解的问题分解成若干子问题，先求解子问题（这些解不是独立的），然互从这些子问题中得到原问题的解。其最终得到的结果往往是最优解。和贪心法不同的是，动态规划法不可以将一个整体进行分割。
举个简单的例子：给出7个数，1,2.....7，从中选出不超过3个使得这3个数的和不超过20.求解时我们应该一步一步进行：
1、先给一个数，然后对7个数进行遍历，找到最大的，为7
2、在找两个数，求其最大和，在和步骤一的最大值进行比较，看看谁大就取哪一个为最大值，在循环遍历找到最大值
3、在找三个数，和步骤二是一样的，最终求得最大值。
其实动态规划法也是这样一个步骤，将其抽象整理为：
1、找出最优解的性质，并刻画其结构特征
2、递归的定义最优解的值
3、以自底向上的方式计算出最优解
4、根据计算最优值时得到的信息，构造一个最优解。
在这有一个问题，为什么求两个数的和最大值和第一个数的最大值进行比较，在这还以背包问题为例，在个数n=5，重量W=17时，求重量不超过W的最大价值，表如下：
在这取n=3时其最大价值为前三个物品的和为19；
当n=4时，说明其可以放进去，故第四个物品的价值为v，而剩下背包最大重量为17-8=9，即在重量不超过9的时候前三个物品放到背包的最大价值为取第三个物品的价值10，所以当n=4时其价值为10+v
最后在进行比较：（10+v）和19哪一个价值大，我们可以知道v是第四个物品的价值，故其最后取值应和v的大小有直接关系，当v>=9时，则最大价值为10+v，反之则为19.正好解释下面这个式子：
总结：动态规划法其本质是变量从小到大不断变化，循环，在一次一次的比较过程中找到那个最优解。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
