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

实验四 用分支限界法实现0-1背包问题一实验目的 1.熟悉分支限界法的基本原理。2.通过本次实验加深对分支限界法的理解。二实验内容及要求内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?要求：使用优先队列式分支限界法算法编程，求解0-1背包问题三程序列表#include #include using namespace std;#define N 100 class HeapNode /定义HeapNode结点类 public:double upper, price, weight; /upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量 int level, xN; /活节点在子集树中所处的层序号 ;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 High; /最大队High double wN, pN; /把物品重量和价值定义为双精度浮点数 double cw, cp, c; /cw为当前重量，cp为当前价值，定义背包容量为cint n; /货物数量为int main()cout 请输入背包容量： c;cout 请输入物品的个数： 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函数求最大上界 double cleft = c - cw; /剩余容量double b = cp; /价值上界 while (k = n&wk = cleft) /以物品单位重量价值递减装填剩余容量 cleft -= wk;b += pk;k+;if (k = n)b += pk / wk * cleft; /装填剩余容量装满背包 return b;void AddLiveNode(double 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; /best为当前最优值 double up = MaxBound(1);/价值上界/搜索子集空间树while (1) /非叶子结点 double wt = cw + wi;if (wt 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;HeapNode node = High.top(); /取下一扩展结点 H