实验用分支限界法实现背包问题.docx

实验用分支限界法实现背包问题.docx

《实验用分支限界法实现背包问题.docx》由会员分享，可在线阅读，更多相关《实验用分支限界法实现背包问题.docx（5页珍藏版）》请在冰点文库上搜索。

实验用分支限界法实现背包问题

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

1.实验目的

1.熟悉分支限界法的基本原理。

2.通过本次实验加深对分支限界法的理解。

？

？

2.实验内容及要求

内容：

•给定n种物品和一个背包。

物品i的重量是w,其价值为v,背包容量为c。

问应

该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

要求：

使用优先队列式分支限界法算法编程，求解0-1背包问题

3.程序列表

#inelude

#include

usingnamespacestd;

#defineN100

classHeapNode//定义HeapNode结点类public

doubleupper,price,weight;

//upper为结点的价值上界，price是结点所对应的

价值，weight为结点所相应的重量

intlevel,x[N];//活节点在子集树中所处的层序号

}；

doubleMaxBound（inti）;

doubleKnap（）;

voidAddLiveNode（doubleup,doublecp,doublecw,boolch,intlevel）;//up是价

值上界，cp是相应的价值，cw是该结点所相应的重量，ch是tureorfalse

stackHigh;//最大队High

doublew[N,p[N；//把物品重量和价值定义为双精度浮点数

doublecw,cp,c;//cw为当前重量，cp为当前价值，定义背包容量为c

intn;//货物数量为

intmain（）

{

cout<<"请输入背包容量：

"<

cin>>c;

cout<<"请输入物品的个数:

II

<

cin>>n;

cout<<"请按顺序分别输入物品的重量：

"<

inti;

for（i=1;i<=n;i++）

cin>>w[i];//输入物品的重量

cout<<"请按顺序分别输入物品的价值：

"<

for（i=1;i<=n;i++）

cin>>p[i];//输入物品的价值

cout<<"最优值为：

";

cout<

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中

{

HeapNodeoe;

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（cp+p[i]>bestp）

bestp=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.emptyO）

returnbestp;

HeapNodenode=High.top（）;//取下一扩展结点

High.pop（）;

cw=node.weight;

cp=node.price;

up=node.upper;

i=node」evel;

}

}四•实验结果