分支界限法解0-1背包问题实验报告.doc

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

1、实验5分支界限法解0-1背包问题一、实验要求1．要求用分支界限法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP+VC++6.0三、源程序#include"stdafx.h"#include#include#include#includeusingnamespacestd;int*x;structnode//结点表结点数据结构{node*parent;//父结点指针node*nex

2、t;//后继结点指针intlevel;//结点的层intbag;//节点的解intcw;//当前背包装载量intcp;//当前背包价值floatub;//结点的上界值};//类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间classKnap{private:structnode*front,//队列队首*bestp,*first;//解结点、根结点int*p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系longlbestp;//背包容量最优解public:voidSort();Knap(int*pp

3、,int*ww,intcc,intnn);~Knap();floatBound(inti,intcw,intcp);//计算上界限node*nnoder(node*pa,intba,floatuub);//生成一个结点ba=1生成左节点ba=0生成右节点voidaddnode(node*nod);//向队列中添加活结点voiddeletenode(node*nod);//将结点从队列中删除structnode*nextnode();//取下一个节点voiddisplay();//输出结果voidsolvebag();//背包问题求解};//按物品单位重量的价值

4、排序voidKnap::Sort(){inti,j,k,kkl;floatminl;for(i=1;i

5、nt[n];for(i=0;inext=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->nex

6、t=p->next;return(p);}//将一个新的结点插入到子集树和优先队列中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->lev

7、el];}else{nodell->cw=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::B

8、ound(inti,intcw,int