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

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

2、le upper,price,weight; /upper 為結(jié)點的價值上界， price是結(jié)點所對應的價值， weight為結(jié)點所相應的重量int level, xN;/活節(jié)點在子集樹中所處的層序號;double MaxBound( int i);double Knap();voidAddLiveNode(double up,double cp,double cw, bool ch, intlevel); /up 是價值上界，cp 是相應的價值， cw 是該結(jié)點所相應的重量，ch 是 ture or false.stack <HeapNode> High;/ 最大隊 Highdo

3、ublew N, pN;/ 把物品重量和價值定義為雙精度浮點數(shù)doublecw, cp, c;/cw 為當前重量， cp 為當前價值，定義背包容量為cintn;/ 貨物數(shù)量為intmain()cout<< " 請輸入背包容量："<< endl;cin>> c;cout<< " 請輸入物品的個數(shù)：" << endl;cin>> n;cout<< " 請按順序分別輸入物品的重量：" << endl;inti;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ù) 輸出最大價值return0;double MaxBound( intk)/MaxBound 函數(shù)求最大上界double cleft = c - cw;/ 剩余容量do

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

6、.level =lev ;if( lev <= n)High.push(be); / 調(diào)用 stack 頭文件的 push 函數(shù) double Knap()/ 優(yōu)先隊列分支限界法，返回最大價值，bestx 返回最優(yōu)解inti = 1;cw = cp = 0;.double bestp = 0;/best為當前最優(yōu)值double up = MaxBound(1);/ 價值上界/ 搜索子集空間樹while (1)/ 非葉子結(jié)點double wt = cw + wi;if(wt <= c)/ 左兒子結(jié)點為可行結(jié)點if(cp + pi>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()returnbestp;HeapNodenode =