动态规划算法
动态规划方法是对解最优问题的一种方法，一种途径，并不是一种特殊的算法。执行步骤：1. 找出最优解的性质，刻画结构特征2. 递归定义最优解3. 自底向上方式计算出最优解4. 根据计算最优值时得到的信息，构造一个最优解总结为2点，建立最优子结构，保证每一个子结构都是最优解；然后重叠子问题，而不是重复子问题，最优解都是建立在最优子结构的基础之上的。下面对动态规划的经典问题进行分析：
【0-1背包问题】
问题描述：有N件物品和一个容量为V的背包。第i件物品的重量是w\[i-1\]，价值是v\[i-1\]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。理解：0-1是指每个物体都有唯一编号，要么放入背包，要么不放。（区别于物品无限背包问题）现在指n=5，W=17，物品的价值和重量：![SouthEast][]**（1）递归定义最优解的值：**![20151005215519594][]理解：（1）物品的下标是从1开始的，当下标为0时，获得的价值为0；包内放入的物品重量为0，则获得价值也为0.（2）第i个物品不能放入包内时，最优解为前一不放该物品最优解c\[i-1\]\[w\];（3）第i个物品能放入时，有两种情况：第i个物品的价值values（i-1）+剩余空间最优解c\[i-1\]\[w-Weights\[i-1\]\]；不放入第i个物品之前的最优解c\[i-1\]\[w\]**（2）算法实现图解**1> 判断编号为i的物品能否放入到允许重量w中。例如：c\[3\]\[7\]这个位置，物品3的重量为7，能放入到w=7的包内。
2> 比较将3放入包内（10）+剩余控件最优解（c\[2\]\[7-7\]=0）与不放入3的最优解（c\[2\]\[7\]=9）的大小，前者得到的价值大，为最终最优解 ，因此c\[3\]\[7\]=10
（3）c语言代码最优解实现int ** KnapsackDP(int n,int W,int* Weights,float* Values){ //n：物品个数；W：允许最大数量；Weights：每个物品重量数组；Values：每个物品价值数组int i,w; //i:指定第几个物品；w：允许重量int** c=(int**)malloc(sizeof(int*)*(n+1)); //分配空间for(n=0;i<=n;i++) //每一个物品分配W+1种空间存放0--W种不同情况下最优解c[j]=(int*)malloc(sizeof(int)*(W+1));for(w=0;w<W;w++) //第一行赋值为0（没有物品的情况）c[0][w]=0;for(i=1;i<=n;i++) //n个物品的循环c[i][0]=0; //第一列赋值为0（包内允许的重量为0）for(w=1;w<=W;w++) //w记录每一种重量的下标if(Weights[i-1]<=w){ //i物品能否放入容量为w的包内if(Values[i-1]+c[i-1][w-Weights[i-1]]>c[i-1][w]) //比较将i放入包内+剩余控件最优解与不放入i的最优解的大小{c[i][w]=Values[i-1]+c[i-1][w-Weights[i-1]]; //将i放入包内+剩余控件最优解为最优解}else{c[i][w]=c[i-1][w]; //不放入i的最优解为最优解}}else{c[i][w]=c[i-1][w]; //不放入i的最优解为最优解}}return c;}该代码实现上表的横向插入，插完第i行然后插入第i+1行。
【总结】
在问题相对复杂的情况下，代码不能马上理解，这时候我们可以先根据自己的理解对问题的图进行理解，根据自己的理解试试能否理解代码，如果出现差错，可以将例题数据带入代码进行运算，可以理解代码的相对流程，然后再思考代码的整体框架实现。
深藏阁楼爱情的钟
浅浅的花香味﹌
爱被打了一巴掌
怼烎@
╰+哭是因爲堅強的太久メ
还没有评论，来说两句吧...