动态规划-背包问题版本二.ppt

算法设计与分析第三章 动态规划-背包问题 杨圣洪 最化算法：动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归定义最优值。有难度。 以自底向上的方式计算出最优值。非递归 根据计算最优值时得到的信息，构造最优解。！ 第(1)为整体最优是否有局部最优。 3.10 0-1背包问题 给定n种物品和一背包。物品i的体积是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个 特殊的整数规划问题。 (板右边表达式) 3.10 0-1背包问题--最优子结构 给定n种物品和一背包。物品i的体积是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 若(y1,y2,…,yn)是全局最优解，则(y2,y3,…,yn)是子问题的最优解。 反证法假设子问题的最优解不是(y2,y3,…,yn)，而是(z2,…,zn) 。 则z2v2+z3v3+…+znvn y2v2+ y3v3 +…+ynvn， 且z2w2 +…+znwn?c-w1y1。 故w1y1 +z2w2 +…+znwn?c即(y1,z2,z3,…,zn)是原问题的可行解 但y1v1+ z2v2+z3v3+…+znvn y1v1+ y2v2+ y3v3 +…+ynvn 即(y1,z2,z3,…,zn)的价值高于(y1,y2,…,yn)，这与(y1,y2,…,yn)是最优解矛盾！故假设错。 递归公式 将子问题最优值记为m(i,j)，其中j为背包容量，i为候选物品的起始号，即候选物品为i,i+1,…,n。递归式如下： 将子问题最优值记为m(i,j)，j背包容量，i为候选物品的起始号。递归式如下： (活动区给出该公式,多算关键交互) 算法 void Knapsack(real* v,int* w,int c,int n,real** m){ //初始化数组m(n,j) for(int j=0;jw[n] j=c;j++){m[n][j]=0;} for(int j=w[n];j=c;j++){m[n][j]=v[n];} //已经最后一行m[n][j]的值，倒过计算m[i][j]的值 for (int i=n-1;i1;i--){ //当容量jw[i]时，物品i放不进，直接取同容量下行值 for(int j=0;jw[i] j=c;j++){m[i][j]=m[i+1][j];} //为j=w[i],+1,+2,..,c时价值 for(int j=w[i];j=c;j++) { m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);} } //以下i=1 if (cw[1]) { //首行只要直接考虑容量j=c的情形,jc均不考虑 m[1][c]=m[2][c];} else { //如果包容量cw[1]即物1能放入包中 m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);}} //边讲边板算法 构造 void Knapsack(real* v,int* w,int c,int n,real** m){ for(int j=0;jw[n] j=c;j++){ m[n][j]=0;} for(int j=w[n];j=c;j++){m[n][j]=v[n];} for (int i=n-1;i1;i--){ for(int j=0;jw[i] j=c;j++){ m[i][j]=m[i+1][j];} for(int j=w[i];j=c;j++) { m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]);} } //以下i=1 if (cw[1]) { m[1][c]=m[2][c];} else { m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]); }} 构造最优解算法描述 void traceback(int**m,int* w,int c,int n,int *x){ for (int i=1;in;i++) { if (m[i][c]==m[i+1][c]) {x[i]=0;} else {x[i]=1;c=c-w[i];} } x[n]=(m[n][c]0)?1:0; } 计算最优值算法及其复杂性 数组m[n][c] 从m(i,j)的递归式及左边程序可知：计