優(yōu)先隊列式分支限界法求解01背包問題

1、算法分析與設(shè)計實驗報告第 7 次實驗姓名學(xué)號班級時間6.4上午地點四合院 實驗名稱優(yōu)先隊列式分支限界法求解0-1背包問題實驗?zāi)康耐ㄟ^上機實驗，要求掌握優(yōu)先隊列式分支限界法求解0-1背包問題的問題描述、算法設(shè)計思想、程序設(shè)計。實驗原理1、使用優(yōu)先隊列式分支限界法算法，根據(jù)不同的輸入用例，能準(zhǔn)確的輸出背包能裝的最大價值，并計算出程序運行所需要的時間。2、分支限界法常以廣度優(yōu)先或最小耗費優(yōu)先（最大效益優(yōu)先）方式搜索問題的解空間樹， 對于0-1背包問題的解空間樹是一個棵子集樹。3、在分支限界法中有一個活結(jié)點表，活結(jié)點表中的每個活結(jié)點只有一次機會成為擴展結(jié)點，一旦成為 擴展結(jié)點就一次性產(chǎn)生所有兒子結(jié)點，

2、在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子 結(jié)點被舍棄，其余兒子結(jié)點被加入到活結(jié)點表中。4、為了盡快找到0-1背包問題的解，每次選取下一個活結(jié)點成為擴展結(jié)點的判斷依據(jù)是當(dāng)前情況下 最有可能找到最優(yōu)解的下一個結(jié)點。因此，每次選擇擴展結(jié)點的方法：當(dāng)前情況下，在活結(jié)點表中 選擇活結(jié)點的上界，最大的活結(jié)點成為當(dāng)前的擴展結(jié)點。 這一過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。實驗步驟1、定義樹結(jié)點類bbnode，用于構(gòu)造子集樹，以便計算最優(yōu)解；定義堆結(jié)點類HeapNode，用于定義堆元素類型； 定義最大堆類MaxHeap，用于實現(xiàn)優(yōu)先隊列定義.物品類Object，用于保存物品編號和物品的單位

3、重量價值；定義解決0-1背包問題的主類Knap。2、設(shè)計求解0-1背包問題的主函數(shù)Knapsack，在其中對物品以單位價值量排序。3、設(shè)計負責(zé)求解0-1背包問題的最優(yōu)值和最優(yōu)解函數(shù)MaxKnapsack在其中調(diào)用計算結(jié)點價值上界函數(shù)Bound，向子集樹和最大堆中插入結(jié)點函數(shù)AddLiveNode和釋放最大堆最大結(jié)點的函數(shù)DeleteMax，實現(xiàn)優(yōu)先級隊列。4、輸入數(shù)據(jù)到input.txt文件中。5、添加計算運行時間的代碼，計算不同規(guī)模數(shù)據(jù)的運行時間，并將結(jié)果輸出到output文件中。6、分析時間復(fù)雜度：在最壞的情況下所有的節(jié)點都入隊，最后一個節(jié)點才是最優(yōu)解，這種情況下時間復(fù)雜度是指數(shù)階。最好的

4、情況是只裝單位價值最大的物品，其余分支都不符合條件被截去這種情況下時間復(fù)雜度是常數(shù)時間。但分支限界法本質(zhì)上還是窮舉法，平均時間復(fù)雜度仍是指數(shù)階。關(guān)鍵代碼/物品類 class Object friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); public: int operator = a.d); private: int ID; /物品編號 float d; /單位重量價值 ; /樹結(jié)點類 class bbnode friend class Knap; friend Typep Knapsack(Typew *, Typep

5、*, Typew, int, int *); private: bbnode *parent; /指向父節(jié)點的指針 int LChild; ; /堆結(jié)點類 class HeapNode friend class Knap; friend class MaxHeap; public: operator Typep()constreturn uprofit; private: Typep uprofit, /結(jié)點的價值上界 profit; /結(jié)點所相應(yīng)的價值 Typew weight; /結(jié)點所相應(yīng)的重量 int level; /活結(jié)點在子集樹中所處的層序號 bbnode *elemPtr; /指

6、向該活結(jié)點在子集樹中相應(yīng)結(jié)點的指針 ; /最大堆類 class MaxHeap public: MaxHeap(int maxElem) HeapElem = new HeapNode* maxElem+1; /下標(biāo)為0的保留 capacity = maxElem; size = 0; void InsertMax(HeapNode *newNode); HeapNode DeleteMax(HeapNode* &N); private: int capacity; int size; HeapNode *HeapElem; ; /0-1背包問題的主類 class Knap friend Ty

7、pep Knapsack(Typew *, Typep *, Typew, int, int *); public: Typep MaxKnapsack(); private: MaxHeap *H; Typep Bound(int i); void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level); bbnode *E; /指向擴展結(jié)點的指針 Typew c; /背包容量 int n; /物品總數(shù) Typew *w; /物品重量數(shù)組（以單位重量價值降序） Typep *p; /物品價值數(shù)組（以單位重量價值降序） Type

8、w cw; /當(dāng)前裝包重量 Typep cp; /當(dāng)前裝包價值 int *bestx; /最優(yōu)解 ; void MaxHeap:InsertMax(HeapNode *newNode) int i = 1; for (i = +size; i/2 0 & HeapElemi/2-uprofit uprofit; i /= 2) HeapElemi = HeapElemi/2; HeapElemi = newNode; HeapNode MaxHeap:DeleteMax(HeapNode *&N) if(size 0 ) N = HeapElem1; int i = 1; while(i si

9、ze) if(i*2 +1) uprofit HeapElemi*2 +1-uprofit) HeapElemi = HeapElemi*2; i = i*2; else if(i*2 = size) HeapElemi = HeapElemi*2; i = i*2; else break; if(i size) HeapElemi = HeapElemsize; size-; return *N; Typep Knap:MaxKnapsack() H = new MaxHeap(10000); bestx = new int n+1; int i = 1; E = 0; cw = 0; cp

10、 = 0; Typep bestp = 0; Typep up = Bound(1); while (i != n+1) Typew wt = cw + wi; if(wt bestp) bestp = cp + pi; AddLiveNode(up, cp + pi, cw + wi, 1, i); up = Bound(i + 1); if(up = bestp) AddLiveNode(up, cp, cw, 0, i); HeapNode* N; H-DeleteMax(N); E = N-elemPtr; cw = N-weight; cp = N-profit; up = N-up

11、rofit; i = N-level + 1; for (int i = n; i 0; i-) bestxi = E-LChild; E = E-parent; return cp; Typep Knap:Bound(int i) Typew cleft = c - cw; Typep b = cp; while (i=n & wi = cleft) cleft -= wi; b += pi; i+; if(iparent=E; b-LChild=ch; HeapNode *N = new HeapNode; N-uprofit=up; N-profit=cp; N-weight=cw; N

12、-level=level; N-elemPtr=b; H-InsertMax(N); /Knapsack返回最大價值，最優(yōu)值保存在bestx Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx) Typew W = 0; Typep P = 0; Object *Q = new Objectn; for(int i =1; i=n; i+) Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if (W = c) for(int i =1; i=n; i+) bestxi

13、= pi; return P; for(int i = 1; in; i+) for(int j = 1; j= n-i; j+) if(Qj-1.d Qj.d) Object temp = Qj-1; Qj-1 = Qj; Qj = temp; Knap K; K.p = new Typep n+1; K.w = new Typew n+1; for(int i = 1; i=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; Typep bestp = K.MaxKnapsack();

14、 for(int i = 1; i=n; i+) bestxQi-1.ID = K.bestxi; delete Q; delete K.w; delete K.p; delete K.bestx; delete K.H; return bestp; 測試結(jié)果1、測試自己輸入的小規(guī)模數(shù)據(jù)2、測試隨機生成1003、隨機生成1000數(shù)據(jù)4、隨機生成1000數(shù)據(jù)實驗心得在做本次實驗之前，我對分支限界法的原理并不是很理解，經(jīng)過查看課件及網(wǎng)上查找資料，同時結(jié)合自己對回溯法等的理解，我對分支限界法有了一個較好的理解，知道了兩種主要的分支限界法及分支限界法如何應(yīng)用于解01背包問題。在查找資料的過程中，我查看

15、了許多網(wǎng)上的別人的代碼實現(xiàn)，結(jié)合課本上的代碼完成了該實驗。通過本次試驗，我基本上掌握了優(yōu)先隊列分支限界法解0-1背包問題的原理，同時鍛煉了自己動手編寫及調(diào)試代碼的能力，收獲良多。實驗得分助教簽名附錄：完整代碼#include #include#include#includeusing namespace std; ifstream in(input.txt);ofstream out(output.txt);typedef int Typew; typedef int Typep; /物品類 class Object friend Typep Knapsack(Typew *, Typep *

16、, Typew, int, int *); public: int operator = a.d); private: int ID; /物品編號 float d; /單位重量價值 ; /樹結(jié)點類 class bbnode friend class Knap; friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); private: bbnode *parent; /指向父節(jié)點的指針 int LChild; ; /堆結(jié)點類 class HeapNode friend class Knap; friend class MaxHeap

17、; public: operator Typep()constreturn uprofit; private: Typep uprofit, /結(jié)點的價值上界 profit; /結(jié)點所相應(yīng)的價值 Typew weight; /結(jié)點所相應(yīng)的重量 int level; /活結(jié)點在子集樹中所處的層序號 bbnode *elemPtr; /指向該活結(jié)點在子集樹中相應(yīng)結(jié)點的指針 ; /最大堆類 class MaxHeap public: MaxHeap(int maxElem) HeapElem = new HeapNode* maxElem+1; /下標(biāo)為0的保留 capacity = maxElem

18、; size = 0; void InsertMax(HeapNode *newNode); HeapNode DeleteMax(HeapNode* &N); private: int capacity; int size; HeapNode *HeapElem; ; /0-1背包問題的主類 class Knap friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); public: Typep MaxKnapsack(); private: MaxHeap *H; Typep Bound(int i); void AddLiv

19、eNode(Typep up, Typep cp, Typew cw, int ch, int level); bbnode *E; /指向擴展結(jié)點的指針 Typew c; /背包容量 int n; /物品總數(shù) Typew *w; /物品重量數(shù)組（以單位重量價值降序） Typep *p; /物品價值數(shù)組（以單位重量價值降序） Typew cw; /當(dāng)前裝包重量 Typep cp; /當(dāng)前裝包價值 int *bestx; /最優(yōu)解 ; void MaxHeap:InsertMax(HeapNode *newNode) int i = 1; for (i = +size; i/2 0 & Heap

20、Elemi/2-uprofit uprofit; i /= 2) HeapElemi = HeapElemi/2; HeapElemi = newNode; HeapNode MaxHeap:DeleteMax(HeapNode *&N) if(size 0 ) N = HeapElem1; int i = 1; while(i size) if(i*2 +1) uprofit HeapElemi*2 +1-uprofit) HeapElemi = HeapElemi*2; i = i*2; else if(i*2 = size) HeapElemi = HeapElemi*2; i = i*

21、2; else break; if(i size) HeapElemi = HeapElemsize; size-; return *N; Typep Knap:MaxKnapsack() H = new MaxHeap(10000); bestx = new int n+1; int i = 1; E = 0; cw = 0; cp = 0; Typep bestp = 0; Typep up = Bound(1); while (i != n+1) Typew wt = cw + wi; if(wt bestp) bestp = cp + pi; AddLiveNode(up, cp +

22、pi, cw + wi, 1, i); up = Bound(i + 1); if(up = bestp) AddLiveNode(up, cp, cw, 0, i); HeapNode* N; H-DeleteMax(N); E = N-elemPtr; cw = N-weight; cp = N-profit; up = N-uprofit; i = N-level + 1; for (int i = n; i 0; i-) bestxi = E-LChild; E = E-parent; return cp; Typep Knap:Bound(int i) Typew cleft = c

23、 - cw; Typep b = cp; while (i=n & wi = cleft) cleft -= wi; b += pi; i+; if(iparent=E; b-LChild=ch; HeapNode *N = new HeapNode; N-uprofit=up; N-profit=cp; N-weight=cw; N-level=level; N-elemPtr=b; H-InsertMax(N); /Knapsack返回最大價值，最優(yōu)值保存在bestx Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx

24、) Typew W = 0; Typep P = 0; Object *Q = new Objectn; for(int i =1; i=n; i+) Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if (W = c) for(int i =1; i=n; i+) bestxi = pi; return P; for(int i = 1; in; i+) for(int j = 1; j= n-i; j+) if(Qj-1.d Qj.d) Object temp = Qj-1; Qj-1 = Qj; Qj = temp; Knap K;

25、K.p = new Typep n+1; K.w = new Typew n+1; for(int i = 1; i=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; Typep bestp = K.MaxKnapsack(); for(int i = 1; i=n; i+) bestxQi-1.ID = K.bestxi; delete Q; delete K.w; delete K.p; delete K.bestx; delete K.H; return bestp; int main() cout請在input.txt文件中輸入物品數(shù)量、背包容量N; Typew c; /背包容量 inc; int bestxN+1; /最優(yōu)解 int bestp; /最優(yōu)值 Typep pN+1;/物品價值 Typew wN+1;/物品重量 cout在input.txt文件中讀取的物品總數(shù)N = N,背包容量C = cendl; cout請選擇生成數(shù)據(jù)的規(guī)模大?。?00請輸入1,2000請輸入2，20000請輸入3x;if(x=1)ofstream in1(input1.txt);srand(time(NULL); int n=200; int *a=n