内容发布更新时间 : 2024/5/12 16:19:45星期一 下面是文章的全部内容请认真阅读。

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

一．实验目的

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

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

二．实验内容及要求

内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题 三．程序列表 #include #include usingnamespacestd; #defineN100 classHeapNode//定义HeapNode结点类 { public: };

doubleMaxBound(inti); doubleKnap();

voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);//up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是tureorfalse stackHigh;//最大队High

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

doubleupper,price,weight;//upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量 intlevel,x[N];//活节点在子集树中所处的层序号

doublecw,cp,c;//cw为当前重量，cp为当前价值，定义背包容量为c intn;//货物数量为 intmain() { } doubleMaxBound(intk)//MaxBound函数求最大上界 {

doublecleft=c-cw;//剩余容量 doubleb=cp;//价值上界

while(k<=n&&w[k]<=cleft)//以物品单位重量价值递减装填剩余容量 {

cleft-=w[k];

cout<<\请输入背包容量：\<>c;

cout<<\请输入物品的个数：\<>n; cout<<\请按顺序分别输入物品的重量：\<>w[i];//输入物品的重量 cout<<\请按顺序分别输入物品的价值：\<>p[i];//输入物品的价值 cout<<\最优值为：\; cout<

} voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlev)//将一个新的活结点插入到子集数和最大堆High中 { HeapNodebe; be.upper=up; be.price=cp; be.weight=cw; be.level=lev; if(lev<=n) High.push(be); } if(k<=n)

b+=p[k]/w[k]*cleft;//装填剩余容量装满背包 b+=p[k]; k++;

returnb;

}//调用stack头文件的push函数} doubleKnap()//优先队列分支限界法，返回最大价值，bestx返回最优解 {

inti=1; cw=cp=0;

doublebestp=0;//best为当前最优值 doubleup=MaxBound(1);//价值上界

//搜索子集空间树

while(1)//非叶子结点 {