在上篇博客中，我们讲了动态规划法在最长公共子序列问题中的应用，（详情请见博客《算法：动态规划法--最长公共子序列》）。这次学习了0-1背包问题，对动态规划法的思想理解了更深了一层，以下是我的简单理解，希望能为路过的读者带来帮助。
第一，动态规划法思想
1、简单了解分治法和贪心法
分治，分治，分而治之。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。贪心法，基本思想是整体最优解可以通过一系列局部最优得到，所以只需得到局部最优解，每一步都只考虑一个数据，所以不一定是整体最优。
2、三法相比，理解动态规划法
贪心法的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。
而用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级。如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思想
第二，动态规划法求解0-1背包问题
***************************************问题描述********************************************
有n个物品，第i个物品价值为vi，重量为wi，其中vi和wi均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。该问题以形式化描述如下：
目标函数为 ：
约束条件为：
满足约束条件的任一集合（x1，x2，...，xn）是问题的一个可行解，问题的目标是要求问题的一个最优解。考虑一个实例，假设n=5，W=17， 每个物品的价值和重量如表9-1所示。可将物品1，2和5装入背包，背包未满，获得价值22，此时问题解为（1，1，0，0，1）。也可以将物品4和5装入背包，背包装满，获得价值24，此时解为（0，0，0，1，1）。
*********************************动态规划法求解过程*****************************************
1、刻画最优解结构
背包求解过程可看做进行一系列决策的过程，即决定哪些物品应该放入背包，哪些不放入。不能物品i装入多次，也不能只装入物品的一部分。如果一个问题的最优解包含了物品n，Xn=1,那么，其他X1，X2…Xn-1一定构成子问题1,2,3…n-1在容量为W-wn时的最优解。如果不包含物品n，Xn=0,那么，其他X1，X2…Xn-1一定构成子问题1,2,3…n-1在容量为W时的最优解，即在此容量下，不放这个物品。
2、递归定义最优解的值
设c[I,w]表示背包容量为w时放i个物品得到的最优解的总价值。显然，我们是要求解c[n,w]。（这里注意，不是第i个物品，是背包里存在i个物品）
3、计算背包问题最优解的值。
（为了让软考的小朋友更好的理解，此代码复制自《软件设计师教程》第4版复制）
C语言代码：
int** KnapsackDP(int n,int W,int* Weights,float* Values) { int i, w ； / * 为 二 维 数 组 申 请 空 间 * / int** c = (int **)malloc(sizeof(int * ） *(n + l)); for (i = 0 ； i < = n; i++) c[i]= (int *)malloc(sizeof(int)*(W + l)); / * 初 始 化 二 维 数 组 * / For(w=0;w <W;w++) c[0][w] = 0； //i=0的一行值全为0； for(i=1;i<= n;i++) { //i在外循环，在i一定时，随着背包容量增加，是否放该物品 c[i][0] = 0； //w=0的一整列全为0； for(w = 1 ;w < = W;w++) { if(Weights[i-1] < = w) { / * 如 果 背 包 剩 余 重 量 大 于 物 品 重 量 if(Values[i-1]+c[i-1][w-Weights[i-1]]>c[i-1][w]) { /* 重 量 为 w 的 背 包 中有 该 物 品 * / c[i][w] = Values[i-1] + c[i-1][w -Weights[i-1]]; } else{ /*重 量 为 w 的 背 包 中没有 该 物 品 * / c[i][w] = c[i-1][w]; } } Else c[i][w] =c[i-1][w]; } } Return c ; }
时间复杂度：O(nW)
得到记录表格：
4、根据计算结果构造问题最优解
Void OutPutKnapsackDP(int n,int w,int *Weights,float *values,int**c) { Int x[n] ； int 1 ； For (i=n;j>1;i--) { if(c[i][w]==c[i-1][w]) / * 重 量 为 w 的 最 优 选 择 的 背 包 中 不 包 含 该 物 品 */ x[i-1] = 0 ； Else{ x[i-1] = 1 ； W =W-Weightst[i-1]; / * 更 新 背 包 目 前 的 最 大 容 量 * / } } if(c[1][W]=0） / * 第 一 个 物 品 不 在 背 包 * / x[0] =0； else / *第 一 个 物 品在背 包中* / x[0] =1； For(i=0;i<n;i++) if(x[i]==1) printf("Weight:%d,Value:%f\n",Weights[i],Values[i]); }
时间复杂度是：O（n）
注：
在C语言中
%d,用来输出十进制整数
%f,用来输出实数（包括单，双精度），以小数形式输出
****************************************举例说明********************************************
当背包容量为8（w=8），可以放2个物品时（i=2），背包的最大价值是多少？
1、判断背包的容量是否可以容下此物品：
Weights[i-1] =Weights[1]=4，（因为数组的下标从0开始，所以这里指第二个物品的重量是4），4<8,第二个物品可以放入背包。
2、根据价值，判断是否将此物品放入背包
假设此物品已经放入背包，那么根据刻画的最优结构“如果一个问题的最优解包含了物品n，Xn=1,那么，其他X1，X2…Xn-1一定构成子问题1,2,3…n-1在容量为W-wn时的最优解。”计算价值
Values[i-1]+c[i-1][w-Weights[i-1]]=Values[1]+c[1][4]=9
即，第二个物品的价值5+背包容量位（8-4）时，放两个物品时的价值（此情况在之前已经计算出，c[1][4]=4）
第三，总结
在什么情况下可以使用动态规划法？1、有最优子结构：一个问题有很多解，每个解对应一个值，我们希望找到最优解；2、重叠子问题：每个子问题之间不是相互独立的，求解第二个问题，可能用到第一个问题的解。
结合最长公共子序列问题和0-1背包问题，适合动态规划法求解的问题，经分解得到的子问题保存已解决的子问题的答案，在需要时再找出已求得的答案，这样可以避免大量的重复计算，从而得到多项式时间的算法。
