fac5_2.java

/最优装载问题解法

//
//本程序取自王晓东编著“算法分析与设计”第 154 页，例
//最优装载问题解法
class Loading
   {
    //类数据成员
     static int n;     //集装箱数
     static int[] w;   //集装箱重量数组
     static int c;     //第一艘轮船的载重量
     static int cw;    //当前载重量
     static int bestw;  //当前最优载重量
    
    public static int maxLoading(int[] ww,int cc)
    {
     //初始化类数据成员
      n=ww.length-1;
      w=ww;
      c=cc;
      cw=0;
      bestw=0;

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

public class Fac5_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));
         // System.out.println("所选集装箱序列  ");
         //for(int k=0;k<n;k++){
         //if(xa[k]==0)break;
         // }
         //System.out.println("  ");
      }
 }