實驗用分支限界法實現(xiàn)背包問題

1、實驗四 用分支限界法實現(xiàn)0-1背包問題一. 實驗目的1. 熟悉分支限界法的基本原理。2. 通過本次實驗加深對分支限界法的理解。？二. 實驗內(nèi)容及要求內(nèi)容：給定n種物品和一個背包。物品i的重量是w,其價值為v,背包容量為c。問應該如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？要求：使用優(yōu)先隊列式分支限界法算法編程，求解0-1背包問題三. 程序列表#inelude <iostream>#include <stack>using namespacestd;#defi ne N100class HeapNode / 定義 HeapNode結(jié)點類 publicdoubl

2、e upper, price, weight;/upper為結(jié)點的價值上界，price是結(jié)點所對應的價值，weight為結(jié)點所相應的重量int level, x N;/活節(jié)點在子集樹中所處的層序號；double MaxBound(int i);double Kn ap();void AddLiveNode( double up, double cp, double cw, bool ch, int level); /up 是價值上界，cp是相應的價值，cw是該結(jié)點所相應的重量，ch是ture or falsestack <HeapNod> High; / 最大隊 Highdoubl

3、e w N, p N； /把物品重量和價值定義為雙精度浮點數(shù)double cw, cp, c; /cw為當前重量，cp為當前價值，定義背包容量為 cint n; /貨物數(shù)量為int main()cout << "請輸入背包容量："<< endl;cin >> c;cout << "請輸入物品的個數(shù):II<< en dl;cin >> n;cout << "請按順序分別輸入物品的重量："<< endl;int i;for (i = 1; i <=

4、 n; i+)cin >> wi;/輸入物品的重量cout << "請按順序分別輸入物品的價值："<< endl;for (i = 1; i <= n; i+)cin >> pi;/輸入物品的價值cout << "最優(yōu)值為："cout << Knap() << endl; /調(diào)用knap函數(shù) 輸出最大價值return 0;double MaxBound(int k) /MaxBound 函數(shù)求最大上界double cleft = c - cw;/ 剩余容量doubl

5、e b = cp;/價值上界while ( k <= n&&w k <= cleft)/以物品單位重量價值遞減裝填剩余容量cleft -= w k;b += p k;k+;if ( k <= n)b += p k / w k * cleft;/裝填剩余容量裝滿背包return b;/將一個新void AddLiveNode( double up, double cp, double cw, bool ch, int lev)的活結(jié)點插入到子集數(shù)和最大堆High中HeapNodeoe;be.upper = up;be.price = cp;be.weight =

6、 cw;be.level = lev ;if ( lev <= n)High.push(be);/調(diào)用stack頭文件的push函數(shù)double Knap() /優(yōu)先隊列分支限界法，返回最大價值，bestx返回最優(yōu)解int i = 1;cw = cp = 0;double bestp = 0; /best 為當前最優(yōu)值double up = MaxBound(1); / 價值上界/搜索子集空間樹while (1)/非葉子結(jié)點double wt = cw + wi;if (cp + pi>bestp)bestp = cp + pi;AddLiveNode(up, cp + pi, cw + wi,true , i + 1);up = MaxBou nd(i + 1);if (up >= bestp) /右子數(shù)可能含最優(yōu)解AddLiveNode(up, cp, cw, false , i + 1);if (High.emptyO)return bestp;HeapNodenode =