实验四用分支限界法实现0-1背包问题
一.实验目的
1.熟悉分支限界法的基本原理。
2.通过本次实验加深对分支限界法的理解。??
二.实验内容及要求
内容:.给定n种物品和一个背包。物品i的重量是w,其价值为v,背包容量为c。问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大? 要求:使用优先队列式分支限界法算法编程,求解0-1背包问题 三.程序列表 #include
doubleMaxBound(inti); doubleKnap();
voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);//up是价值上界,cp是相应的价值,cw是该结点所相应的重量,ch是tureorfalse stack
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<<\请输入背包容量:\<
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)//非叶子结点 {