背包问题实验报告.doc.docVIP

《程序设计和算法语言》上机实验报告实验目的： 3.?掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法。 算法描述（可用文字描述，也可用流程图）：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi?，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？？ 在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。? ? 问题分析：令V(i,j)表示在前i(1=i=n)个物品中能够装入容量为就j(1=j=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) ??V(i,0)=V(0,j)=0? (2) ? V(i,j)=V(i-1,j) ?jwi ?? ? ?V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } jwi (1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi?的背包中的价值加上第i个物品的价值vi;?(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。? 源代码：public class bb { public static void knapsack(int[] v, int[] w, int c, int[][] m) { int n = v.length-1; int jMax = Math.min(w[n]-1, c); for(int j = 0; j = jMax; j++) m[n][j] = 0; for (int l = w[n]; l = c; l++) m[n][l] = v[n]; for(int i = n-1; i =1; i--) { jMax = Math.min(w[i]-1,c); for(int k = 0; k =jMax; k++) m[i][k] = m[i+1][k]; for(int h = w[i]; h = c; h++) m[i][h] = Math.max(m[i+1][h],m[i+1][h-w[i]]+v[i]); } m[0][c] = m[1][c]; if(c = w[0]) m[0][c] = Math.max(m[0][c],m[1][c-w[0]]+v[0]); System.out.println(bestw =+m[0][c]); } public static void traceback(int[][] m, int[] w, int c, int[] x) { int n = w.length-1; for(int i = 0; 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]0)?1:0; } public static void main(String[] args) { int[] ww = {2,2,6,5,4}; int[] vv = {6,3,5,4,6}; int[][] mm = new int[11][11]; knapsack(vv,ww,10,mm); int[] xx =new int[ww.length];