fac5_6_1.java

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

//本程序取自王晓东编著“算法分析与设计”第 165 页，例
//背包问题的贪心解法
//
   class Knapsack
   { 
      private  static class Element implements Comparable
        {
          int id;//物品编号
          double d;
          private Element(int idd,double dd)
           {
             id=idd;
             d=dd;
           }
        public int compareTo(Object x)
           {
             double xd=((Element) x).d;
             if(d<xd)return -1; 
             if(d==xd)return 0;
             return 1;
           }
       public boolean equals(Object x)
          {return d==((Element) x).d;}
      }
    
     static double  c;         // 背包容量
     static int n;             // 物品数 
     static double []w ;       // 物品数量数组 
     static double []p;        // 物品价值数组
     static double cw;         // 当前重量
     static double cp;         // 当前价值
     static double bestp;      // 当前最优价值
      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].d-c[j].d>=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 double knapsack(double []pp,double []ww,double cc)
     {
     c=cc;
     n=pp.length-1;
     cw=0.0;
     cp=0.0;
     bestp=0.0;
     //q为单位重量价值数组
     Element []q=new Element[n];
     //初始化   q[0,n-1]

     for(int i=1;i<=n;i++)
      q[i-1]= new Element(i,pp[i]/ww[i]);
   // 将各物品依单位重量价值从大到小排序 
       mergeSort(q,0,n-1);
     // System.out.println("输出依单位重量价值从大到小排序  ");
     // for(int i=0;i<q.length;i++)
     // System.out.print(q[i].d+"  ");
     // System.out.println();
     p=new double[n+1];
     w=new double[n+1];
     for(int i=1;i<=n;i++)
      {
       p[i]=pp[q[i-1].id];
       w[i]=ww[q[i-1].id];
      }
     //  System.out.println("输出单位价值升序排序后的价值顺序结果  ");
     //  for(int i=1;i<p.length;i++)
     // System.out.print(p[i]+"  ");
     // System.out.println();
     //  System.out.println("输出单位价值升序排序后的重量顺序结果  ");
     //  for(int i=1;i<w.length;i++)
     // System.out.print(w[i]+"  ");
     // System.out.println();
     return bound(1);
    }
     private static double bound(int i)
       {//计算上界
        double cleft=c-cw;// 剩余容量 
          
        double bound=cp;
        //以物品单位重量价值递减顺序装入物品
        while(i<=n && w[i]<=cleft)
          {//System.out.println("剩余容量="+cleft+"  w["+i+"]="+w[i]+","+p[i]); 
            cleft-=w[i];
            bound+=p[i];
            i++;
          }
        //System.out.println("剩余容量="+cleft+"  w["+i+"]="+cleft/w[i]+","+p[i]);
        //装满背包
        if(i<=n)
         bound+=p[i]/w[i]*cleft;
        return bound;
      }
     
  }
      public class Fac5_6_1{
      public static void main(String args[])
  {
     double pk[]={0,9d,10d,7d,4d};
     double wk[]={0,3d,5d,2d,1d};
     Knapsack abc=new Knapsack();
     abc.n=4;
     abc.c=7;
     abc.p=pk;
     abc.w=wk;
      
     System.out.println("0-1背包装入最大价值为 " + abc.knapsack(abc.p,abc.w,abc.c));
  }
}