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

实验5分支界限法解0-1背包问题一、实验要求1．要求用分支界限法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP+VC++6.0三、源程序#includestdafx.h#includeiostream#includecstdio#includeconio.h#includeiomanipusingnamespacestd;int*x;structnode//结点表结点数据结构{node*parent;//父结点指针node*next;//后继结点指针intlevel;//结点的层intbag;//节点的解intcw;//当前背包装载量intcp;//当前背包价值floatub;//结点的上界值};//类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间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,intba,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;in;i++){minl=1.0*p[i]/w[i];k=0;for(j=1;j=n-i;j++){if(minl1.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;in;i++){p[i]=pp[i];w[i]=ww[i];M[i]=i;//用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);}//将一个新的结点插入到子集树和优先队列中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=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-ubub){no-next=p;next1-next=no;break;}next1=p;p=p-next;}if(p==NULL){next1-next=no;}}//计算结点所相应价值的上界floatKnap::Bound(inti,intcw,intcp){intcleft=c-cw;//剩余容量floatb=(float)cp;//价值上界//以物品单位重量价值减序装填剩余容量while(in&&w[i]=cleft){cleft-=w[i];b+=p[i];i++;}//装填剩余容量装满背包if(in)b+=1.0*p[i]/w[i]*cleft;returnb;}//计算最优值和变量值voidKnap::display(){inti;coutendl;cout当前最优价值为:lbestpendl;for(i=n;i=1;i--){x[M[i-1]]=bestp-bag;bestp=bestp-parent;}cout变量值x=;for(i=1;i=n;i++)coutx[i-1];coutendl;}//背包问题求解voidKnap::solvebag(){inti;floatubb;node*aa;//记录上限最大结点first=newnode[1];//根结点first-parent=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+w[i]=c&&(long)(aa-cp+p[i])lbestp){lbestp=aa-cp+p[i];bestp=nnoder(aa,1,(float)lbestp);//将一个新的结点插入到子集树和优先队列中}if((long)(aa-cp)lbestp){lbestp=aa-cp;bestp=nnoder(aa,0,(float)lbestp);}}//非叶子结点，递归调用Bound函数计算上界if(in-1){if(aa-cw+w[i]=c&&Bound(i+1,aa-cw+w[i],aa-cp+p[i])(float)lbestp){ubb=Bound(i,aa-cw+w[i],aa-cp+p[i]);addnode(nnoder(aa,1,ubb));//将结点加入到优先队列中}ubb=ubb=Bound(i,aa-cw,aa-cp);if(ubblbestp)addnode(nnoder(aa,0,ubb));}}display();}intmain(){intc,n;inti=0;int*p;int*w;coutendl;cout|***********分支限界法解0-1背包问题***********|endl;coutendl;cout请输入物品数量n=;cinn;coutendl;cout请输入背包容量C=;cinc;coutendl;x=newint[n];//变量值p=newint[n];//物品价值w=newint[n];//物品重量cout请分别输入这n个物品的重量W:endl;for(i=0;in;i++)cinw[i];coutendl;cout请输入这n个物品的价值P:endl;for(i=0;in;i++)cinp[i];Knapknbag(p,w,c,n);knbag.solvebag();getch();return0;}四、运行结果五、实验小结回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。