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

实验 用分支限界法实现01背包问题实验四 用分支限界法实现0-1背包问题 一实验目的 1.熟悉分支限界法的基本原理。 2.通过本次实验加深对分支限界法的理解。 二实验内容及要求 内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题 三程序列表 #include<iostream> #include<stack> usingnamespace std; #defineN 100 classHeapNode/定义HeapNode结点类 public: ; double MaxBound(int i); double Knap; void AddLiveNode(double up, double cp, double cw, bool ch, int level);/up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是ture or false stack<HeapNode> High; /最大队High double wN, pN; /把物品重量和价值定义为双精度浮点数 double cw, cp, c; /cw为当前重量，cp为当前价值，定义背包容量为c int n; /货物数量为 int main cout <<"请输入背包容量："<< endl; cin >> c; cout <<"请输入物品的个数："<< endl; cin >> n; cout <<"请按顺序分别输入物品的重量："<< endl; int i; for (i = 1; i <= n; i+) cin >> wi; /输入物品的重量 double upper, price, weight; /upper为结点的价值上界，price是结点所对应的价值，weightint level, xN; /活节点在子集树中所处的层序号 为结点所相应的重量 cout <<"请按顺序分别输入物品的价值："<< endl; for (i = 1; i <= n; i+) cin >> pi; /输入物品的价值 cout <<"最优值为：" cout << Knap << endl; /调用knap函数 输出最大价值 return 0; double MaxBound(intk) /MaxBound函数求最大上界 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) 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 <= c) /左儿子结点为可行结点 /搜索子集空间树 while (1) /非叶子结点 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); return bestp; if (High.empty) HeapNode node = High.top; /取下一扩展结点 High.pop; cw = node.weight; cp = node.price; up = node.upper; i = node.level; 四实验结果