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

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

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

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

4、i;for (i = 1; i <= 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 函数求最大上界d

5、ouble 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 中HeapN

6、odebe;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; /best 为当前最优值double up = MaxBound(1); / 价值上界 / 搜索子集空间树while (1)/ 非叶子结点double wt = cw + wi; if (wt <= c) / 左儿子结点为可行结点if (cp + pi>bestp)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;HeapNoden