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

《分支限界法求0-1背包问题实验程序以及代码(C++)(共3页).doc》由会员分享，可在线阅读，更多相关《分支限界法求0-1背包问题实验程序以及代码(C++)(共3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上分支限界法求0-1背包问题实验程序以及代码（C+）本程序中（规定物品数量为3，背包容量为30，输入为6个数，前3个为物品重量，后3个数为物品价值）：代码：#include #include using namespace std; #define N 100 class HeapNode /定义HeapNode结点类 public: double upper,price,weight; /upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量 int level,xN; /活节点在子集树中所处的层序号 ; double MaxBoun

2、d(int i); double Knap(); void AddLiveNode(double up,double cp,double cw,bool ch,int level); stack High; /最大队High double wN,pN; /把物品重量和价值定义为双精度浮点数double cw,cp,c=30; /cw为当前重量，cp为当前价值，定义背包容量为30 int n=3; /货物数量为3 int main() cout请按顺序输入3个物品的重量：（按回车键区分每个物品的重量）endl;int i; for(i=1;iwi; /输入3个物品的重量 cout请按顺序输入3个

3、物品的价值：（按回车键区分每个物品的价值）endl;for(i=1;ipi; /输入3个物品的价值 cout最大价值为：;coutKnap()endl; /调用knap函数 输出最大价值 return 0; double MaxBound(int j) /MaxBound函数求最大上界 double left=c-cw,b=cp; /剩余容量和价值上界 while(j=n&wj=left) /以物品单位重量价值递减装填剩余容量 left-=wj; b+=pj; j+; if(j=n) b+=pj/wj*left; /装填剩余容量装满背包 return b; void AddLiveNode(d

4、ouble up,double cp,double cw,bool ch,int lev) /将一个新的活结点插入到子集数和最大堆High中 HeapNode be; be.upper=up; be.price=cp; be.weight=cw; be.level=lev; if(lev=n) High.push(be); /调用stack头文件的push函数 double Knap() /优先队列分支限界法，返回最大价值，bestx返回最优解 int i=1; cw=cp=0; double bestp=0,up=MaxBound(1); /调用MaxBound求出价值上界，best为最优值

5、 while(1) /非叶子结点 double wt=cw+wi; if(wtbestp) bestp=cp+pi; AddLiveNode(up,cp+pi,cw+wi,true,i+1); up=MaxBound(i+1); if(up=bestp) /右子数可能含最优解 AddLiveNode(up,cp,cw,false,i+1); if(High.empty() return bestp; HeapNode node=High.top(); /取下一扩展结点 High.pop(); cw=node.weight; cp=node.price; up=node.upper; i=node.level; 输出结果为：专心-专注-专业