分支限界法求0-1背包问题实验程序以及代码(C++)

分支限界法求0-1背包问题实验程序以及代码（C++）本程序中（规定物品数量为3，背包容量为30，输入为6个数，前3个为物品重量，后3个数为物品价值）：代码：#includeiostream#includestackusingnamespacestd;#defineN100classHeapNode//定义HeapNode结点类{public:doubleupper,price,weight;//upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量intlevel,x[N];//活节点在子集树中所处的层序号};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);stackHeapNodeHigh;//最大队Highdoublew[N],p[N];//把物品重量和价值定义为双精度浮点数doublecw,cp,c=30;//cw为当前重量，cp为当前价值，定义背包容量为30intn=3;//货物数量为3intmain(){cout请按顺序输入3个物品的重量：（按回车键区分每个物品的重量）endl;inti;for(i=1;i=n;i++)cinw[i];//输入3个物品的重量cout请按顺序输入3个物品的价值：（按回车键区分每个物品的价值）endl;for(i=1;i=n;i++)cinp[i];//输入3个物品的价值cout最大价值为：;coutKnap()endl;//调用knap函数输出最大价值return0;}doubleMaxBound(intj)//MaxBound函数求最大上界{doubleleft=c-cw,b=cp;//剩余容量和价值上界while(j=n&&w[j]=left)//以物品单位重量价值递减装填剩余容量{left-=w[j];b+=p[j];j++;}if(j=n)b+=p[j]/w[j]*left;//装填剩余容量装满背包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,up=MaxBound(1);//调用MaxBound求出价值上界，best为最优值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;}}输出结果为：