分支界限法解0-1背包问题实验报告.doc
《分支界限法解0-1背包问题实验报告.doc》由会员分享，可在线阅读，更多相关《分支界限法解0-1背包问题实验报告.doc（7页珍藏版）》请在冰点文库上搜索。
实验5分支界限法解0-1背包问题
一、实验要求
1．要求用分支界限法求解0-1背包问题；
2．要求交互输入背包容量，物品重量数组，物品价值数组；
3．要求显示结果。
二、实验仪器和软件平台
仪器：
带usb接口微机
软件平台：
WIN-XP+VC++6.0
三、源程序
#include"stdafx.h"
#include
#include
#include
#include
usingnamespacestd;
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;i {
minl=1.0*p[i]/w[i];
k=0;
for（j=1;j<=n-i;j++）
{
if（minl<1.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;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->ubnext=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（i{
cleft-=w[i];
b+=p[i];
i++;
}
//装填剩余容量装满背包
if（ireturnb;
}
//计算最优值和变量值
voidKnap:
:
display（）
{
inti;
cout< cout<<"当前最优价值为:
"< for（i=n;i>=1;i--）
{
x[M[i-1]]=bestp->bag;
bestp=bestp->parent;
}
cout<<"变量值x=";
for（i=1;i<=n;i++）
cout< cout<}
//背包问题求解
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（i {
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（ubb>lbestp）
addnode（nnoder（aa,0,ubb））;
}
}
display（）;
}
intmain（）
{
intc,n;
inti=0;
int*p;
int*w;
cout< cout<<"|***********分支限界法解0-1背包问题***********|"< cout< cout<<"请输入物品数量n=";
cin>>n;
cout< cout<<"请输入背包容量C=";
cin>>c;
cout< x=newint[n];//变量值
p=newint[n];//物品价值
w=newint[n];//物品重量
cout<<"请分别输入这"<"< for（i=0;i cin>>w[i];
cout< cout<<"请输入这"<"< for（i=0;i cin>>p[i];
Knapknbag（p,w,c,n）;
knbag.solvebag（）;
getch（）;
return0;
}
四、运行结果
五、实验小结
回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
升级会员 