fac5_2_1.java

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

//
//本程序取自王晓东编著“算法分析与设计”第 155页，例
//最优装载问题回溯算法改进解法
class Loading
   {
    //类数据成员
     static int n;     //集装箱数
     static int[] w;   //集装箱重量数组
     static int c;     //第一艘轮船的载重量
     static int cw;    //当前载重量
     static int bestw;  //当前最优载重量
     static int r;      //剩余集装箱数量
    public static int maxLoading(int[] ww,int cc)
    {
     //初始化类数据成员
      n=ww.length-1;
      w=ww;
      c=cc;
      cw=0;
      bestw=0;
     //初始化 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)
       {  //到达叶结点
         if(cw>bestw)bestw=cw;
         return;
       }
     //搜索子树
       r-=w[i];
      if(cw+w[i]<=c)
       {  //搜索左子树
         cw+=w[i];
         backtrack(i+1);
         cw-=w[i];
       }
     if(cw+r>bestw)
        backtrack(i+1);
      r+=w[i];
    }
}
    

public class Fac5_2_1{
  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));
        
      }
 }