实验 4 用分支限界法实现0-1背包问题

《实验 4 用分支限界法实现0-1背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四用分支限界法实现0-1背包问题一．实验目的1.熟悉分支限界法的基本原理。2.通过本次实验加深对分支限界法的理解。  二．实验内容及要求内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?要求：使用优先队列式分支限界法算法编程，求解0-1背包问题三．程序列表#include#includeusingnamespacestd;#defineN100classHeapNode//定义HeapNode结点类{public:doubleupper,price,weigh

2、t;//upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量intlevel,x[N];//活节点在子集树中所处的层序号};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);//up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是tureorfalsestackHigh;//最大队Highdoublew[N],p[N];//把物品重量和价值定义为双精度浮点数doublecw,cp

3、,c;//cw为当前重量，cp为当前价值，定义背包容量为cintn;//货物数量为intmain(){cout<<"请输入背包容量："<>c;cout<<"请输入物品的个数："<>n;cout<<"请按顺序分别输入物品的重量："<>w[i];//输入物品的重量cout<<"请按顺序分别输入物品的价值："<>p[i];//输入物品的价值cout<<"最优值为：";cout<

4、值return0;}doubleMaxBound(intk)//MaxBound函数求最大上界{doublecleft=c-cw;//剩余容量doubleb=cp;//价值上界while(k<=n&&w[k]<=cleft)//以物品单位重量价值递减装填剩余容量{cleft-=w[k];b+=p[k];k++;}if(k<=n)b+=p[k]/w[k]*cleft;//装填剩余容量装满背包returnb;}voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlev)//将一个新的活结点插入到子集数和最大堆High中{HeapNod

5、ebe;be.upper=up;be.price=cp;be.weight=cw;be.level=lev;if(lev<=n)High.push(be);}//调用stack头文件的push函数}doubleKnap()//优先队列分支限界法，返回最大价值，bestx返回最优解{inti=1;cw=cp=0;doublebestp=0;//best为当前最优值doubleup=MaxBound(1);//价值上界//搜索子集空间树while(1)//非叶子结点{doublewt=cw+w[i];if(wt<=c)//左儿子结点为可行结点{if(cp+p[i]>bestp)bestp

6、=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=MaxBound(i+1);if(up>=bestp)//右子数可能含最优解AddLiveNode(up,cp,cw,false,i+1);if(High.empty())returnbestp;HeapNodenode=High.top();//取下一扩展结点High.pop();cw=node.weight;cp=node.price;up=node.upper;i=node.level;}}四．实验结果