fac6_3_3.java

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

//本程序取自王晓东编著“算法分析与设计”第 208 页，例
//装载问题的优先队列式分支限界改进解法（构造最优解）


  class MaxHeap 
   {                      //Max-heap impmentation
     static HeapNode [] Heap;  //Pointer to the heap array
     static int size;     //Maximum size of the heap
     static int n;        //Number of intents now in heapheapsoet

    public MaxHeap(HeapNode [] h,int num,int max)//constructor
     { Heap=h;n=num;size=max;buildheap();}

    public int heapsize()//return current size of the heap
     {  return n;}

    public static boolean isLeaf(int pos)//true if pos is a leaf position
     { return(pos>=n/2)&&(pos<n);} 

    public static void Assert_notFalse(boolean p,String q)
     {if(!p)System.out.println((String)q);}

    public static int key( HeapNode [] q,int p)
     {  return q[p].uweight;}

  //return position for left child of pos
    public static int leftchild(int pos)
     { Assert_notFalse(pos<n/2,"position has no left child");
       return 2*pos+1;
     }

  //return position for right child of pos
    public static int rightchild(int pos)
     {Assert_notFalse(pos<(n-1)/2,"position has no right child");
     return 2*pos+2;
     }

    public static int parent(int pos)//return position for parent
     {Assert_notFalse(pos>0,"position has no parent");
     return (pos-1)/2;
     }

    public static  void buildheap() //Heapify contents of Heap
     {  for(int i=n/2-1;i>=0;i--)siftdown(i);}

    public static void swap(HeapNode [] q,int i,int j)
     {      
       HeapNode  temp;
       temp=q[i];q[i]=q[j];q[j]=temp;}

    private static void siftdown(int pos) //put intent in itscorrent place
     {Assert_notFalse((pos>=0) && (pos<n),"illegal heap position ");
     while(! isLeaf(pos))
      {
       int j=leftchild(pos);
       if((j<(n-1))&&(key(Heap,j)<key(Heap,j+1)))
         j++;// j is now index of child with greater value
       if(key(Heap,pos)>=key(Heap,j)) return;// Done
       swap(Heap,pos,j);
       pos=j;//Move down 
      }
     }

    public static void insert(HeapNode  val) //Insert value into heap
     { 
     Assert_notFalse(n<size,"Heap is full ");
     int curr=n++;
     Heap[curr]=val;      //start t end of heap
     //Now sift up until curr's parent's key<curr's key
     while((curr!=0)&&(key(Heap,curr)>key(Heap,parent(curr))))
       {
         swap(Heap,curr,parent(curr));
         curr=parent(curr);
       }
      }

    public static HeapNode  removeMax()  //remove minimum value
      {
       Assert_notFalse(n>0,"Removing from empty heap ");
       swap(Heap,0,--n);//swap minimum with last value
       if(n!=0)     //Not on last intent
       siftdown(0); //Put new heap root val in corrent place 
       return Heap[n];
     }

  //Remove intent at specified position 
    public static HeapNode  remove(int pos)
     {
      Assert_notFalse((pos>0)&&(pos<n),"illegal heap position ");
      swap(Heap,pos,--n);//swap with last value
      if(n!=0)     //Not on last intent
      siftdown(pos);//put new heap root val in corrent place
      return Heap[n];
     }

   public static void outMaxHeap()
     {
     for(int i=0;i<=n-1;i++)
     System.out.print(Heap[i].uweight+"  ");
     System.out.println(); 
     }       

  static void heapsort()  //heapsort
    {
     System.out.println("建最大堆之后排序");
     
     for(int i=1;i<size-1;i++) //now sort
     System.out.print(removeMax().uweight+"  ");
     System.out.println( );    //removemax places min value at end of heap
    } 
 }// class MaxHeap

   
 class BBNode
    {
     BBNode parent;
     boolean leftChild;
    
    //
     BBNode(BBNode par,boolean ch)
      {
      parent=par;
      leftChild=ch;
      
      }
    }
 class HeapNode implements Comparable
    {
     BBNode liveNode;
     int  uweight;
     int  level;
    //
     HeapNode(BBNode node,int up,int lev)
      {
        liveNode=node;
        uweight=up;
        level=lev;
      }
     public int compareTo(Object x)
      {
       int xuw=((HeapNode)x).uweight;
       if(uweight<xuw)return -1;
       if(uweight==xuw)return 0;
       return 1;
      }
     public boolean equals(Object x)
      {
       return uweight==((HeapNode)x).uweight;
      }
    }
   public class Fac6_3_3{
     private static void addLiveNode(int up,int lev,BBNode par,boolean ch,MaxHeap heap1)
      {//
       BBNode b=new BBNode(par,ch);
       HeapNode node=new HeapNode(b,up,lev);
       heap1.insert(node);
      }
 
    public static int maxLoading(int[] w,int c,int []bestx)
     {// 队列式分支限界法，返回最优载重量 bestx返回最优解
        int n=w.length-1;
       // int n2=Integer.MAX_VALUE;
        HeapNode []abc=new HeapNode[n+1];       
       MaxHeap heap=new MaxHeap(abc,0,n+3 );
       //System.out.println("n="+n);
      
       //System.out.println("heap.n="+heap.n);
       //System.out.println("heap.size="+heap.size);
        BBNode e=null;               //当前扩展结点        
        int i=1;                     //当前扩展结点所处的层
        int ew=0;                    //扩展结点所相应的载重量
        int []r=new int[n+1];        //定义剩余重量数组r
        for(int j=n-1;j>=0;j--)
        {r[j]=r[j+1]+w[j+1];}
        
      //搜索子集空间树
        while(i!=n+1)
        {//非叶结点
         //检查当前扩展结点的儿子结点
       //  System.out.println("@@ i="+i+"  heap.n="+heap.n);
         if(ew+w[i]<=c)  
          //左儿子结点为可行结点
         addLiveNode(ew+w[i]+r[i],i+1,e,true,heap);          
       
         // 右儿子结点总为可行结点 
          addLiveNode(ew+r[i],i+1,e,false,heap); 
         //取下一个扩展结点
        
        HeapNode node=(HeapNode)heap.removeMax();
        i=node.level;
        e=node.liveNode;
        ew=node.uweight-r[i-1];
     //    heap.outMaxHeap();
      //  System.out.println("ew=  "+ew);
       }
      //构造当前最优解

    for(int j=n;j>0;j--)
     {
      bestx[j]=(e.leftChild)?1:0;
      e=e.parent;
     }
    return ew;
   }
 
      public static void main(String args[])
       {          
         int ca=5000;
         int wa[]={1000,2000,2303,4000};        
         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();
       }
  }