beibao.rar_0-1背包

public class Zero_one_package2 { // public static int ww=0; //存放最优解时背包的容量 // public static int vv=0; //存放最优解时背包的价值 public static double knapsack(double[]w,double[]v,double c,double [][]p,int[]x){ //*********************初始化********************** int n = v.length-1; int []head = new int[n+2]; head[n+1] = 0; p[0][0] = 0; p[0][1] = 0; int left = 0, right = 0, next = 1; head[n] = 1; for(int i=n;i>=1;i--){ int k = left; //**************计算被装入背包物品的最优解的跳跃点************* for(int j=left; j<=right;j++){ if(p[j][0]+w[i]>c) break; double y = p[j][0]+w[i], m = p[j][1]+v[i]; while(k<=right && p[k][0]<y){ p[next][0] = p[k][0]; p[next++][1] = p[k++][1]; } if(k<=right && p[k][0]==y){ if(m<p[k][1]) m = p[k][1]; k++; } if(m>p[next-1][1]){ p[next][0] = y; p[next++][1] = m; } while(k<right && p[k][1]<=p[next-1][1]) k++; } while(k<=right){ p[next][0] = p[k][0]; p[next++][1] = p[k++][1]; } left = right+1; right = next-1; head[i-1] = next; } //*********************输出跳跃点、最优解********************** traceback(w, v, p, head, x); System.out.println("跳跃点："); int j = n; int i; for( i=0;i<next-1;i++) { /*/////////////////////////////////////////////////////////////////////// switch(i) { case 1: System.out.println("p[6]："); case 2 :System.out.println("p[5]："); break; case 3 :System.out.println("p[4]："); break; case 4 :System.out.println("p[3]："); break; case 5 :System.out.println("p[2]："); break; default:System.out.println("p[1]:"); } //////////////////////////////////////////////////////////////////////////////*/ System.out.print("\t("+p[i][0]+","+p[i][1]+")"); if(i==head[j]-1){ System.out.println("\n"); j--; } } System.out.println("\n\n所以，当背包容量为"+p[i-1][0]+"时"+"背包的价值最大为"+p[i-1][1]); return p[next-1][1]; } //****************计算被装入背包的物品序列***************** public static void traceback(double[]w,double[]v,double[][]p,int[]head,int[]x){ int n = w.length-1; double j = p[head[0]-1][0], m = p[head[0]-1][1]; for(int i=0;i<=n;i++){ x[i]=0; for(int k=head[i+1];k<=head[i]-1; k++){ if(p[k][0]+w[i]==j && p[k][1]+v[i]==m){ x[i] = 1; j = p[k][0]; m = p[k][1]; break; } } } // System.out.print("\n");///////////////////////////// } //*******************主函数********************************* public static void main(String[] args) { //已知条件，包括背包容量，每件物品的重量与价值 double []v = new double[]{0,6,3,5,4,6};//初始化数组v double []w = new double[]{0,2,2,6,5,4};//初始化数组w double packageweight = 10.0;//背包容量 int len = v.length-1; int []x = new int[len+1];//x[]数组存放物品的装载序列 //int []head = new int[len+1]; double [][]p = new double[len+20][2];//定义数组p[][2]，其中p[][0]表示物品重量，p[][1]表示物品价值 Zero_one_package2.knapsack(w, v, packageweight, p , x); //public static double knapsack(double[]w,double[]v,double c,double [][]p,int[]x) } }