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

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

2、uble upper, price, weight; /upper 為結(jié)點(diǎn)的價值上界，price 是結(jié)點(diǎn)所對應(yīng)的價值，weight為結(jié)點(diǎn)所相應(yīng)的重量int level, x N;/ 活節(jié)點(diǎn)在子集樹中所處的層序號;double MaxBound(int i);double Knap();void AddLiveNode( double up, double cp, double cw, bool ch, int level); /up 是價值上界，cp 是相應(yīng)的價值，cw是該結(jié)點(diǎn)所相應(yīng)的重量，ch 是 ture or falsestack <HeapNode> High; / 最大隊(duì)

3、 Highdouble w N, p N; / 把物品重量和價值定義為雙精度浮點(diǎn)數(shù)double cw, cp, c; /cw 為當(dāng)前重量，cp 為當(dāng)前價值，定義背包容量為cint n; / 貨物數(shù)量為 int main() cout << "請輸入背包容量：" << endl;cin >> c;cout << "請輸入物品的個數(shù)：" << endl;cin >> n;cout << "請按順序分別輸入物品的重量：" << endl;int

4、i;for (i = 1; i <= 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ù)求最大上界d

5、ouble cleft = c - cw;/ 剩余容量double 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é)點(diǎn) 插入到子集數(shù)和最大堆High 中HeapN

6、odebe;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ì)列分支限界法，返回最大價值，bestx 返回最優(yōu)解int i = 1;cw = cp = 0;double bestp = 0; /best 為當(dāng)前最優(yōu)值double up = MaxBound(1); / 價值上界 / 搜索子集空間樹while (1)/ 非葉子結(jié)點(diǎn)double wt = cw + wi; if (wt <= c) / 左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn)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()return bestp;HeapNoden