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

实验四用分支限界法实现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)//非叶子结点 {

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4