《分支界限法解0-1背包问题实验报告(共7页).doc》由会员分享，可在线阅读，更多相关《分支界限法解0-1背包问题实验报告(共7页).doc（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上实验5 分支界限法解0-1背包问题一 、实验要求1 要求用分支界限法求解0-1背包问题；2 要求交互输入背包容量，物品重量数组，物品价值数组；3 要求显示结果。二 、实验仪器和软件平台仪器 ：带usb接口微机软件平台：WIN-XP + VC+6.0三 、源程序#include stdafx.h#include#include#include#includeusing namespace std;int *x;struct node /结点表结点数据结构 node *parent;/父结点指针 node *next; /后继结点指针 int level;/结点的层 in
2、t 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();f
3、loat 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;flo
4、at 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()del
5、ete 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
6、-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-
7、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-ba
8、g;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)
9、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(ub
10、blbestp)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 intn; /物品重量cout请分别输入这n个物品的重量W:endl;for(i=0;iwi; coutendl;cout请输入这n个物品的价值P:endl;for(i=0;ipi;Knap knbag(
11、p,w,c,n);knbag.solvebag();getch();return 0;四 、运行结果五 、实验小结回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。专心-专注-专业