分支限界法求0-1背包問題實(shí)驗(yàn)程序以及代碼(c)

1、分支限界法求0；背包問題實(shí)驗(yàn)程序以及代碼(C+)本程序中(規(guī)定物品 數(shù)量為3,背包容量為30,輸入為6個(gè)數(shù)，前3個(gè)為物品重量，后3個(gè)數(shù)為物 品價(jià)值)：代碼：#include<iostream>#include<stack> using namespace std;#define N 100 classHeapNode 定義 HeapNode 結(jié)點(diǎn)類 ( public: doubleupper,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)在子集樹中所處的層序號(hào)；do

2、uble MaxBound(int i);double Knap();void AddLiveNode(double up,double cp,double cw,bool ch,int level); stack<HeapNode> High; 最大隊(duì) Highdouble wN,pN; 把物品重量和價(jià)值定義為雙精度浮點(diǎn)數(shù)double cw,cp,c=30;cw為當(dāng)前重量，cp為當(dāng)前價(jià)值，定義背包容量為 30int n=3;貨物數(shù)量為3int main()cout<<“請(qǐng)按順序輸入3個(gè)物品的重量：(按回車鍵區(qū)分每個(gè)物品的重量) "«endl;int

3、 i;for(i=l;i<=n;i+)cin»wi; 輸入3個(gè)物品的重量cout<<“請(qǐng)按順序輸入3個(gè)物品的價(jià)值：(按回車鍵區(qū)分每個(gè)物品的價(jià)值) "«endl;for(i=l;i<=n;i+)cin»pi; 輸入3個(gè)物品的價(jià)值cout""最大價(jià)值為：”；cout«Knap()«endl; 調(diào)用knap函數(shù)輸出最大價(jià)值return 0;)double MaxBound(int j) /MaxBound 函數(shù)求最大上界double1/4Ieft=c-cw,b=cp;剩余容量和價(jià)值上界while(

4、j<=n&&wj<=le代)以物品單位重量?jī)r(jià)值遞減裝填剩余容量(left-=wj;b+=pj；j+；)if(j<=n)b+=pj/wj*left;裝填剩余容量裝滿背包return b;)void AddLiveNode(double up,double cp,double cw,bool chjnt 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頭文件的pus

5、h函數(shù)double Knap()優(yōu)先隊(duì)列分支限界法，返回最大價(jià)值，bestx返回最優(yōu)解int i=l; cw=cp=0; doublebestp=0,up=MaxBound(l); 調(diào)用 MaxBound 求出價(jià)值上界，best 為最優(yōu) 值while(l)非葉子結(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/trgi+l);)up=MaxBound(i+l);if(up>=bestp)右子數(shù)可能含最優(yōu)解AddLiveNode(up,cp,cw,false,i+1);if(High.empty() return bestp;HeapNode node=High.top(); 取下一擴(kuò)展結(jié)點(diǎn)