fac6_3_2.java

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

//本程序取自王晓东编著“算法分析与设计”第 205 页，例
//装载问题的分支限界改进解法（构造最优解）
  private static class QNode
    {
     QNode parent;
     boolean leftChild;
     int weight;
    //
     private QNode(QNode theParent,boolean theLeftChild,int the Weight)
      {
      parent=theParent;
      leftChild=theLeftChild;
      weight=theWeight;
      }
    }
  private static void enQueue(int wt,int i,QNode parent,boolean leftchild)
    {
      if(i==n)
       {//
        if(wt==bestw)
         {//
          bestE=parent;
          bestx[n]=(leftchild)?1:0;
         }
        return;
       }
      //
      QNode b=new QNode(parent,leftchild,wt);
      queue.put(b);
    }
  class FIFOBBloding
  {
    static int n;            // 当前最优载重量
    static int bestw;        // 活结点队列
    static ArrayQueue queue; 
    static QNode bestE;
    static int [] bestx;
    public static int maxLoading(int[] w,int c,int []xx)
     {// 队列式分支限界法，返回最优载重量
       初始化
        n=w.length-1;
        bestw=0;
        queue=new ArrayQueue();
        queue.put(null);  //同层结点尾部标志 r
        QNode e=null;
        bestE=null;
        bestx=xx;
        
        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)  
          {//可行结点
          if(wt>bestw)bestw=wt;
           enQueue(wt,i,e,true);
          }
       
         //检查右儿子结点 

         if(ew+r>bestw)enQueue(ew,i,e,false);            
         ew=(QNode)queue.remove());//取下一扩展结点
         if(e==null)
          {//同层结点尾部
            if(queue.isEmpty())break;
            queue.put(null);        //同层结点尾部标志
            e=((QNode)queue.remove();  //取下一扩展结点
            i++;    //进入下一层
            r-=w[i];              //剩余集装箱重量
       }
         ew=e.weight;
     }
    //
    for(int j=n-1;j>0;j--)
     {
      bestx[j]=(bestE.leftChild)?1:0;
      bestE=bestE.parent;
     }
    return bestw;
   }
 }


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