0-1背包问题的分支限界法源代码

1、/#includestdafx.h#include#include#include#includeusingnamespacestd;int*x;structnode结点表结点数据结构(node.parent;父结点指针node*next;后继结点指针intlevel;结点的层intbag;节点的解intcw;当前背包装载量intcp;当前背包价值floatub;结点的上界值；类Kn叩中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间classKnap(private:structnode*front,队列队首*bestp,*first;解结点、根结点int*p,*w,n,

2、c,*M;背包价值、重量、物品数、背包容量、记录大小顺序关系longIbestp;背包容量最优解public:voidSort();Knap(int*pp,int*ww,intccjntnn);Knap();floatBound(intijntcwjntcp);计算上界限node*nnoder(node*pa,intbajloatuub);生成一个结点ba=l生成左节点ba=0生成右节点voidaddnode(node*nod);向队列中添加活结点voiddeletenode(node*nod);将结点从队列中删除structnode*nextnode();/取下一个节点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);将一个新的结点插入到子集树和优先队列中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);将结点加入优先队列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;)计算最优值和变量值voidKnap:display()(inti;coutendl;coutcv当前最优价值为:=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;当叶子节点处的解最优解时，更新最优解if(i=n-l)if(aa-cw+wicp+pi)lbestp)lbestp=aa-cp+pi;bestp=nnoder(aa,l,(fl

8、oat)lbestp);将一个新的结点插入到子集树和优先队列中)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);将结点加入到优先队列中)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请分别输入这个