fac4_3.java

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

//
//本程序取自王晓东编著“算法分析与设计”第 114 页，例
//最优装载问题解法
class Element implements Comparable
   {
     float w;
     int id;
      public Element(float ww,int ii)
         {
           w=ww;
           id=ii;
         }
      public int compareTo(Object x)
         {
           float xw=((Element)x).w;
           if(w<xw)return -1;
           if(w==xw)return 0;
           return 1;
         }
   } 
  public class Fac4_3{
        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].w-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 float loading(float c, float [] w, int [] x)
     {
      int n=w.length;
      Element [] d = new Element [n];
      for (int i = 0; i < n; i++)
        d[i] = new Element(w[i],i);
     mergeSort(d,0,n-1);
      float opt=0;
      for (int i = 0; i < n; i++) x[i] = 0;
      for (int i = 0; i < n && d[i].w <= c; i++) {
         x[d[i].id] =1;
         opt+=d[i].w;
         c -= d[i].w;
         }
      return opt;
     }
  public static void main(String args[])
     {
         float ca=5000;
         float wa[]={100,200,303,678,975,123,880,2400,1300,1500};
         int n=wa.length;
         int xa[]=new int[n];
         System.out.println("输出原始数据：轮船载重c="+ca);
         for(int i=0;i<n;i++)
         System.out.println("w["+i+"]="+wa[i]+" ");
         System.out.print("轮船承载最大价值 opt= ");
         System.out.println(loading(ca,wa,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("  ");
      }
 }