fac6_3_1.java

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

//本程序取自王晓东编著“算法分析与设计”第 204 页，例
//装载问题的分支限界改进解法
  class FIFOBBloding
  {
    static int n;            // 当前最优载重量
    static int bestw;        // 活结点队列
    static ArrayQueue queue; 
  
    public static int maxLoading(int[] w,int c)
     {// 队列式分支限界法，返回最优载重量
      // 初始化
        n=w.length-1;
        bestw=0;
        queue=new ArrayQueue();
        queue.put(new Integer(-1));  //同层结点尾部标志
        
        int i=1;                     //当前扩展结点所处的层
        int ew=0;                   //扩展结点所相应的载重量
        int r=0;                    //剩余集装箱重量
     for(int j=2;j<=n;j++)
        r+=w[j];
 
      //搜索子集空间树
        while(true)
        {
         //检查左儿子结点
         int wt=ew+w[i];            //左儿子结点的重量
         if(wt<=c)  //x[i]=1
          {//可行结点
          if(wt>bestw)bestw=wt;
           //加入活结点队列
          if(i<n)queue.put(new Integer(wt));
          }
       
         //检查右儿子结点 

         if(ew+r>bestw && i<n)     //可能含最优解
            queue.put(new Integer(ew));            
         ew=((Integer)queue.remove()).intValue;//取下一扩展结点
         if(ew==-1)
          {//同层结点尾部
            if(queue.isEmpty())return bestw;
            queue.put(new Integer(-1));        //同层结点尾部标志
            ew=((Integer)queue.remove()).intValue;  //取下一扩展结点
            i++;    //进入下一层
            r-=w[i];              //剩余集装箱重量
       }
     }
   }
 }


 public class Fac6_3_1{
   public static int bbflow(int nn)
   {
    //优先队列式分支限界法解批处理作业调度问题
      n=nn;
     sort();//对各作业在机器1和机器2上所需时间排序
     //初始化最小堆
     MinHeap heap=new MinHeap
     HeapNode enode=new HeapNode(n);
     //搜索排列空间树
     do
      {
     if(enode.s==n){//叶结点
       if(enode.sf2<bestc){
         bestc=enode.sf2;
         for(int i=0;i<n;i++)
          bestx[i]=enode.x[i];
         }
        }
     else //产生当前扩展结点的儿子结点
      for(inti=enode.s;i<n;i++){
       MyMath.swap(enode.x,enode.s,i);
       int[] f=new int[3];
       int bb=bound9enode.f);
       if(bb<bestc){
        // 子树可能含最优解 
        // 结点插入最小堆
        HeapNode node=new HeapNode(enode,f,bb,n); 
        heap.put(node0;}
        MyMath.swap(enode.x,enode.s,i);
        } // 完成结点扩展
        //  取下一扩展结点 
        enode=(HeapNode) heap.removeMin();
    }while(enode !=null && enode.s<=n); 
      return bestc;     
   }           

      public static void main(String args[])
  {
    int ca=5000;
         int wa[]={100,200,303,678,975,123,880,2400,1300,1500};        
         System.out.print("第一艘轮船承载最大重量 opt= ");              
         int n1=wa.length-1;
         int x1[]=new int[n1+1];   
         System.out.println("  "+maxLoading(wa,ca,x1));
         for(int i=0;i<=n1;i++)
         System.out.print(x1[i]+"  ");
         System.out.println();
  }
}