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

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

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

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

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

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

6、向該活結(jié)點(diǎn)在子集樹中相應(yīng)結(jié)點(diǎn)的指針 ; /最大堆類 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; /指向擴(kuò)展結(jié)點(diǎn)的指針 Typew c; /背包容量 int n; /物品總數(shù) Typew *w; /物品重量數(shù)組（以單位重量?jī)r(jià)值降序） Typep *p; /物品價(jià)值數(shù)組（以單位重量?jī)r(jià)值降序） Type

8、w cw; /當(dāng)前裝包重量 Typep cp; /當(dāng)前裝包價(jià)值 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返回最大價(jià)值，最優(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; 測(cè)試結(jié)果1、測(cè)試自己輸入的小規(guī)模數(shù)據(jù)2、測(cè)試隨機(jī)生成1003、隨機(jī)生成1000數(shù)據(jù)4、隨機(jī)生成1000數(shù)據(jù)實(shí)驗(yàn)心得在做本次實(shí)驗(yàn)之前，我對(duì)分支限界法的原理并不是很理解，經(jīng)過查看課件及網(wǎng)上查找資料，同時(shí)結(jié)合自己對(duì)回溯法等的理解，我對(duì)分支限界法有了一個(gè)較好的理解，知道了兩種主要的分支限界法及分支限界法如何應(yīng)用于解01背包問題。在查找資料的過程中，我查看

15、了許多網(wǎng)上的別人的代碼實(shí)現(xiàn)，結(jié)合課本上的代碼完成了該實(shí)驗(yàn)。通過本次試驗(yàn)，我基本上掌握了優(yōu)先隊(duì)列分支限界法解0-1背包問題的原理，同時(shí)鍛煉了自己動(dòng)手編寫及調(diào)試代碼的能力，收獲良多。實(shí)驗(yàn)得分助教簽名附錄：完整代碼#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; /物品編號(hào) float d; /單位重量?jī)r(jià)值 ; /樹結(jié)點(diǎn)類 class bbnode friend class Knap; friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); private: bbnode *parent; /指向父節(jié)點(diǎn)的指針 int LChild; ; /堆結(jié)點(diǎn)類 class HeapNode friend class Knap; friend class MaxHeap

17、; public: operator Typep()constreturn uprofit; private: Typep uprofit, /結(jié)點(diǎn)的價(jià)值上界 profit; /結(jié)點(diǎn)所相應(yīng)的價(jià)值 Typew weight; /結(jié)點(diǎn)所相應(yīng)的重量 int level; /活結(jié)點(diǎn)在子集樹中所處的層序號(hào) bbnode *elemPtr; /指向該活結(jié)點(diǎn)在子集樹中相應(yīng)結(jié)點(diǎn)的指針 ; /最大堆類 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; /指向擴(kuò)展結(jié)點(diǎn)的指針 Typew c; /背包容量 int n; /物品總數(shù) Typew *w; /物品重量數(shù)組（以單位重量?jī)r(jià)值降序） Typep *p; /物品價(jià)值數(shù)組（以單位重量?jī)r(jià)值降序） Typew cw; /當(dāng)前裝包重量 Typep cp; /當(dāng)前裝包價(jià)值 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返回最大價(jià)值，最優(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請(qǐng)?jiān)趇nput.txt文件中輸入物品數(shù)量、背包容量N; Typew c; /背包容量 inc; int bestxN+1; /最優(yōu)解 int bestp; /最優(yōu)值 Typep pN+1;/物品價(jià)值 Typew wN+1;/物品重量 cout在input.txt文件中讀取的物品總數(shù)N = N,背包容量C = cendl; cout請(qǐng)選擇生成數(shù)據(jù)的規(guī)模大?。?00請(qǐng)輸入1,2000請(qǐng)輸入2，20000請(qǐng)輸入3x;if(x=1)ofstream in1(input1.txt);srand(time(NULL); int n=200; int *a=n