0-1背包問題的分支限界法源代碼

1、/#includestdafx.h#include#include#include#includeusingnamespacestd;int*x;structnode結點表結點數據結構(node.parent;父結點指針node*next;后繼結點指針intlevel;結點的層intbag;節(jié)點的解intcw;當前背包裝載量intcp;當前背包價值floatub;結點的上界值；類Kn叩中的數據記錄解空間樹中的結點信息，以減少參數傳遞及遞歸調用所需的棧空間classKnap(private:structnode*front,隊列隊首*bestp,*first;解結點、根結點int*p,*w,n,

2、c,*M;背包價值、重量、物品數、背包容量、記錄大小順序關系longIbestp;背包容量最優(yōu)解public:voidSort();Knap(int*pp,int*ww,intccjntnn);Knap();floatBound(intijntcwjntcp);計算上界限node*nnoder(node*pa,intbajloatuub);生成一個結點ba=l生成左節(jié)點ba=0生成右節(jié)點voidaddnode(node*nod);向隊列中添加活結點voiddeletenode(node*nod);將結點從隊列中刪除structnode*nextnode();/取下一個節(jié)點voiddisplay

3、。;輸出結果voidsolvebag();背包問題求解);按物品單位重量的價值排序voidKnap:Sort()intijkkkl;floatmini;for(i=l;in;i+)minl=1.0*pi/wi;k=0;for(j=l;j=n-i;j+)if(minl1.0*pj/wj)minl=1.0*pj/wj;swap(pk/pj);swap(wk,wj);swap(Mk,Mj);k=j；)Knap:Knap(int*pp,int*ww,intccjntnn)(inti;n=nn;c=cc;p=newintn;w=newintn;M=newintn;for(i=0;inext=NULL;l

4、bestp=0;bestp=newnodel;bestp=NULL;Sort();)Knap:Knap()deletefront;deletebestp;deletep;deletew;)取上限最大結點node*Knap:nextnode()(node*p=front-next;front-next=p-next;return(p);將一個新的結點插入到子集樹和優(yōu)先隊列中node*Knap:nnoder(structnode*pa,intba,floatuub)生成一個新結點node*nodell=new(node);nodell-parent=pa;nodell-next=NULL;node

5、ll-level=(pa-level)+l;nodell-bag=ba;nodell-ub=uub;if(ba=l)nodell-cw=pa-cw+wpa-level;nodell-cp=pa-cp+ppa-level;elsenodell-cw=pa-cw;nodell-cp=pa-cp;return(nodell);將結點加入優(yōu)先隊列voidKnap:addnode(node*no)node*p=front-next/nextl=front;floatub=no-ub;while(p!=NULL)if(p-ubnext=p;nextl-next=no;break;nextl=p;p=p-n

6、ext;if(p=NULL)nextl-next=no;)/計算結點所相應價值的上界floatKnap:Bound(intijntcvintcp)(intcleft=c-cw;剩余容量floatb=(float)cp;價值上界以物品單位重量價值減序裝填剩余容量while(in&wi=cleft)cleft-=wi;b+=pi；i+；)裝填剩余容量裝滿背包if(in)b+=1.0*pi/wi*cleft;returnb;)計算最優(yōu)值和變量值voidKnap:display()(inti;coutendl;coutcv當前最優(yōu)價值為:=l;i-)xMi-l=bestp-bag;bestp=best

7、p-parent;cout變量值x=H;for(i=l;iparent=NULL;first-next=NULL;first-level=O;用level記錄結點的層first-cw=0;first-cp=O;first-bag=O;ubb=Bound(0,0,0)；first-ub=ubb;front-next=first;while(front-next!=NULL)aa=nextnode();i=aa-level;當葉子節(jié)點處的解最優(yōu)解時，更新最優(yōu)解if(i=n-l)if(aa-cw+wicp+pi)lbestp)lbestp=aa-cp+pi;bestp=nnoder(aa,l,(fl

8、oat)lbestp);將一個新的結點插入到子集樹和優(yōu)先隊列中)if(long)(aa-cp)lbestp)lbestp=aa-cp;bestp=nnoder(aa,0,(float)lbestp);)非葉子結點，遞歸調用Bound函數計算上界if(aa-cw+wicw+wi,aa-cp+pi)(float)lbestp)ubb=Bound(i/aa-cw+wi/aa-cp+pi);addnode(nnoder(aa,l,ubb);將結點加入到優(yōu)先隊列中)ubb=ubb=Bound(i,aa-cw,aa-cp);if(ubblbestp)addnode(nnoder(aa,0,ubb);)display();)intmain()(intczn;inti=O;int*p;int*w;coutendl;coukv*11c分支限界法解0-1背包問題*”endl;coutendl;cout“請輸入物品數量n=;cinn;coutendl;cout”請輸入背包容量C=;cinc;coutendl;x=newintn;變量值p=newintn;物品價值w=newintn;物品重量8ut請分別輸入這個