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

《实验 用分支限界法实现01背包问题.docx》由会员分享，可在线阅读，更多相关《实验 用分支限界法实现01背包问题.docx（4页珍藏版）》请在三一办公上搜索。

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

2、int i); double Knap; void AddLiveNode(double up, double cp, double cw, bool ch, int level);/up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是ture or false stack High; /最大队High double wN, pN; /把物品重量和价值定义为双精度浮点数 double cw, cp, c; /cw为当前重量，cp为当前价值，定义背包容量为c int n; /货物数量为 int main cout 请输入背包容量： c; cout 请输入物品的个数： n; cout

3、 请按顺序分别输入物品的重量： endl; int i; for (i = 1; i wi; /输入物品的重量 double upper, price, weight; /upper为结点的价值上界，price是结点所对应的价值，weightint level, xN; /活节点在子集树中所处的层序号 为结点所相应的重量 cout 请按顺序分别输入物品的价值： endl; for (i = 1; i pi; /输入物品的价值 cout 最优值为：; cout Knap endl; /调用knap函数 输出最大价值 return 0; double MaxBound(intk) /MaxBoun

4、d函数求最大上界 void AddLiveNode(doubleup, doublecp, doublecw, boolch, intlev) /将一个新的活结点插入到子集数和最大堆High中 HeapNode be; be.upper = up; be.price = cp; be.weight = cw; be.level = lev; if (lev= n) High.push(be); double cleft = c - cw; /剩余容量 double b = cp; /价值上界 while (k= n&wk = cleft) /以物品单位重量价值递减装填剩余容量 if (k= n

5、) b += pk / wk * cleft; /装填剩余容量装满背包 return b; cleft -= wk; b += pk; k+; /调用stack头文件的push函数 double Knap /优先队列分支限界法，返回最大价值，bestx返回最优解 int i = 1; cw = cp = 0; double bestp = 0; /best为当前最优值 double up = MaxBound(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); return bestp; if (High.empty) HeapNode node = High.top; /取下一扩展结点 High.pop; cw = node.weight; cp = node.price; up = node.upper; i = node.level; 四实验结果