fac4_2.java

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

//
//本程序取自王晓东编著“算法分析与设计”第 113 页，例
//背包问题贪心解法
  class Element implements Comparable
   {
     float w;
     float v;
     int i;
      public Element(float ww,float vv,int ii)
         {
           w=ww;
           v=vv;
           i=ii;
         }
      public int compareTo(Object x)
         {
           float xw=((Element)x).w;
           if(w<xw)return -1;
           if(w==xw)return 0;
           return 1;
         }
   } 
  class Fac4_2{
     public static float knapsack(float c, float [] w, float []v,float [] x)
       {
      int n=v.length;
      Element [] d = new Element [n];
      for (int i = 0; i < n; i++)
        d[i] = new Element(w[i],v[i],i);
      mergeSort(d,0,n-1);
      int i;
      float opt=0;
      for (i=0; i<n; i++)x[i]=0;
      for (i=0; i<n; i++) {
         if(d[i].w>c)break;
         x[d[i].i] = 1;
         opt+=d[i].v;
         c -= d[i].w;
         }
      if(i<n){
       x[d[i].i]=c/d[i].w;
       opt+=x[d[i].i]*d[i].v;
       }
      return opt;
    }
      public static void mergeSort(Element[] a,int left,int right)
    {
     Element b[]=new Element[a.length];
     if(left<right){//至少有2个元素
     int i=(left+right)/2;//取中点 
     mergeSort(a,left,i);
     mergeSort(a,i+1,right);
     merge(a,b,left,i,right);//合并到数组 b
     copy(a,b,left,right);//复制回数组 a
      }
     }
   public static void copy(Element[] a,Element[] b,int i,int j)
    {
      int k;
      for(k=i;k<=j;k++)
      a[k]=b[k];
     } 
  public static void merge(Element[] c,Element[] d,int l,int m,int r)
     {//合并c[l:m]和c[m+1:r]到d[l:m]
      int i=l,
          j=m+1,
          k=l;
      while((i<=m)&&(j<=r))
          if((c[i].v/c[i].w-c[j].v/c[j].w)>=0)
             d[k++]=c[i++];
          else d[k++]=c[j++];
          if(i>m)
          for(int q=j;q<=r;q++)
              d[k++]=c[q];
          else 
           for(int q=i;q<=m;q++)
              d[k++]=c[q];
      }
    public static void main(String agrc[])
       {
         float ca=50;
         float wa[]={10,20,30};
         float va[]={60,100,120};
         int n=wa.length;
         float xa[]=new float[n];
         System.out.println("输出原始数据：背包容量c="+ca);
         for(int i=0;i<n;i++)
         System.out.println("w["+i+"]="+wa[i]+"  v["+i+"]="+va[i]+"   v/w="+va[i]/wa[i]);
         System.out.print("背包承载最大价值 opt= ");
         System.out.println(knapsack(ca,wa,va,xa));
         System.out.println("所选物品序列  ");
         for(int k=0;k<n;k++){
         // if(xa[k]==0)break;
         System.out.print("xa["+k+"]="+xa[k]+"   ");
         }
         System.out.println("  ");
       }
  }