fac6_3.java

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

//本程序取自王晓东编著“算法分析与设计”第 198 页，例
//装载问题的分支限界解法
 class Element implements Comparable
   {
     int w;
     int id;
      public Element(int ww,int ii)
         {
           w=ww;
           id=ii;
         }
      public int compareTo(Object x)
         {
           int xw=((Element)x).w;
           if(w<xw)return -1;
           if(w==xw)return 0;
           return 1;
         }
   } 
  class AQueue 
   { private static final int defultSize=20;
     private int size;                     //
     private int front;
     private int rear;
     private Element[] listArray;
     
     AQueue(){setup(defultSize);}
     AQueue(int sz){setup(sz);}

     void setup(int sz)
      {size=sz+1;front=rear=0;listArray=new Element[sz+1];}
     public void clear()
      {front=rear=0;}
     public static void Assert_notFalse(boolean p,String q)
     {if(!p)System.out.println((String)q);}

     public void enqueue(Element it)
       {
        Assert_notFalse(((rear+1)% size)!=front,"Queue is full");
        rear=(rear+1)%size;
        listArray[rear]=it;
       }
    public Element remove()
       {
        Assert_notFalse(! isEmpty(),"Queue is empty ");
        front=(front+1)%size;
        return listArray[front];
       }
    public Element firstValue()
       {
        Assert_notFalse(! isEmpty(),"Queue is empty "); 
        return listArray[(front+1)%size];
       }
    public boolean isEmpty()
       { return front==rear;}
    public void put(int k,int g)
       {
       Element itg=new Element(k,g);
       enqueue(itg);
       }           
 
   }//class AQueue
  class FIFOBBloding
  {
    static int n;            // 表示最大层数，即集装箱个数
    static int bestw;        // 当前最优载重量
    static AQueue queue;     //活结点队列
  
    public static int maxLoading(int[] w,int c)
     {// 队列式分支限界法，返回最优载重量
      // 初始化
        n=w.length-1;
        bestw=0;
        queue=new AQueue();
        queue.put(1,-1);  //同层结点尾部标志
        
        int i=1;                     //当前扩展结点所处的层
        int ew=0;                    //扩展结点所相应的载重量
      //搜索子集空间树
        while(true)
        {
         //检查左儿子结点
         if(ew+w[i]<=c)//x[i]=1
          enQueue(ew+w[i],i);
         //右儿子结点总是可行的
         enQueue(ew,i);                        //x[i]=0
         ew=queue.remove().w;//取下一扩展结点
         if(ew==-1)
          {//同层结点尾部
            if(queue.isEmpty())return bestw;
            queue.put(i,-1);        //同层结点尾部标志
            ew=queue.remove().w;  //取下一扩展结点
            i++;    //进入下一层
          }
        }
      }
    private static void enQueue(int wt,int i)
       {//将活结点加入到活结点队列Q中
         if(i==n)
            {//可行叶结点
              if(wt>bestw)bestw=wt;
            }
         else  //非叶结点
           queue.put(i,wt);
       }
    }


  public class Fac6_3{
   

      public static void main(String args[])
  {

         FIFOBBloding abc=new  FIFOBBloding();
         int ca=5000;
         int wa[]={0,100,200,303,678,975,123,880,2400,1300,1500};
         int n1=wa.length;
         int xa[]=new int[n1];
         System.out.println("输出原始数据：第一艘轮船载重c="+ca);
         for(int i=0;i<n1;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("  ");
    
  }
}