0034算法筆記——[分支限界法]最優裝載問題

   有一批共個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。

     容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優裝載方案。
     (1)首先將第一艘輪船盡可能裝滿；
     (2)將剩余的集裝箱裝上第二艘輪船。

     1、隊列式分支限界法求解

      在算法的循環體中，首先檢測當前擴展結點的左兒子結點是否為可行結點。如果是則將其加入到活結點隊列中。然後將其右兒子結點加入到活結點隊列中(右兒子結點一定是可行結點)。2個兒子結點都產生後，當前擴展結點被捨棄。

     活結點隊列中的隊首元素被取出作為當前擴展結點，由於隊列中每一層結點之後都有一個尾部標記-1，故在取隊首元素時，活結點隊列一定不空。當取出的元素是-1時，再判斷當前隊列是否為空。如果隊列非空，則將尾部標記-1加入活結點隊列，算法開始處理下一層的活結點。

     節點的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設bestw是當前最優解；ew是當前擴展結點所相應的重量；r是剩余集裝箱的重量。則當ew+r<bestw時，可將其右子樹剪去，因為此時若要船裝最多集裝箱，就應該把此箱裝上船。另外，為了確保右子樹成功剪枝，應該在算法每一次進入左子樹的時候更新bestw的值。

     為了在算法結束後能方便地構造出與最優值相應的最優解，算法必須存儲相應子集樹中從活結點到根結點的路徑。為此目的，可在每個結點處設置指向其父結點的指針，並設置左、右兒子標志。

     找到最優值後，可以根據parent回溯到根節點，找到最優解。

     算法具體代碼實現如下：

     1、Queue.h

[cpp]
#include<iostream>  
using namespace std; 
 
template <class T> 
class Queue 
{ 
    public: 
        Queue(int MaxQueueSize=50); 
        ~Queue(){delete [] queue;} 
        bool IsEmpty()const{return front==rear;} 
        bool IsFull(){return ( (  (rear+1)  %MaxSize==front )?1:0);} 
        T Top() const; 
        T Last() const; 
        Queue<T>& Add(const T& x); 
        Queue<T>& AddLeft(const T& x); 
        Queue<T>& Delete(T &x); 
        void Output(ostream& out)const; 
        int Length(){return (rear-front);} 
    private: 
        int front; 
        int rear; 
        int MaxSize; 
        T *queue; 
}; 
 
template<class T> 
Queue<T>::Queue(int MaxQueueSize) 
{ 
    MaxSize=MaxQueueSize+1; 
    queue=new T[MaxSize]; 
    front=rear=0; 
} 
 
template<class T > 
T Queue<T>::Top()const 
{ 
    if(IsEmpty()) 
    { 
        cout<<"queue:no element,no!"<<endl; 
        return 0; 
    } 
    else return queue[(front+1) % MaxSize]; 
} 
 
template<class T> 
T Queue<T> ::Last()const 
{ 
    if(IsEmpty()) 
    { 
        cout<<"queue:no element"<<endl; 
        return 0; 
    } 
    else return queue[rear]; 
} 
 
template<class T> 
Queue<T>&  Queue<T>::Add(const T& x) 
{ 
    if(IsFull())cout<<"queue:no memory"<<endl; 
    else 
    { 
        rear=(rear+1)% MaxSize; 
        queue[rear]=x; 
    } 
    return *this; 
} 
 
template<class T> 
Queue<T>&  Queue<T>::AddLeft(const T& x) 
{ 
    if(IsFull())cout<<"queue:no memory"<<endl; 
    else 
    { 
        front=(front+MaxSize-1)% MaxSize; 
        queue[(front+1)% MaxSize]=x; 
    } 
    return *this; 
} 
 
template<class T> 
Queue<T>&  Queue<T> ::Delete(T & x) 
{ 
    if(IsEmpty())cout<<"queue:no element(delete)"<<endl; 
    else  
    { 
        front=(front+1) % MaxSize; 
        x=queue[front]; 
    } 
    return *this; 
} 
 
 
template<class T> 
void Queue <T>::Output(ostream& out)const 
{ 
    for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--) 
       out<<queue[i]; 
} 
 
template<class T> 
ostream& operator << (ostream& out,const Queue<T>& x) 
{x.Output(out);return out;} 

#include<iostream>
using namespace std;

template <class T>
class Queue
{
 public:
  Queue(int MaxQueueSize=50);
  ~Queue(){delete [] queue;}
  bool IsEmpty()const{return front==rear;}
  bool IsFull(){return ( (  (rear+1)  %MaxSize==front )?1:0);}
  T Top() const;
  T Last() const;
  Queue<T>& Add(const T& x);
  Queue<T>& AddLeft(const T& x);
  Queue<T>& Delete(T &x);
  void Output(ostream& out)const;
  int Length(){return (rear-front);}
 private:
  int front;
  int rear;
  int MaxSize;
  T *queue;
};

template<class T>
Queue<T>::Queue(int MaxQueueSize)
{
 MaxSize=MaxQueueSize+1;
 queue=new T[MaxSize];
 front=rear=0;
}

template<class T >
T Queue<T>::Top()const
{
 if(IsEmpty())
 {
  cout<<"queue:no element,no!"<<endl;
  return 0;
 }
 else return queue[(front+1) % MaxSize];
}

template<class T>
T Queue<T> ::Last()const
{
 if(IsEmpty())
 {
  cout<<"queue:no element"<<endl;
  return 0;
 }
 else return queue[rear];
}

template<class T>
Queue<T>&  Queue<T>::Add(const T& x)
{
 if(IsFull())cout<<"queue:no memory"<<endl;
 else
 {
  rear=(rear+1)% MaxSize;
     queue[rear]=x;
 }
 return *this;
}

template<class T>
Queue<T>&  Queue<T>::AddLeft(const T& x)
{
 if(IsFull())cout<<"queue:no memory"<<endl;
 else
 {
  front=(front+MaxSize-1)% MaxSize;
  queue[(front+1)% MaxSize]=x;
 }
 return *this;
}

template<class T>
Queue<T>&  Queue<T> ::Delete(T & x)
{
 if(IsEmpty())cout<<"queue:no element(delete)"<<endl;
 else
 {
  front=(front+1) % MaxSize;
  x=queue[front];
 }
 return *this;
}

template<class T>
void Queue <T>::Output(ostream& out)const
{
 for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--)
    out<<queue[i];
}

template<class T>
ostream& operator << (ostream& out,const Queue<T>& x)
{x.Output(out);return out;}
      2、6d3-1.cpp

[cpp]
//裝載問題 隊列式分支限界法求解   
#include "stdafx.h"  
#include "Queue.h"  
#include <iostream>  
using namespace std; 
 
const int N = 4; 
 
template<class Type> 
class QNode 
{ 
    template<class Type> 
    friend void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx[],bool ch); 
 
    template<class Type> 
    friend Type MaxLoading(Type w[],Type c,int n,int bestx[]); 
 
    private: 
        QNode *parent;  //指向父節點的指針  
        bool LChild;    //左兒子標識  
        Type weight;    //節點所相應的載重量  
}; 
 
template<class Type> 
void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx[],bool ch); 
 
template<class Type> 
Type MaxLoading(Type w[],Type c,int n,int bestx[]); 
 
int main() 
{ 
    float c = 70;   
    float w[] = {0,20,10,26,15};//下標從1開始    
    int x[N+1];   
    float bestw; 
   
    cout<<"輪船載重為："<<c<<endl;   
    cout<<"待裝物品的重量分別為："<<endl;   
    for(int i=1; i<=N; i++)   
    {   
        cout<<w[i]<<" ";   
    }   
    cout<<endl;   
    bestw = MaxLoading(w,c,N,x);   
   
    cout<<"分支限界選擇結果為:"<<endl;   
    for(int i=1; i<=4; i++)   
    {   
        cout<<x[i]<<" ";   
    }   
    cout<<endl;   
    cout<<"最優裝載重量為："<<bestw<<endl; 
   
    return 0;   
} 
 
//將活節點加入到活節點隊列Q中  
template<class Type> 
void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx[],bool ch) 
{ 
    if(i == n)//可行葉節點  
    { 
        if(wt == bestw) 
        { 
            //當前最優裝載重量  
            bestE = E; 
            bestx[n] = ch;           
        } 
        return; 
    } 
    //非葉節點  
    QNode<Type> *b; 
    b = new QNode<Type>; 
    b->weight = wt; 
    b->parent = E; 
    b->LChild = ch; 
    Q.Add(b); 
} 
 
template<class Type> 
Type MaxLoading(Type w[],Type c,int n,int bestx[]) 
{//隊列式分支限界法，返回最優裝載重量，bestx返回最優解  
 //初始化  
    Queue<QNode<Type>*> Q;      //活節點隊列  
    Q.Add(0);                   //同層節點尾部標識  
    int i = 1;                  //當前擴展節點所處的層  
    Type Ew = 0,                //擴展節點所相應的載重量  
         bestw = 0,             //當前最優裝載重量  
         r = 0;                 //剩余集裝箱重量  
 
    for(int j=2; j<=n; j++) 
    { 
        r += w[j]; 
    } 
     
    QNode<Type> *E = 0,           //當前擴展節點  
                *bestE;         //當前最優擴展節點  
 
    //搜索子集空間樹  
    while(true) 
    { 
        //檢查左兒子節點  
        Type wt = Ew + w[i]; 
        if(wt <= c)//可行節點  
        { 
            if(wt>bestw) 
            { 
                bestw = wt; 
            } 
            EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true); 
        } 
 
        //檢查右兒子節點  
        if(Ew+r>bestw) 
        { 
            EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false); 
        } 
        Q.Delete(E);//取下一擴展節點  
 
        if(!E)//同層節點尾部  
        { 
            if(Q.IsEmpty()) 
            { 
                break; 
            } 
            Q.Add(0);       //同層節點尾部標識  
            Q.Delete(E);    //取下一擴展節點  
            i++;            //進入下一層  
            r-=w[i];        //剩余集裝箱重量  
        } 
        Ew  =E->weight;      //新擴展節點所對應的載重量  
    } 
 
    //構造當前最優解  
    for(int j=n-1; j>0; j--) 
    { 
        bestx[j] = bestE->LChild; 
        bestE = bestE->parent; 
    } 
    return bestw; 
} 

//裝載問題 隊列式分支限界法求解
#include "stdafx.h"
#include "Queue.h"
#include <iostream>
using namespace std;

const int N = 4;

template<class Type>
class QNode
{
 template<class Type>
 friend void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx[],bool ch);

 template<class Type>
 friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);

 private:
  QNode *parent; //指向父節點的指針
  bool LChild;    //左兒子標識
  Type weight;    //節點所相應的載重量
};

template<class Type>
void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx[],bool ch);

template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[]);

int main()
{
 float c = 70; 
    float w[] = {0,20,10,26,15};//下標從1開始 
    int x[N+1]; 
 float bestw;
 
    cout<<"輪船載重為："<<c<<endl; 
    cout<<"待裝物品的重量分別為："<<endl; 
    for(int i=1; i<=N; i++) 
    { 
        cout<<w[i]<<" "; 
    } 
    cout<<endl; 
    bestw = MaxLoading(w,c,N,x); 
 
    cout<<"分支限界選擇結果為:"<<endl; 
    for(int i=1; i<=4; i++) 
    { 
        cout<<x[i]<<" "; 
    } 
    cout<<endl; 
 cout<<"最優裝載重量為："<<bestw<<endl;
 
    return 0; 
}

//將活節點加入到活節點隊列Q中
template<class Type>
void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx[],bool ch)
{
 if(i == n)//可行葉節點
 {
  if(wt == bestw)
  {
   //當前最優裝載重量
   bestE = E;
   bestx[n] = ch;   
  }
  return;
 }
 //非葉節點
 QNode<Type> *b;
 b = new QNode<Type>;
 b->weight = wt;
 b->parent = E;
 b->LChild = ch;
 Q.Add(b);
}

template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{//隊列式分支限界法，返回最優裝載重量，bestx返回最優解
 //初始化
 Queue<QNode<Type>*> Q;  //活節點隊列
 Q.Add(0);     //同層節點尾部標識
 int i = 1;     //當前擴展節點所處的層
 Type Ew = 0,    //擴展節點所相應的載重量
   bestw = 0,    //當前最優裝載重量
   r = 0;     //剩余集裝箱重量

 for(int j=2; j<=n; j++)
 {
  r += w[j];
 }
 
 QNode<Type> *E = 0,   //當前擴展節點
    *bestE;   //當前最優擴展節點

 //搜索子集空間樹
 while(true)
 {
  //檢查左兒子節點
  Type wt = Ew + w[i];
  if(wt <= c)//可行節點
  {
   if(wt>bestw)
   {
    bestw = wt;
   }
   EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);
  }

  //檢查右兒子節點
  if(Ew+r>bestw)
  {
   EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);
  }
  Q.Delete(E);//取下一擴展節點

  if(!E)//同層節點尾部
  {
   if(Q.IsEmpty())
   {
    break;
   }
   Q.Add(0);       //同層節點尾部標識
   Q.Delete(E); //取下一擴展節點
   i++;   //進入下一層
   r-=w[i];  //剩余集裝箱重量
  }
  Ew  =E->weight;  //新擴展節點所對應的載重量
 }

 //構造當前最優解
 for(int j=n-1; j>0; j--)
 {
  bestx[j] = bestE->LChild;
  bestE = bestE->parent;
 }
 return bestw;
}     程序運行結果如圖：

     2、優先隊列式分支限界法求解

      解裝載問題的優先隊列式分支限界法用最大優先隊列存儲活結點表。活結點x在優先隊列中的優先級定義為從根結點到結點x的路徑所相應的載重量再加上剩余集裝箱的重量之和。
     優先隊列中優先級最大的活結點成為下一個擴展結點。以結點x為根的子樹中所有結點相應的路徑的載重量不超過它的優先級。子集樹中葉結點所相應的載重量與其優先級相同。
     在優先隊列式分支限界法中，一旦有一個葉結點成為當前擴展結點，則可以斷言該葉結點所相應的解即為最優解。此時可終止算法。

     算法具體代碼實現如下：

     1、MaxHeap.h

[cpp]
template<class T> 
class MaxHeap 
{ 
    public: 
        MaxHeap(int MaxHeapSize = 10); 
        ~MaxHeap() {delete [] heap;} 
        int Size() const {return CurrentSize;} 
 
        T Max()  
        {          //查  
           if (CurrentSize == 0) 
           { 
                throw OutOfBounds(); 
           } 
           return heap[1]; 
        } 
 
        MaxHeap<T>& Insert(const T& x); //增  
        MaxHeap<T>& DeleteMax(T& x);   //刪  
 
        void Initialize(T a[], int size, int ArraySize); 
 
    private: 
        int CurrentSize, MaxSize; 
        T *heap;  // element array  
}; 
 
template<class T> 
MaxHeap<T>::MaxHeap(int MaxHeapSize) 
{// Max heap constructor.  
    MaxSize = MaxHeapSize; 
    heap = new T[MaxSize+1]; 
    CurrentSize = 0; 
} 
 
template<class T> 
MaxHeap<T>& MaxHeap<T>::Insert(const T& x) 
{// Insert x into the max heap.  
    if (CurrentSize == MaxSize) 
    { 
        cout<<"no space!"<<endl;  
        return *this;  
    } 
 
    // 尋找新元素x的位置  
    // i——初始為新葉節點的位置，逐層向上，尋找最終位置  
    int i = ++CurrentSize; 
    while (i != 1 && x > heap[i/2]) 
    { 
        // i不是根節點，且其值大於父節點的值，需要繼續調整  
        heap[i] = heap[i/2]; // 父節點下降  
        i /= 2;              // 繼續向上，搜尋正確位置  
    } 
 
   heap[i] = x; 
   return *this; 
} 
 
template<class T> 
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x) 
{// Set x to max element and delete max element from heap.  
    // check if heap is empty  
    if (CurrentSize == 0) 
    { 
        cout<<"Empty heap!"<<endl;  
        return *this;  
    } 
 
    x = heap[1]; // 刪除最大元素  
    // 重整堆  
    T y = heap[CurrentSize--]; // 取最後一個節點，從根開始重整  
 
    // find place for y starting at root  
    int i = 1,  // current node of heap  
       ci = 2; // child of i  
 
    while (ci <= CurrentSize)  
    { 
        // 使ci指向i的兩個孩子中較大者  
        if (ci < CurrentSize && heap[ci] < heap[ci+1]) 
        { 
            ci++; 
        } 
        // y的值大於等於孩子節點嗎？  
        if (y >= heap[ci]) 
        { 
            break;   // 是，i就是y的正確位置，退出  
        } 
 
        // 否，需要繼續向下，重整堆  
        heap[i] = heap[ci]; // 大於父節點的孩子節點上升  
        i = ci;             // 向下一層，繼續搜索正確位置  
        ci *= 2; 
    } 
 
    heap[i] = y; 
    return *this; 
} 
 
template<class T> 
void MaxHeap<T>::Initialize(T a[], int size,int ArraySize) 
{// Initialize max heap to array a.  
    delete [] heap; 
    heap = a; 
    CurrentSize = size; 
    MaxSize = ArraySize; 
 
    // 從最後一個內部節點開始，一直到根，對每個子樹進行堆重整  
   for (int i = CurrentSize/2; i >= 1; i--) 
   { 
        T y = heap[i]; // 子樹根節點元素  
        // find place to put y  
        int c = 2*i; // parent of c is target  
                   // location for y  
        while (c <= CurrentSize)  
        { 
            // heap[c] should be larger sibling  
            if (c < CurrentSize && heap[c] < heap[c+1]) 
            { 
                c++; 
            } 
            // can we put y in heap[c/2]?  
            if (y >= heap[c]) 
            { 
                break;  // yes  
            } 
 
            // no  
            heap[c/2] = heap[c]; // move child up  
            c *= 2; // move down a level  
        } 
        heap[c/2] = y; 
    } 
} 

template<class T>
class MaxHeap
{
 public:
  MaxHeap(int MaxHeapSize = 10);
  ~MaxHeap() {delete [] heap;}
        int Size() const {return CurrentSize;}

        T Max()
  {          //查
           if (CurrentSize == 0)
     {
                throw OutOfBounds();
     }
           return heap[1];
        }

  MaxHeap<T>& Insert(const T& x); //增
  MaxHeap<T>& DeleteMax(T& x);   //刪

  void Initialize(T a[], int size, int ArraySize);

 private:
  int CurrentSize, MaxSize;
  T *heap;  // element array
};

template<class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize)
{// Max heap constructor.
 MaxSize = MaxHeapSize;
 heap = new T[MaxSize+1];
 CurrentSize = 0;
}

template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x)
{// Insert x into the max heap.
 if (CurrentSize == MaxSize)
 {
  cout<<"no space!"<<endl;
  return *this;
 }

    // 尋找新元素x的位置
    // i——初始為新葉節點的位置，逐層向上，尋找最終位置
 int i = ++CurrentSize;
 while (i != 1 && x > heap[i/2])
 {
  // i不是根節點，且其值大於父節點的值，需要繼續調整
  heap[i] = heap[i/2]; // 父節點下降
  i /= 2;              // 繼續向上，搜尋正確位置
    }

   heap[i] = x;
   return *this;
}

template<class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x)
{// Set x to max element and delete max element from heap.
 // check if heap is empty
 if (CurrentSize == 0)
 {
  cout<<"Empty heap!"<<endl;
  return *this;
 }

 x = heap[1]; // 刪除最大元素
 // 重整堆
 T y = heap[CurrentSize--]; // 取最後一個節點，從根開始重整

 // find place for y starting at root
 int i = 1,  // current node of heap
    ci = 2; // child of i

 while (ci <= CurrentSize)
    {
  // 使ci指向i的兩個孩子中較大者
  if (ci < CurrentSize && heap[ci] < heap[ci+1])
  {
   ci++;
  }
  // y的值大於等於孩子節點嗎？
  if (y >= heap[ci])
  {
   break;   // 是，i就是y的正確位置，退出
  }

  // 否，需要繼續向下，重整堆
  heap[i] = heap[ci]; // 大於父節點的孩子節點上升
  i = ci;             // 向下一層，繼續搜索正確位置
  ci *= 2;
    }

 heap[i] = y;
 return *this;
}

template<class T>
void MaxHeap<T>::Initialize(T a[], int size,int ArraySize)
{// Initialize max heap to array a.
 delete [] heap;
 heap = a;
 CurrentSize = size;
 MaxSize = ArraySize;

 // 從最後一個內部節點開始，一直到根，對每個子樹進行堆重整
   for (int i = CurrentSize/2; i >= 1; i--)
   {
  T y = heap[i]; // 子樹根節點元素
  // find place to put y
  int c = 2*i; // parent of c is target
                   // location for y
  while (c <= CurrentSize)
  {
   // heap[c] should be larger sibling
   if (c < CurrentSize && heap[c] < heap[c+1])
   {
    c++;
   }
   // can we put y in heap[c/2]?
   if (y >= heap[c])
   {
    break;  // yes
   }

   // no
   heap[c/2] = heap[c]; // move child up
   c *= 2; // move down a level
        }
  heap[c/2] = y;
 }
}     2、6d3-2.cpp

[cpp]
//裝載問題 優先隊列式分支限界法求解   
#include "stdafx.h"  
#include "MaxHeap.h"  
#include <iostream>  
using namespace std; 
 
const int N = 4; 
 
class bbnode; 
 
template<class Type> 
class HeapNode 
{ 
    template<class Type> 
    friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev); 
    template<class Type> 
    friend Type MaxLoading(Type w[],Type c,int n,int bestx[]); 
    public: 
        operator Type() const{return uweight;} 
    private: 
        bbnode *ptr;        //指向活節點在子集樹中相應節點的指針  
        Type uweight;       //活節點優先級(上界)  
        int level;          //活節點在子集樹中所處的層序號  
}; 
 
class bbnode 
{ 
    template<class Type> 
    friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev); 
    template<class Type> 
    friend Type MaxLoading(Type w[],Type c,int n,int bestx[]); 
    friend class AdjacencyGraph; 
 
    private: 
        bbnode *parent;     //指向父節點的指針  
        bool LChild;        //左兒子節點標識  
}; 
 
template<class Type> 
void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev); 
 
template<class Type> 
Type MaxLoading(Type w[],Type c,int n,int bestx[]); 
 
 
int main() 
{ 
    float c = 70;   
    float w[] = {0,20,10,26,15};//下標從1開始    
    int x[N+1];   
    float bestw; 
   
    cout<<"輪船載重為："<<c<<endl;   
    cout<<"待裝物品的重量分別為："<<endl;   
    for(int i=1; i<=N; i++)   
    {   
        cout<<w[i]<<" ";   
    }   
    cout<<endl;   
    bestw = MaxLoading(w,c,N,x);   
   
    cout<<"分支限界選擇結果為:"<<endl;   
    for(int i=1; i<=4; i++)   
    {   
        cout<<x[i]<<" ";   
    }   
    cout<<endl;   
    cout<<"最優裝載重量為："<<bestw<<endl; 
   
    return 0;  
} 
 
//將活節點加入到表示活節點優先隊列的最大堆H中  
template<class Type> 
void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev) 
{ 
    bbnode *b = new bbnode; 
    b->parent = E; 
    b->LChild = ch; 
    HeapNode<Type> N; 
 
    N.uweight = wt; 
    N.level = lev; 
    N.ptr = b; 
    H.Insert(N); 
} 
 
//優先隊列式分支限界法，返回最優載重量，bestx返回最優解  
template<class Type> 
Type MaxLoading(Type w[],Type c,int n,int bestx[]) 
{ 
    //定義最大的容量為1000  
    MaxHeap<HeapNode<Type>> H(1000); 
 
    //定義剩余容量數組  
    Type *r = new Type[n+1]; 
    r[n] = 0; 
 
    for(int j=n-1; j>0; j--) 
    { 
        r[j] = r[j+1] + w[j+1]; 
    } 
 
    //初始化  
    int i = 1;//當前擴展節點所處的層  
    bbnode *E = 0;//當前擴展節點  
    Type Ew = 0; //擴展節點所相應的載重量  
 
    //搜索子集空間樹  
    while(i!=n+1)//非葉子節點  
    { 
        //檢查當前擴展節點的兒子節點  
        if(Ew+w[i]<=c) 
        { 
            AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1); 
        } 
        //右兒子節點  
        AddLiveNode(H,E,Ew+r[i],false,i+1); 
 
        //取下一擴展節點  
        HeapNode<Type> N; 
        H.DeleteMax(N);//非空  
        i = N.level; 
        E = N.ptr; 
        Ew = N.uweight - r[i-1]; 
    } 
 
    //構造當前最優解  
    for(int j=n; j>0; j--) 
    { 
        bestx[j] = E->LChild; 
        E = E->parent; 
    } 
 
    return Ew; 
} 

//裝載問題 優先隊列式分支限界法求解
#include "stdafx.h"
#include "MaxHeap.h"
#include <iostream>
using namespace std;

const int N = 4;

class bbnode;

template<class Type>
class HeapNode
{
 template<class Type>
 friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);
 template<class Type>
 friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);
 public:
  operator Type() const{return uweight;}
 private:
  bbnode *ptr;  //指向活節點在子集樹中相應節點的指針
  Type uweight;  //活節點優先級(上界)
  int level;   //活節點在子集樹中所處的層序號
};

class bbnode
{
 template<class Type>
 friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);
 template<class Type>
 friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);
 friend class AdjacencyGraph;

 private:
  bbnode *parent;  //指向父節點的指針
  bool LChild;  //左兒子節點標識
};

template<class Type>
void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);

template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[]);

int main()
{
 float c = 70; 
    float w[] = {0,20,10,26,15};//下標從1開始 
    int x[N+1]; 
 float bestw;
 
    cout<<"輪船載重為："<<c<<endl; 
    cout<<"待裝物品的重量分別為："<<endl; 
    for(int i=1; i<=N; i++) 
    { 
        cout<<w[i]<<" "; 
    } 
    cout<<endl; 
    bestw = MaxLoading(w,c,N,x); 
 
    cout<<"分支限界選擇結果為:"<<endl; 
    for(int i=1; i<=4; i++) 
    { 
        cout<<x[i]<<" "; 
    } 
    cout<<endl; 
 cout<<"最優裝載重量為："<<bestw<<endl;
 
    return 0;
}

//將活節點加入到表示活節點優先隊列的最大堆H中
template<class Type>
void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev)
{
 bbnode *b = new bbnode;
 b->parent = E;
 b->LChild = ch;
 HeapNode<Type> N;

 N.uweight = wt;
 N.level = lev;
 N.ptr = b;
 H.Insert(N);
}

//優先隊列式分支限界法，返回最優載重量，bestx返回最優解
template<class Type>
Type MaxLoading(Type w[],Type c,int n,int bestx[])
{
 //定義最大的容量為1000
 MaxHeap<HeapNode<Type>> H(1000);

 //定義剩余容量數組
 Type *r = new Type[n+1];
 r[n] = 0;

 for(int j=n-1; j>0; j--)
 {
  r[j] = r[j+1] + w[j+1];
 }

 //初始化
 int i = 1;//當前擴展節點所處的層
 bbnode *E = 0;//當前擴展節點
 Type Ew = 0; //擴展節點所相應的載重量

 //搜索子集空間樹
 while(i!=n+1)//非葉子節點
 {
  //檢查當前擴展節點的兒子節點
  if(Ew+w[i]<=c)
  {
   AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);
  }
  //右兒子節點
  AddLiveNode(H,E,Ew+r[i],false,i+1);

  //取下一擴展節點
  HeapNode<Type> N;
  H.DeleteMax(N);//非空
  i = N.level;
  E = N.ptr;
  Ew = N.uweight - r[i-1];
 }

 //構造當前最優解
 for(int j=n; j>0; j--)
 {
  bestx[j] = E->LChild;
  E = E->parent;
 }

 return Ew;
}     程序運行結果如圖：