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

/#include stdafx.h#include#include#include#includeusing namespace std;int *x;struct node /结点表结点数据结构 node *parent;/父结点指针 node *next; /后继结点指针 int level;/结点的层 int bag;/节点的解 int cw;/当前背包装载量 int cp;/当前背包价值 float ub; /结点的上界值;/类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间class Knap private: struct node *front, /队列队首 *bestp,*first; /解结点、根结点 int *p,*w,n,c,*M;/背包价值、重量、物品数、背包容量、记录大小顺序关系 long lbestp;/背包容量最优解 public:void Sort();Knap(int *pp,int *ww,int cc,int nn);Knap();float Bound(int i,int cw,int cp);/计算上界限node *nnoder(node *pa,int ba,float uub);/生成一个结点 ba=1生成左节点 ba=0生成右节点void addnode(node *nod);/向队列中添加活结点void deletenode(node *nod);/将结点从队列中删除struct node *nextnode(); /取下一个节点void display(); /输出结果void solvebag(); /背包问题求解;/按物品单位重量的价值排序void Knap:Sort()int i,j,k,kkl;float minl; for(i=1;in;i+) minl=1.0*pi/wi;k=0;for(j=1;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,int cc,int nn) int i;n=nn;c=cc;p=new intn;w=new intn;M=new intn;for(i=0;inext=NULL;lbestp=0;bestp=new node1;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);/将一个新的结点插入到子集树和优先队列中node * Knap:nnoder(struct node *pa,int ba,float uub)/生成一个新结点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+wpa-level;nodell-cp=pa-cp+ppa-level ;else nodell-cw=pa-cw;nodell-cp=pa-cp;return(nodell);/将结点加入优先队列void Knap:addnode(node *no)node *p=front-next,*next1=front;float ub=no-ub;while(p!=NULL)if(p-ubnext=p;next1-next=no;break;next1=p;p=p-next;if(p=NULL)next1-next=no;/ 计算结点所相应价值的上界float Knap:Bound(int i,int cw,int cp) int cleft=c-cw; /剩余容量 float b=(float)cp; /价值上界 /以物品单位重量价值减序装填剩余容量 while (in&wi=cleft) cleft-=wi; b+=pi; i+; /装填剩余容量装满背包 if (in) b+=1.0*pi/wi*cleft; return b;/计算最优值和变量值void Knap:display()int i;coutendl;cout当前最优价值为:lbestp=1;i-) xMi-1=bestp-bag;bestp=bestp-parent;cout变量值 x = ;for(i=1;i=n;i+)coutxi-1;coutparent=NULL;first-next=NULL;first-level=0; /用level记录结点的层first-cw=0;first-cp=0;first-bag=0;ubb=Bound(0,0,0);first-ub=ubb;front-next=first;while(front-next!=NULL)aa=nextnode();i=aa-level;/当叶子节点处的解最优解时，更新最优解if(i=n-1) if(aa-cw+wicp+pi)lbestp)lbestp=aa-cp+pi;bestp=nnoder(aa,1,(float)lbestp);/将一个新的结点插入到子集树和优先队列中if(long)(aa-cp)lbestp) lbestp=aa-cp;bestp=nnoder(aa,0,(float)lbestp);/非叶子结点，递归调用Bound函数计算上界if(icw+wicw+wi,aa-cp+pi)(float)lbestp)ubb=Bound(i,aa-cw+wi,aa-cp+pi);addnode(nnoder(aa,1,ubb);/将结点加入到优先队列中ubb=ubb=Bound(i,aa-cw,aa-cp);if(ubblbestp)addnode(nnoder(aa,0,ubb);display();int main()int c,n;int i=0;int *p;int *w;coutendl;cout|*分支限界法解0-1背包问题*| endl;coutendl;coutn; coutendl;coutc;coutendl;x=new intn; /变量值p=new intn; /物品价值w=new