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

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

2、ight;/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 High; / 最大队 Highdouble w N, p N； /把物品重量和价值定义为双精度浮点数dou

3、ble cw, cp, c; /cw为当前重量，cp为当前价值，定义背包容量为 cint n; /货物数量为int main()cout 请输入背包容量： c;cout 请输入物品的个数:II n;cout 请按顺序分别输入物品的重量： endl;int i;for (i = 1; i wi; /输入物品的重量cout 请按顺序分别输入物品的价值： endl;for (i = 1; i pi; /输入物品的价值cout 最优值为：;cout Knap() endl; /调用knap函数 输出最大价值return 0;double MaxBound(int k) /MaxBound 函数求最大上

4、界double cleft = c - cw; / 剩余容量double 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

5、= cp;be.weight = cw;be.level = lev ;if ( lev 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 = High.top(); / 取下一扩展结点High.pop();cw = no de.weight;cp = no de.price;up = no de.upper;i = nodeevel;四实验结果