实验用分支限界法实现背包问题

1、实验四 用分支限界法实现0-1背包问题一. 实验目的1. 熟悉分支限界法的基本原理。2. 通过本次实验加深对分支限界法的理解。？二. 实验内容及要求内容：给定n种物品和一个背包。物品i的重量是w,其价值为v,背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？要求：使用优先队列式分支限界法算法编程，求解0-1背包问题三. 程序列表#inelude <iostream>#include <stack>using namespacestd;#defi ne N100class HeapNode / 定义 HeapNode结点类 publicdoubl

2、e upper, price, weight;/upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量int level, x N;/活节点在子集树中所处的层序号；double MaxBound(int i);double Kn ap();void AddLiveNode( double up, double cp, double cw, bool ch, int level); /up 是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是ture or falsestack <HeapNod> High; / 最大队 Highdoubl

3、e w N, p N； /把物品重量和价值定义为双精度浮点数double cw, cp, c; /cw为当前重量，cp为当前价值，定义背包容量为 cint n; /货物数量为int main()cout << "请输入背包容量："<< endl;cin >> c;cout << "请输入物品的个数:II<< en dl;cin >> n;cout << "请按顺序分别输入物品的重量："<< endl;int i;for (i = 1; i <=

4、 n; i+)cin >> wi;/输入物品的重量cout << "请按顺序分别输入物品的价值："<< endl;for (i = 1; i <= n; i+)cin >> pi;/输入物品的价值cout << "最优值为："cout << Knap() << endl; /调用knap函数 输出最大价值return 0;double MaxBound(int k) /MaxBound 函数求最大上界double cleft = c - cw;/ 剩余容量doubl

5、e b = cp;/价值上界while ( k <= n&&w k <= cleft)/以物品单位重量价值递减装填剩余容量cleft -= w k;b += p k;k+;if ( k <= n)b += p k / w k * cleft;/装填剩余容量装满背包return b;/将一个新void AddLiveNode( double up, double cp, double cw, bool ch, int lev)的活结点插入到子集数和最大堆High中HeapNodeoe;be.upper = up;be.price = cp;be.weight =

6、 cw;be.level = lev ;if ( lev <= n)High.push(be);/调用stack头文件的push函数double Knap() /优先队列分支限界法，返回最大价值，bestx返回最优解int i = 1;cw = cp = 0;double bestp = 0; /best 为当前最优值double up = MaxBound(1); / 价值上界/搜索子集空间树while (1)/非叶子结点double wt = cw + wi;if (cp + pi>bestp)bestp = cp + pi;AddLiveNode(up, cp + pi, cw + wi,true , i + 1);up = MaxBou nd(i + 1);if (up >= bestp) /右子数可能含最优解AddLiveNode(up, cp, cw, false , i + 1);if (High.emptyO)return bestp;HeapNodenode =