實(shí)驗(yàn) 4 用分支限界法實(shí)現(xiàn)0-1背包問(wèn)題.doc

實(shí)驗(yàn)四 用分支限界法實(shí)現(xiàn)0-1背包問(wèn)題一實(shí)驗(yàn)?zāi)康?1.熟悉分支限界法的基本原理。2.通過(guò)本次實(shí)驗(yàn)加深對(duì)分支限界法的理解。二實(shí)驗(yàn)內(nèi)容及要求內(nèi)容：.給定n種物品和一個(gè)背包。物品i的重量是w，其價(jià)值為v，背包容量為c。問(wèn)應(yīng)該如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?要求：使用優(yōu)先隊(duì)列式分支限界法算法編程，求解0-1背包問(wèn)題三程序列表#include #include using namespace std;#define N 100 class HeapNode /定義HeapNode結(jié)點(diǎn)類(lèi) public:double upper, price, weight; /upper為結(jié)點(diǎn)的價(jià)值上界，price是結(jié)點(diǎn)所對(duì)應(yīng)的價(jià)值，weight為結(jié)點(diǎn)所相應(yīng)的重量 int level, xN; /活節(jié)點(diǎn)在子集樹(shù)中所處的層序號(hào) ;double MaxBound(int i);double Knap();void AddLiveNode(double up, double cp, double cw, bool ch, int level);/up是價(jià)值上界，cp是相應(yīng)的價(jià)值，cw是該結(jié)點(diǎn)所相應(yīng)的重量，ch是ture or falsestack High; /最大隊(duì)High double wN, pN; /把物品重量和價(jià)值定義為雙精度浮點(diǎn)數(shù) double cw, cp, c; /cw為當(dāng)前重量，cp為當(dāng)前價(jià)值，定義背包容量為cint n; /貨物數(shù)量為int main()cout 請(qǐng)輸入背包容量： c;cout 請(qǐng)輸入物品的個(gè)數(shù)： n;cout 請(qǐng)按順序分別輸入物品的重量： endl;int i;for (i = 1; i wi; /輸入物品的重量 cout 請(qǐng)按順序分別輸入物品的價(jià)值： endl;for (i = 1; i pi; /輸入物品的價(jià)值 cout 最優(yōu)值為：;cout Knap() endl; /調(diào)用knap函數(shù) 輸出最大價(jià)值 return 0;double MaxBound(int k) /MaxBound函數(shù)求最大上界 double cleft = c - cw; /剩余容量double b = cp; /價(jià)值上界 while (k = n&wk = cleft) /以物品單位重量?jī)r(jià)值遞減裝填剩余容量 cleft -= wk;b += pk;k+;if (k = n)b += pk / wk * cleft; /裝填剩余容量裝滿(mǎn)背包 return b;void AddLiveNode(double up, double cp, double cw, bool ch, int lev) /將一個(gè)新的活結(jié)點(diǎn)插入到子集數(shù)和最大堆High中 HeapNode be;be.upper = up;be.price = cp;be.weight = cw;be.level = lev;if (lev = n)High.push(be);/調(diào)用stack頭文件的push函數(shù) double Knap() /優(yōu)先隊(duì)列分支限界法，返回最大價(jià)值，bestx返回最優(yōu)解 int i = 1;cw = cp = 0;double bestp = 0; /best為當(dāng)前最優(yōu)值 double up = MaxBound(1);/價(jià)值上界/搜索子集空間樹(shù)while (1) /非葉子結(jié)點(diǎn) double wt = cw + wi;if (wt bestp)bestp = cp + pi;AddLiveNode(up, cp + pi, cw + wi, true, i + 1);up = MaxBound(i + 1);if (up = bestp) /右子數(shù)可能含最優(yōu)解 AddLiveNode(up, cp, cw, false, i + 1);if (High.empty()return bestp;HeapNode node = High.top(); /取下