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

容易證明：如果一個(gè)給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。
(1)首先將第一艘輪船盡可能裝滿；
(2)將剩余的集裝箱裝上第二艘輪船。
思想：
在算法的循環(huán)體中，首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。如果是則將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中(右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn))。2個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄。

活結(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個(gè)尾部標(biāo)記-1，故在取隊(duì)首元素時(shí)，活結(jié)點(diǎn)隊(duì)列一定不空。當(dāng)取出的元素是-1時(shí)，再判斷當(dāng)前隊(duì)列是否為空。如果隊(duì)列非空，則將尾部標(biāo)記-1加入活結(jié)點(diǎn)隊(duì)列，算法開始處理下一層的活結(jié)點(diǎn)。

節(jié)點(diǎn)的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量。則當(dāng)ew+r<bestw時(shí)，可將其右子樹剪去，因?yàn)榇藭r(shí)若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。另外，為了確保右子樹成功剪枝，應(yīng)該在算法每一次進(jìn)入左子樹的時(shí)候更新bestw的值。

為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲(chǔ)相應(yīng)子集樹中從活結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)志。

找到最優(yōu)值后，可以根據(jù)parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解。

優(yōu)先隊(duì)列寫法：

#include<iostream> #include<queue>//優(yōu)先隊(duì)列的頭文件 using namespace std; //子集樹中節(jié)點(diǎn)的定義 class bbnode{ public:bbnode *parent;//指向父節(jié)點(diǎn)的指針 bool Lchild;//是否是左孩子結(jié)點(diǎn)的標(biāo)記 }; //優(yōu)先隊(duì)列中節(jié)點(diǎn)的定義 class HeapNode{public:bbnode *ptr; //指向活結(jié)點(diǎn)在子集樹中相應(yīng)節(jié)點(diǎn)的指針int uweight; //活結(jié)點(diǎn)的優(yōu)先級(jí)(上界) //優(yōu)先級(jí)的定義：從根節(jié)點(diǎn)到節(jié)點(diǎn)x的路徑相應(yīng)的載重量加上剩余集裝箱的重量之和int level; //活結(jié)點(diǎn)在子集樹中所處的層次 }; struct compare{bool const operator()(HeapNode *&a,HeapNode *&b){return (a->uweight) < (b->uweight);//最大堆 } }; //該函數(shù)是將新產(chǎn)生的活結(jié)點(diǎn)加入到子集樹中，并將這個(gè)節(jié)點(diǎn)插入到表示活結(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆中 void AddLiveNode(priority_queue<HeapNode*,vector<HeapNode*>,compare> &Q,bbnode *parent,bool isLeft,int uWeight,int level) {//先在子集樹中建立這個(gè)節(jié)點(diǎn)bbnode *b = new bbnode;b->parent = parent;b->Lchild = isLeft;//再在優(yōu)先隊(duì)列中新建一個(gè)節(jié)點(diǎn)HeapNode *h = new HeapNode;h->ptr = b;//將剛在添加到子集樹中的新節(jié)點(diǎn)b再賦值給將要添加到優(yōu)先隊(duì)列中的節(jié)點(diǎn)h h->uweight = uWeight;h->level = level; //將新建的節(jié)點(diǎn)添加到優(yōu)先隊(duì)列Q.push(h); }int MaxLoading(int *weight,int n,int *bestx,int c) {priority_queue<HeapNode*,vector<HeapNode*>,compare> Heap;int i=0;// 表示當(dāng)前所在子集樹的層次int now_weight=0;//表示當(dāng)前已裝載的重量int node_priority=0; //優(yōu)先級(jí)————裝載的最大上界=當(dāng)前裝載量+剩余集裝箱的重量HeapNode *H;//用于保存從優(yōu)先隊(duì)列出來的節(jié)點(diǎn) bbnode *B;//子集樹上的擴(kuò)展節(jié)點(diǎn)int *remains; //剩余集裝箱 ， 記載未裝的貨物remains = new int[n];remains[n-1]=0;//當(dāng)?shù)竭_(dá)最后的葉子節(jié)點(diǎn)時(shí)，沒有剩余的貨物 for(int j=n-2;j>=0;j--){ //計(jì)算當(dāng)?shù)竭_(dá)指定層時(shí)的剩余數(shù)組 remains[j]=remains[j+1]+weight[j+1];}while(i!=n)//沒有到達(dá)葉子節(jié)點(diǎn)時(shí) ,到達(dá)第i層 {if(now_weight+weight[i]<=c)//即當(dāng)前的重量能夠裝的下 =進(jìn)入左子樹 左孩子 {node_priority=(now_weight+weight[i]) +remains[i];//優(yōu)先級(jí) =當(dāng)前裝載量+剩余集裝箱的重量AddLiveNode(Heap,B,true,node_priority,i+1);}// 進(jìn)入右子樹 右孩子 node_priority=(now_weight) +remains[i];//優(yōu)先級(jí) =當(dāng)前裝載量+剩余集裝箱的重量AddLiveNode(Heap,B,false,node_priority,i+1);H = Heap.top(); //查詢優(yōu)先隊(duì)列隊(duì)頭結(jié)點(diǎn) Heap.pop(); //隊(duì)頭結(jié)點(diǎn)出隊(duì) i=H->level;B=H->ptr; //記錄當(dāng)前到達(dá)的結(jié)點(diǎn) now_weight=H->uweight - remains[i-1]; //計(jì)算當(dāng)前已經(jīng)裝載量 }// 記錄已裝載貨物 for(int j=n-1;j>=0;j--){bestx[j]=B->Lchild? 1:0;B=B->parent;}return now_weight; //返回最優(yōu)裝載量 } int main() {int n; //貨物數(shù) int shipNum; //貨船數(shù)量 int bestw; //最優(yōu)裝載量 int weight[n]; //貨物總重量 int bestx[n]; //最優(yōu)的裝載序列 int c1=0; //第一艘船的裝載重量 int c2=0; //第二艘船的裝載重量 cout<<"請(qǐng)輸入貨物數(shù)：";cin>>n;cout<<"請(qǐng)輸入貨船的數(shù)量：";cin>>shipNum;cout<<"請(qǐng)輸入貨物的重量序列：";for(int i=0;i<n;i++){cin>>weight[i];}cout<<"請(qǐng)輸入兩艘船的載重量：";cin>>c1>>c2;int maxc=0;//船的最大裝載重量 int sumc=c1+c2;//船的裝載重和 if(c1>c2)maxc=c1;else maxc=c2;int maxweight=0;//貨物中的最大重量int sumweight=0; //貨船總重量 for(int i=0;i<n;i++){if(weight[i]>maxweight){maxweight=weight[i];}sumweight+=weight[i];}if(maxweight>maxc){printf("貨物重量超過貨船的載重量，無法裝載！");return 0;} if(sumweight>sumc){printf("貨物總重量超過貨船的總載重量，無法裝載！");return 0;}MaxLoading(weight,n,bestx,c1);cout<<"裝載序列為："; for(int i=0;i<n;i++){cout<<bestx[i]<<" ";}cout<<endl;cout<<"第1艘船的最優(yōu)裝載量為："<<MaxLoading(weight,n,bestx,c1)<<endl;cout<<"裝載的貨物為：";for(int i=0;i<n;i++){if(bestx[i]!=0)cout<<weight[i]<<" ";}cout<<endl;cout<<"第2艘船的最優(yōu)裝載量為："<<sumweight-MaxLoading(weight,n,bestx,c1)<<endl;cout<<"裝載的貨物為：";for(int i=0;i<n;i++){if(bestx[i]!=1)cout<<weight[i]<<" ";}}

堆寫法：

#include<iostream> #include<queue>//優(yōu)先隊(duì)列的頭文件 using namespace std;class bbnode{ public:bbnode *parent;//指向父節(jié)點(diǎn)的指針 bool Lchild;//是否是左孩子結(jié)點(diǎn)的標(biāo)記 }; //優(yōu)先隊(duì)列中節(jié)點(diǎn)的定義 class HeapNode{public:operator double() const{return uweight;}int operator <= (HeapNode hn) const{return uweight<=hn.uweight; }int operator < (HeapNode hn) const{return uweight<hn.uweight; }int operator >= (HeapNode hn) const{return uweight>=hn.uweight; }int operator > (HeapNode hn) const{return uweight>hn.uweight; }int operator == (HeapNode hn) const{return uweight==hn.uweight; }HeapNode(){}bbnode *ptr; //指向活結(jié)點(diǎn)在子集樹中相應(yīng)節(jié)點(diǎn)的指針int uweight; //活結(jié)點(diǎn)的優(yōu)先級(jí)(上界) //優(yōu)先級(jí)的定義：從根節(jié)點(diǎn)到節(jié)點(diǎn)x的路徑相應(yīng)的載重量加上剩余集裝箱的重量之和int level; //活結(jié)點(diǎn)在子集樹中所處的層次 }; class MaxHeap { public:MaxHeap(int n); //構(gòu)造函數(shù)，N表示堆中能存儲(chǔ)的最大元素的個(gè)數(shù) void Insert(HeapNode heapNode); //向堆中插入一個(gè)結(jié)點(diǎn) void DeleteMax(HeapNode &heapNode); //刪除堆中的最大結(jié)點(diǎn) private:int size; HeapNode *MH; void Delete(HeapNode &heapNode,int index); //刪除堆中標(biāo)號(hào)為index的元素，index從1開始，即1表示最大元素 void SiftUp(int index); //將堆中標(biāo)號(hào)為index的元素，向上調(diào)整，保證堆結(jié)構(gòu) void SiftDown(int index); //將堆中標(biāo)號(hào)為index的元素，向下調(diào)整，保證堆結(jié)構(gòu) };MaxHeap::MaxHeap(int n) {size=0;MH=new HeapNode[n]; }void MaxHeap::SiftUp(int index) {if(index<=1)return;bool done=false;do{if(MH[index]>MH[index/2]){HeapNode tmp=MH[index];MH[index]=MH[index/2];MH[index/2]=tmp;}elsedone=true;index=index/2;}while(index>1&&!done); }void MaxHeap::SiftDown(int index) {if(2*index>size)return;bool done=false;do{index=2*index;if(index+1<=size&&MH[index+1]>MH[index])index=index+1;if(MH[index/2]<MH[index]){HeapNode tmp=MH[index];MH[index]=MH[index/2];MH[index/2]=tmp;}elsedone=true;}while(2*index<=size&&!done); }void MaxHeap::Insert(HeapNode heapNode) {size+=1;MH[size]=heapNode;SiftUp(size); }void MaxHeap::Delete(HeapNode &heapNode,int index) {if(index<1||index>size){return;}HeapNode x=MH[index],y=MH[size];heapNode=MH[index];size-=1;if(index==size+1)return;MH[index]=y;//將原來堆中的最后一個(gè)放到要被刪除的位置，再繼續(xù)調(diào)整堆 if(y>=x)SiftUp(index);elseSiftDown(index); }void MaxHeap::DeleteMax(HeapNode &heapNode) {Delete(heapNode,1); } //子集樹中節(jié)點(diǎn)的定義//該函數(shù)是將新產(chǎn)生的活結(jié)點(diǎn)加入到子集樹中，并將這個(gè)節(jié)點(diǎn)插入到表示活結(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆中 void AddLiveNode(MaxHeap &Q,bbnode *parent,bool isLeft,int uWeight,int level) {//先在子集樹中建立這個(gè)節(jié)點(diǎn)bbnode *b = new bbnode;b->parent = parent;b->Lchild = isLeft;//再在優(yōu)先隊(duì)列中新建一個(gè)節(jié)點(diǎn)HeapNode H;H.ptr = b;//將剛在添加到子集樹中的新節(jié)點(diǎn)b再賦值給將要添加到優(yōu)先隊(duì)列中的節(jié)點(diǎn)h H.uweight = uWeight;H.level = level; //將新建的節(jié)點(diǎn)添加到優(yōu)先隊(duì)列Q.Insert(H); }int MaxLoading(int *weight,int n,int *bestx,int c) {MaxHeap *Maxhp=new MaxHeap(100);;int i=0;// 表示當(dāng)前所在子集樹的層次int now_weight=0;//表示當(dāng)前已裝載的重量int node_priority=0; //優(yōu)先級(jí)————裝載的最大上界=當(dāng)前裝載量+剩余集裝箱的重量HeapNode H;//用于保存從優(yōu)先隊(duì)列出來的節(jié)點(diǎn) bbnode *B;//子集樹上的擴(kuò)展節(jié)點(diǎn)int *remains; //剩余集裝箱 ， 記載未裝的貨物remains = new int[n];remains[n-1]=0;//當(dāng)?shù)竭_(dá)最后的葉子節(jié)點(diǎn)時(shí)，沒有剩余的貨物 for(int j=n-2;j>=0;j--){ //計(jì)算當(dāng)?shù)竭_(dá)指定層時(shí)的剩余數(shù)組 remains[j]=remains[j+1]+weight[j+1];}while(i!=n)//沒有到達(dá)葉子節(jié)點(diǎn)時(shí) ,到達(dá)第i層 {if(now_weight+weight[i]<=c)//即當(dāng)前的重量能夠裝的下 =進(jìn)入左子樹 左孩子 {node_priority=(now_weight+weight[i]) +remains[i];//優(yōu)先級(jí) =當(dāng)前裝載量+剩余集裝箱的重量AddLiveNode(*Maxhp,B,true,node_priority,i+1);}// 進(jìn)入右子樹 右孩子 node_priority=(now_weight) +remains[i];//優(yōu)先級(jí) =當(dāng)前裝載量+剩余集裝箱的重量AddLiveNode(*Maxhp,B,false,node_priority,i+1);Maxhp->DeleteMax(H); //查詢優(yōu)先隊(duì)列隊(duì)頭結(jié)點(diǎn) i=H.level;B=H.ptr; //記錄當(dāng)前到達(dá)的結(jié)點(diǎn) now_weight=H.uweight - remains[i-1]; //計(jì)算當(dāng)前已經(jīng)裝載量 }// 記錄已裝載貨物 for(int j=n-1;j>=0;j--){bestx[j]=B->Lchild? 1:0;B=B->parent;}return now_weight; //返回最優(yōu)裝載量 } int main() {int n; //貨物數(shù) int shipNum; //貨船數(shù)量 int bestw; //最優(yōu)裝載量 int weight[n]; //貨物總重量 int bestx[n]; //最優(yōu)的裝載序列 int c1=0; //第一艘船的裝載重量 int c2=0; //第二艘船的裝載重量 cout<<"請(qǐng)輸入貨物數(shù)：";cin>>n;cout<<"請(qǐng)輸入貨船的數(shù)量：";cin>>shipNum;cout<<"請(qǐng)輸入貨物的重量序列：";for(int i=0;i<n;i++){cin>>weight[i];}cout<<"請(qǐng)輸入兩艘船的載重量：";cin>>c1>>c2;int maxc=0;//船的最大裝載重量 int sumc=c1+c2;//船的裝載重和 if(c1>c2)maxc=c1;else maxc=c2;int maxweight=0;//貨物中的最大重量int sumweight=0; //貨船總重量 for(int i=0;i<n;i++){if(weight[i]>maxweight){maxweight=weight[i];}sumweight+=weight[i];}if(maxweight>maxc){printf("貨物重量超過貨船的載重量，無法裝載！");return 0;} if(sumweight>sumc){printf("貨物總重量超過貨船的總載重量，無法裝載！");return 0;}MaxLoading(weight,n,bestx,c1);cout<<"裝載序列為："; for(int i=0;i<n;i++){cout<<bestx[i]<<" ";}cout<<endl;cout<<"第1艘船的最優(yōu)裝載量為："<<MaxLoading(weight,n,bestx,c1)<<endl;cout<<"裝載的貨物為：";for(int i=0;i<n;i++){if(bestx[i]!=0)cout<<weight[i]<<" ";}cout<<endl;cout<<"第2艘船的最優(yōu)裝載量為："<<sumweight-MaxLoading(weight,n,bestx,c1)<<endl;cout<<"裝載的貨物為：";for(int i=0;i<n;i++){if(bestx[i]!=1)cout<<weight[i]<<" ";}}

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析——分支限界法——装载问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。