fac5_2_2.java

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

//
//本程序取自王晓东编著“算法分析与设计”第 156页，例
//最优装载问题回溯算法改进解法（构造最优解）
class Loading
   {
    //类数据成员
     static int n;     //集装箱数
     static int[] w;   //集装箱重量数组
     static int c;     //第一艘轮船的载重量
     static int cw;    //当前载重量
     static int bestw;  //当前最优载重量
     static int r;      //剩余集装箱数量
     static int [] x;      //当前解
     static int [] bestx;  //当前最优解
    public static int maxLoading(int[] ww,int cc,int []xx)
    {
     //初始化类数据成员
      n=ww.length-1;
      w=ww;
      c=cc;
      cw=0;
      bestw=0;
      x=new int[n+1];
      bestx=xx;
     //初始化 r
      for(int i=1;i<=n;i++)
      r+=w[i];

     //计算最优载重量
      backtrack(1);
      return bestw;
    }
     //回溯算法
   public static void backtrack(int i)
    {
      //搜索第i层结点
      if(i>n){//到达叶结点
       for(int j=1;j<=n;j++)
         bestx[j]=x[j];
       bestw=cw;
       return;
       }
     //搜索子树
       r-=w[i];
      if(cw+w[i]<=c){//搜索左子树
         x[i]=1;
         cw+=w[i];
         backtrack(i+1);
         cw-=w[i];
     }
     if(cw+r>bestw)
      {
        x[i]=0;//搜索右子树
        backtrack(i+1);
      }
      r+=w[i];
   }
  }
    

public class Fac5_2_2{
  public static void main(String args[])
     {
         Loading abc=new Loading();
         int ca=5000;
         int 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(abc.maxLoading(wa,ca,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("  ");
      }
 }