fac5_2_3.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[] w,int c ,int []bestx)
    {
      //迭代回溯法
      //返回最优载重量及其相应解
      //初始化根结点
      int i=1;//当前层
      int n=w.length-1;
      int []x=new int[n+1];
      int bestw=0;
      int cw=0;
      int r=0;
     
      //初始化 r
      for(int j=1;j<=n;j++)
      r+=w[j];

      //搜索子树
    while(true)
     {
      while(i<=n && cw+w[i]<=c)
       {//进入左子树    
     
       r-=w[i];     
       cw+=w[i];
       x[i]=1;
       i++;
       }
     if(i>n)
      {//到达叶结点
        for(int j=1;j<=n;j++)
           bestx[j]=x[j];
        bestw=cw;
      }
     else
      {//进入右子树
        r-=w[i];
        x[i]=0;
        i++;
      }
    while(cw+r<=bestw)
      {//剪枝回溯      
       i--;
       while(i>0 && x[i]==0)
        {//从右子树返回
         r+=w[i];
         i--;
        }
       if(i==0)return bestw;
        //进入右子树
        x[i]=0;
        cw-=w[i];
        i++;
      }
     }
    }     
  }  

public class Fac5_2_3{
  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("  ");
      }
 }