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

实验四用分支限界法实现0-1背包问题一．实验目的1.熟悉分支限界法的基本原理。2.通过本次实验加深对分支限界法的理解。二．实验内容及要求内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?要求：使用优先队列式分支限界法算法编程，求解0-1背包问题三．程序列表#includeiostream#includestackusingnamespacestd;#defineN100classHeapNode//定义HeapNode结点类{public:doubleupper,price,weight;//upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量intlevel,x[N];//活节点在子集树中所处的层序号};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);//up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是tureorfalsestackHeapNodeHigh;//最大队Highdoublew[N],p[N];//把物品重量和价值定义为双精度浮点数doublecw,cp,c;//cw为当前重量，cp为当前价值，定义背包容量为cintn;//货物数量为intmain(){cout请输入背包容量：endl;cinc;cout请输入物品的个数：endl;cinn;cout请按顺序分别输入物品的重量：endl;inti;for(i=1;i=n;i++)cinw[i];//输入物品的重量cout请按顺序分别输入物品的价值：endl;for(i=1;i=n;i++)cinp[i];//输入物品的价值cout最优值为：;coutKnap()endl;//调用knap函数输出最大价值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中{HeapNodebe;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(wt=c)//左儿子结点为可行结点{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.empty())returnbestp;HeapNodenode=High.top();//取下一扩展结点High.pop();cw=node.weight;cp=node.price;up=node.upper;i=node.level;}}四．实验结果