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

如有侵权，请联系网站删除，仅供学习与交流实验 4 用分支限界法实现0-1背包问题【精品文档】第 5 页实验四 用分支限界法实现0-1背包问题一实验目的 1.熟悉分支限界法的基本原理。2.通过本次实验加深对分支限界法的理解。  二实验内容及要求内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?要求：使用优先队列式分支限界法算法编程，求解0-1背包问题三程序列表#include<iostream> #include<stack> 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<HeapNode> High; /最大队High double wN, pN; /把物品重量和价值定义为双精度浮点数 double cw, cp, c; /cw为当前重量，cp为当前价值，定义背包容量为cint n; /货物数量为int main()cout << "请输入背包容量：" << endl;cin >> c;cout << "请输入物品的个数：" << endl;cin >> n;cout << "请按顺序分别输入物品的重量：" << endl;int 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函数求最大上界 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 <= 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;HeapNode node = High.top(); /取下一扩展结点 High.pop();cw = node.weight;cp = node.price;up = node.upper;i = node.level;四实验结果