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

《0-1背包问题的分支限界法源代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、//#include"stdafx.h"#include#include#include#includeusingnamespacestd;int*x;structnode//结点表结点数据结构{node*parent;//父结点指针node*next;//后继结点指针intlevel;//结点的层intbag;//节点的解intcw;//当前背包装载量intcp;//当前背包价值floatub;//结点的上界值};//类Knap中的数据记录解空间树中的结

2、点信息，以减少参数传递及递归调用所需的栈空间classKnap{private:structnode*front,//队列队首*bestp,*first;//解结点、根结点int*p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系longlbestp;//背包容量最优解public:voidSort();Knap(int*pp,int*ww,intcc,intnn);~Knap();floatBound(inti,intcw,intcp);//计算上界限node*nnoder(node*pa,int

3、ba,floatuub);//生成一个结点ba=1生成左节点ba=0生成右节点voidaddnode(node*nod);//向队列中添加活结点voiddeletenode(node*nod);//将结点从队列中删除structnode*nextnode();//取下一个节点voiddisplay();//输出结果voidsolvebag();//背包问题求解};//按物品单位重量的价值排序voidKnap::Sort(){inti,j,k,kkl;floatminl;for(i=1;i

4、]/w[i];k=0;for(j=1;j<=n-i;j++){if(minl<1.0*p[j]/w[j]){minl=1.0*p[j]/w[j];swap(p[k],p[j]);swap(w[k],w[j]);swap(M[k],M[j]);k=j;}}}}Knap::Knap(int*pp,int*ww,intcc,intnn){inti;n=nn;c=cc;p=newint[n];w=newint[n];M=newint[n];for(i=0;i

5、用M数组记录大小顺序关系}front=newnode[1];front->next=NULL;lbestp=0;bestp=newnode[1];bestp=NULL;Sort();}Knap::~Knap(){delete[]first;delete[]front;delete[]bestp;delete[]p;delete[]w;}//取上限最大结点node*Knap::nextnode(){node*p=front->next;front->next=p->next;return(p);}//将一个新的结点插入到子集树和

6、优先队列中node*Knap::nnoder(structnode*pa,intba,floatuub){//生成一个新结点node*nodell=new(node);nodell->parent=pa;nodell->next=NULL;nodell->level=(pa->level)+1;nodell->bag=ba;nodell->ub=uub;if(ba==1){nodell->cw=pa->cw+w[pa->level];nodell->cp=pa->cp+p[pa->level];}else{nodell->cw

7、=pa->cw;nodell->cp=pa->cp;}return(nodell);}//将结点加入优先队列voidKnap::addnode(node*no){node*p=front->next,*next1=front;floatub=no->ub;while(p!=NULL){if(p->ubnext=p;next1->next=no;break;}next1=p;p=p->next;}if(p==NULL){next1->next=no;}}//计算结点所相应价值的上界floatKnap::Boun

8、d(inti,intcw,intcp){intcleft=c-cw;//剩余容量floatb=(float)cp;//价值上界//以物品单位重量价值减序装填剩余容量while(i