1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)分支限界法求0-1背包問題實驗程序以及代碼（C+）本程序中（規(guī)定物品數(shù)量為3，背包容量為30，輸入為6個數(shù)，前3個為物品重量，后3個數(shù)為物品價值）：代碼：#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)

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

3、量）endl;int i; for(i=1;iwi; /輸入3個物品的重量 cout請按順序輸入3個物品的價值：（按回車鍵區(qū)分每個物品的價值）endl;for(i=1;ipi; /輸入3個物品的價值 cout最大價值為：;coutKnap()endl; /調(diào)用knap函數(shù) 輸出最大價值 return 0; double MaxBound(int j) /MaxBound函數(shù)求最大上界 double left=c-cw,b=cp; /剩余容量和價值上界 while(j=n&wj=left) /以物品單位重量價值遞減裝填剩余容量 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) /將一個新的活結(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,up=MaxBound(1); /調(diào)用MaxBound求出價值上界，best為最優(yōu)值 while(1) /非葉子結(jié)點 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(); /取下一擴展結(jié)點