01背包问题 分支界限法

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

1、实验五01背包问题一、实验内容：运用分支限界法解决0-1背包问题。二、算法分析分支限界法分支限界法按广度优先策略遍历问题的解空间树,在遍历过程中,对已经处理的每一个结点根据限界函数估算目标函数的可能取值,从中选取使目标函数取得极值的结点优先进行广度优先搜索,从而不断调整搜索方向,尽快找到问题的解。因为限界函数常常是基于问题的目标函数而确定的,所以,分支限界法适用于求解最优化问题。0-1背包问题1）基本思想给定n种物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,0/1背包问题是如何选择装入背包的物品(物品不可分割),

2、使得装入背包中物品的总价值最大，一般情况下,解空间树中第i层的每个结点,都代表了对物品1～i做出的某种特定选择,这个特定选择由从根结点到该结点的路径唯一确定:左分支表示装入物品,右分支表示不装入物品。对于第i层的某个结点,假设背包中已装入物品的重量是w,获得的价值是v,计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v,加上背包剩余容量W-w与剩下物品的最大单位重量价值vi+1/wi+1的积,于是,得到限界函数:ub=v+(W-w)×(vi+1/wi+1)根据限界函数确定目标函数的界[down,up]，

3、然后,按照广度优先策略遍历问题的空间树。2）复杂度分析时间复杂度是O(2n);三、实验结果：四、源程序及注释：#include#include#include#include#includeusingnamespacestd;int*x;structnode{//结点表结点数据结构node*parent,//父结点指针*next;//后继结点指针intlevel,//结点的层bag,//节点的解cw,//当前背包装载量cp;//当前背包

4、价值floatub;//结点的上界值};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

5、,floatuub);//生成一个结点ba=1生成左节点ba=0生成右节点voidaddnode(node*nod);//将结点添加到队列中voiddeletenode(node*nod);//将结点队列中删除structnode*nextnode();//取下一个voiddisplay();//输出结果voidsolvebag();//背包问题求解};Knap::Knap(int*pp,int*ww,intcc,intnn){inti;n=nn;c=cc;p=newint[n];w=newint[n];M=newint[n]

6、;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;}floatKnap::Bound(inti,intcw,intcp){//计算上界intcleft=c-cw;floatb=

7、(float)cp;while(iparent=pa;nodell->next=NULL;nodell->level=(pa->level)+1;nodell->bag=ba;nodell->ub

8、=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);}vo