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

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