《计算机算法设计与分析》第三章动态规划.pptVIP

* 3.6　0-1背包问题 问题描述 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? * 0-1背包问题是一个特殊的整数规划问题。 求(x1,x2,…,xn)使目标函数　　　　　　　　最大，其中c0, wi 0, vi 0, 1≤i≤n 0-1背包问题Knapsack(1,n,c) * 例：w = ( w1, w2, w3) = (2, 3, 4) v=(v1, v2, v3)=(2, 3, 4) 求Knapsack(1, 3, 6) 取x = (1, 0, 1)时，Knapsack(1,3,6) = (v1x1+v2x2+v3x3) = 1*1 + 2*0 + 5*1 = 6最大 用穷举法求解，时间复杂度为O(n2n) * 1、 最优子结构性质 证明：(反证法) 设(y1,y2,…,yn)是Knapsack(1,n,c)的一个最优解，则(y2,…,yn)是Knapsack(2,n,c-w1y1)子问题的一个最优解。若不然，设(z2,…,zn)是Knapsack(2,n,c-w1y1)的最优解，因此有 说明(y1,z2,…,zn)是Knap(1,n,c)的一个更优解，矛盾。 0-1背包问题Knapsack(1, n, c)满足最优性原理 * 2、 递归关系 设所给0-1背包问题的子问题记为Knapsack(i, n, j)， j≤c(假设c, wi取整数) Knapsack(i, n, j)的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。 注：子问题的背包容量j在不断地发生变化 * 由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下： 临界条件 说明：当j＜wi时，只有xi =0，则m(i,j)=m(i+1,j) 　　　当j≥wi时，取xi =0时，为m(i+1,j) 　 　　　 　 取xi =1时，为m(i+1,j-wi)+ vi 3、 算法描述 void Knapsack (Type *v, int *w, int c, int n, Type **m) {//m[1][c]为最优值 int jMax=min(w[n]-1,c); //j≤jMax,即0≤j＜wn; jjMax,即j≥wn for(int j=0;i=jMax;j++) m[n][j]=0; // 0≤jwn’ for(int j=w[n];i=c;j++) m[n][j]=v[n]; // j≥wn’ for(int i=n-1;i1;i--){　　//i1表示对i=1暂不处理 i=1时只需求m[1][c] jMax=min(w[i]-1,c); for(int j=0;j=jMax;j++) // 0≤j＜wi’ m[i][j]=m[i+1][j]; for(int j=w[i];j=c;j++) // j≥wi’ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } * void Traceback(Type **m, int *w, int c, int n, int *x) {//输出解X[ ] for (int i=1;in;i++) if (m[i][c]==m[i+1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c])?1:0; } * 4、 计算复杂性分析 算法复杂度分析 从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。 例：当c2n时，算法需要Ω(n2n)计算时间。 * 由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1