算法分析与设计算法（动态规划算法以及求解0-1背包问题）
算法分析与设计算法（动态规划算法以及求解0-1背包问题）4、根据计算最优值得到的信息，构造一个最优解3、自底向上的方式计算出最优值 动态规划算法通常用于求解具有某种最优性质的问题。这类问题中，可能会有许多可行的解，每个解对应个值，我们希望找到最大值或者最小值的那个解，其步骤如下：1、找出最优值的性质，并分析其结构特征2、递归定义最优解的值
一、动态规划法的设计思想
动态规划法是数学--"运筹学"中一个决策分析的实现，广泛运用在计算机算法、企业决策、市场营销等领域。
动态规划法是将待求解的问题分成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经过分解的子问题往往不是独立的。若用分治法求解这类问题，则相同的子问题会被求解多次，以至于最后解决问题需要消耗指数级别的时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已经解决的子问题的答案，在需要时再找出已经求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以使用个表来记录已经解决子问题的答案，不管子问题以后是否被用到，只要它计算过，就将其结果填入表中，这就是动态规划法的基本思路。
动态规划算法通常用于求解具有某种最优性质的问题。这类问题中，可能会有许多可行的解，每个解对应个值，我们希望找到最大值或者最小值的那个解，其步骤如下：
1、找出最优值的性质，并分析其结构特征
2、递归定义最优解的值
3、自底向上的方式计算出最优值
4、根据计算最优值得到的信息，构造一个最优解
步骤1—2是基本步骤，在只需求出最优值的情况下步骤4可以省略。若需要求子问题的最优解，则必须执行步骤4，此时在步骤3中计算最优值时，通常记录等多的信息，以便在步骤4中根据所记录的信息快速构造出一个最优解
动态规划算法是非常有效的算法技术，那么什么时候使用它呢？或者说其运用场景是什么？若求解问题具有一下性质，可以考虑使用动态规划法：
1、最优子结构：如果一个问题的最优解中包含其子问题的最优解，就是说该问题具有最优子结构。这时候贪婪算法可能也使用求解此类问题
2、重叠子问题：重叠子问题是指用来求解问题的递归算法可以反复的解同样的问题，而不是总在产生新的问题，即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题，此时若使用分治法递归求解时，则每次遇到子问题都会视为新问题，会极大降低效率，而动态规划法对每个子问题仅计算一次，把解保存到在一个需要时就可以查看的表中
二、动态规划法案例：0-1背包问题
有n个物品，第i个物品的价值为 Vi，重量为Wi，其中Vi和Wi均为非负数，背包容量为W，W为非负数。现考虑如何选择装入背包的物品，使装入背包的物品总价值最大。假设商品有5件，n=5，容量为17，W=17
要装入的物品及其价值如下表所示：
（一）、求解思路
1、使用矩阵规划出最优解
把求解过程看作是一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包
（1）如果一个问题的最优解包含了物品n，即Xn=1，那么其余的X1 X2 ….Xn-1一定构成子问题1 2 ……n-1在容量为W-wn时的最优解
（2）如果这个最优解不包含物品n，即Xn=0，那么其余X1 X2…. Xn-1一定构成子问题1 2…. n-1在容量为W时的最优解
根据上述分析，设c[i w]表示背包容量为w时i个物品最优解的总价值，得到公式：
0 i = 0或w = 0
C[ i w ] = c [i – 1 w] wi > w
max{ c [ i – 1 w – wi ] vi c [ i – 1 w ] } i > 0 且 wi <= w
2、根据物品的件数 i = 5、包的容量W = 17规划"价值"分布矩阵，如下图所示：
（1）物品价值重量关系表
（2）物品件数—价值分布矩阵
（二）程序实现
1、Java语言代码实现如下：
public static void main(String[] args) {
int[] goods_weight = {3 4 7 8 9}; //物品重量
int[] goods_value = {4 5 10 11 13}; //物品价值
int m = 17; //背包容量
int n = 5; //物品个数
//c[i][j]表示前i个物品能装入容量为Wj的背包中的最大价值
int c[][] = new int[n 1][m 1];
int path[][] = new int[n 1][m 1];
//初始化第一列和第一行
for(int i=0;i<c.length;i ){
c[i][0] = 0;
}
for(int i=0;i<c[0].length;i ){
c[0][i] = 0;
}
//通过公式迭代计算
for(int i=1;i<c.length;i ){
for(int Wj=1;Wj<c[0].length;Wj ){
if(goods_weight[i-1]>Wj)
c[i][Wj] = c[i-1][Wj];
else{
if(c[i-1][Wj]<c[i-1][Wj-goods_weight[i-1]] goods_value[i-1]){
c[i][Wj] = c[i-1][Wj-goods_weight[i-1]] goods_value[i-1];
path[i][Wj] = 1;
}else{
c[i][Wj] = c[i-1][Wj];
}
}
}
}
for(int i=0;i<c.length;i ){
for(int j=0;j<c[0].length;j ){
System.out.print(c[i][j] " ");
}
System.out.println();
}
int i=c.length-1;
int j=c[0].length-1;
while(i>0&&j>0){
if(path[i][j] == 1){
System.out.print("第" i "个物品装入 ");
j -= goods_weight[i-1];
}
i--;
}
}
2、C/C 代码实现如下：
int** demo(int n int W int* Weights float* Values)
{
int i w;
//为二维数组申请空间
int** c = (int**)malloc(sizeof(int *)*(n 1));
for(i=0;i<=n;i )
c[i] = (int *)malloc(sizeof(int)*(W 1));
//初始化二维数组
for(w=0;w<=W;w )
c[0][w]=0;
for(i=1;i<=n;i )
{
c[i][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;
}
