fac3_9_1.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 96 页，例
//0-1背包问题改进动态规划解法
public class Fac3_9_1{
   public static double knapsack(double []w,double []v,double c,double [][]p,int []head)
   {
     int n=v.length-1;
     head[n+2]=0;
     p[0][0]=0;
     p[0][1]=0;
     int left=0,right=0,next=1;
     head[n+1]=1;
     for(int i=n;i>=0;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];
       // System.out.println("y="+y+"  ,m= "+m);
        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;
    //  System.out.println("@@@@@@@@@@@@@@"); 
     head[i]=next;
     } 
   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];
    double m=p[head[0]-1][1];
    for(int i=0;i<=n;i++){
         x[i]=0;
         for(int k=head[i+2];k<=head[i+1]-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;
        }
       }
      }
  }
       
      public static void main(String args[])
  {
    double v1[]={6,3,5,4,6};
    double w1[]={2,2,6,5,4};
    double c1=10;
    int n1=v1.length-1;
    int head1[]=new int[n1+3];
    int x1[]=new int[n1+1];
    double [][]m1=new double[100][2];       
    System.out.println("最大价值是  "+ knapsack(w1,v1,c1,m1,head1));
    traceback(w1,v1,m1,head1,x1);
    for(int i=0;i<=n1;i++)
    System.out.print(x1[i]+"  ");
    System.out.println();
  }
}