用分支限界算法解裝載問題詳解

1、湖州師范學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：算法實(shí)驗(yàn)五： 分支限界算法一、 實(shí)驗(yàn)?zāi)康?、理解分支限界法的概念，掌握分支限界法的基本要素。2、 掌握設(shè)計(jì)分支限界法的一般步驟，針對(duì)具體問題，能應(yīng)用分支限界法求解二、 實(shí)驗(yàn)內(nèi)容1、問題描述：有一批共個(gè)集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且w1+wn= C1+ C2; 裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。 2、數(shù)據(jù)輸入：文件輸入或鍵盤輸入。3、要求：1）完成上述問題的隊(duì)列式分支限界法解決問題，時(shí)間為 1 次課。2）獨(dú)立完成實(shí)驗(yàn)及實(shí)驗(yàn)報(bào)告。三、 實(shí)驗(yàn)步驟1、 理解方法思想和

2、問題要求。2、 采用編程語(yǔ)言實(shí)現(xiàn)題目要求。3、 上機(jī)輸入和調(diào)試自己所寫的程序。4、附程序主要代碼：#include using namespace std;class MaxHeapQNodepublic: MaxHeapQNode *parent; int lchild; int weight; int lev;struct cmp bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const return a-weight weight; ;int n;int c;int bestw;int w100;int bestx100;void

3、 InPut() scanf(%d %d, &n, &c); for(int i = 1; i = n; +i) scanf(%d, &wi);void AddAliveNode(priority_queueMaxHeapQNode *, vector, cmp &q, MaxHeapQNode *E, int wt, int i, int ch) MaxHeapQNode *p = new MaxHeapQNode; p-parent = E; p-lchild = ch; p-weight = wt; p-lev = i + 1; q.push(p);void MaxLoading() p

4、riority_queueMaxHeapQNode *, vector, cmp q; / 大頂堆 /定義剩余重量數(shù)組r int rn + 1; rn = 0; for(int j = n - 1; j 0; -j) rj = rj + 1 + wj + 1; int i = 1; MaxHeapQNode *E; int Ew = 0; while(i != n + 1) if(Ew + wi lev; Ew = E-weight - ri - 1; bestw = Ew; for(int j = n; j 0; -j) bestxj = E-lchild; E = E-parent; void OutPut() printf(最優(yōu)裝載量為 %dn, bestw); printf(裝載的物品為 n); for(int i = 1; i = n; +i) if(bestxi = 1) printf(%d , i);int main() InPut(); MaxLoading(); OutPut();5、實(shí)驗(yàn)結(jié)果：4、 裝載問題實(shí)驗(yàn)分析：1、將wt=best