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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)分支限界法求0-1背包問題實(shí)驗(yàn)程序以及代碼（C+）本程序中（規(guī)定物品數(shù)量為3，背包容量為30，輸入為6個(gè)數(shù)，前3個(gè)為物品重量，后3個(gè)數(shù)為物品價(jià)值）：代碼：#include #include using namespace std; #define N 100 class HeapNode /定義HeapNode結(jié)點(diǎn)類 public: double upper,price,weight; /upper為結(jié)點(diǎn)的價(jià)值上界，price是結(jié)點(diǎn)所對(duì)應(yīng)的價(jià)值，weight為結(jié)點(diǎn)所相應(yīng)

2、的重量 int level,xN; /活節(jié)點(diǎn)在子集樹中所處的層序號(hào) ; double MaxBound(int i); double Knap(); void AddLiveNode(double up,double cp,double cw,bool ch,int level); stack High; /最大隊(duì)High double wN,pN; /把物品重量和價(jià)值定義為雙精度浮點(diǎn)數(shù)double cw,cp,c=30; /cw為當(dāng)前重量，cp為當(dāng)前價(jià)值，定義背包容量為30 int n=3; /貨物數(shù)量為3 int main() cout請(qǐng)按順序輸入3個(gè)物品的重量：（按回車鍵區(qū)分每個(gè)物品的重

3、量）endl;int i; for(i=1;iwi; /輸入3個(gè)物品的重量 cout請(qǐng)按順序輸入3個(gè)物品的價(jià)值：（按回車鍵區(qū)分每個(gè)物品的價(jià)值）endl;for(i=1;ipi; /輸入3個(gè)物品的價(jià)值 cout最大價(jià)值為：;coutKnap()endl; /調(diào)用knap函數(shù) 輸出最大價(jià)值 return 0; double MaxBound(int j) /MaxBound函數(shù)求最大上界 double left=c-cw,b=cp; /剩余容量和價(jià)值上界 while(j=n&wj=left) /以物品單位重量價(jià)值遞減裝填剩余容量 left-=wj; b+=pj; j+; if(j=n) b+=pj

4、/wj*left; /裝填剩余容量裝滿背包 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,up=MaxBound(1); /調(diào)用MaxBound求出價(jià)值上界，best為最優(yōu)值 while(1) /非葉子結(jié)點(diǎn) double wt=cw+wi; if(wtbestp) 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(); /取下一擴(kuò)展結(jié)點(diǎn)