优先队列式分支限界法求解01背包问题

1、算法分析与设计实验报告第 7 次实验姓名学号班级时间6.4上午地点四合院 实验名称优先队列式分支限界法求解0-1背包问题实验目的通过上机实验，要求掌握优先队列式分支限界法求解0-1背包问题的问题描述、算法设计思想、程序设计。实验原理1、使用优先队列式分支限界法算法，根据不同的输入用例，能准确的输出背包能装的最大价值，并计算出程序运行所需要的时间。2、分支限界法常以广度优先或最小耗费优先（最大效益优先）方式搜索问题的解空间树， 对于0-1背包问题的解空间树是一个棵子集树。3、在分支限界法中有一个活结点表，活结点表中的每个活结点只有一次机会成为扩展结点，一旦成为 扩展结点就一次性产生所有儿子结点，

2、在这些儿子结点中，导致不可行解或导致非最优解的儿子 结点被舍弃，其余儿子结点被加入到活结点表中。4、为了尽快找到0-1背包问题的解，每次选取下一个活结点成为扩展结点的判断依据是当前情况下 最有可能找到最优解的下一个结点。因此，每次选择扩展结点的方法：当前情况下，在活结点表中 选择活结点的上界，最大的活结点成为当前的扩展结点。 这一过程一直持续到找到所需的解或活结点表为空时为止。实验步骤1、定义树结点类bbnode，用于构造子集树，以便计算最优解；定义堆结点类HeapNode，用于定义堆元素类型； 定义最大堆类MaxHeap，用于实现优先队列定义.物品类Object，用于保存物品编号和物品的单位

3、重量价值；定义解决0-1背包问题的主类Knap。2、设计求解0-1背包问题的主函数Knapsack，在其中对物品以单位价值量排序。3、设计负责求解0-1背包问题的最优值和最优解函数MaxKnapsack在其中调用计算结点价值上界函数Bound，向子集树和最大堆中插入结点函数AddLiveNode和释放最大堆最大结点的函数DeleteMax，实现优先级队列。4、输入数据到input.txt文件中。5、添加计算运行时间的代码，计算不同规模数据的运行时间，并将结果输出到output文件中。6、分析时间复杂度：在最坏的情况下所有的节点都入队，最后一个节点才是最优解，这种情况下时间复杂度是指数阶。最好的

4、情况是只装单位价值最大的物品，其余分支都不符合条件被截去这种情况下时间复杂度是常数时间。但分支限界法本质上还是穷举法，平均时间复杂度仍是指数阶。关键代码/物品类 class Object friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); public: int operator = a.d); private: int ID; /物品编号 float d; /单位重量价值 ; /树结点类 class bbnode friend class Knap; friend Typep Knapsack(Typew *, Typep

5、*, Typew, int, int *); private: bbnode *parent; /指向父节点的指针 int LChild; ; /堆结点类 class HeapNode friend class Knap; friend class MaxHeap; public: operator Typep()constreturn uprofit; private: Typep uprofit, /结点的价值上界 profit; /结点所相应的价值 Typew weight; /结点所相应的重量 int level; /活结点在子集树中所处的层序号 bbnode *elemPtr; /指

6、向该活结点在子集树中相应结点的指针 ; /最大堆类 class MaxHeap public: MaxHeap(int maxElem) HeapElem = new HeapNode* maxElem+1; /下标为0的保留 capacity = maxElem; size = 0; void InsertMax(HeapNode *newNode); HeapNode DeleteMax(HeapNode* &N); private: int capacity; int size; HeapNode *HeapElem; ; /0-1背包问题的主类 class Knap friend Ty

7、pep Knapsack(Typew *, Typep *, Typew, int, int *); public: Typep MaxKnapsack(); private: MaxHeap *H; Typep Bound(int i); void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level); bbnode *E; /指向扩展结点的指针 Typew c; /背包容量 int n; /物品总数 Typew *w; /物品重量数组（以单位重量价值降序） Typep *p; /物品价值数组（以单位重量价值降序） Type

8、w cw; /当前装包重量 Typep cp; /当前装包价值 int *bestx; /最优解 ; void MaxHeap:InsertMax(HeapNode *newNode) int i = 1; for (i = +size; i/2 0 & HeapElemi/2-uprofit uprofit; i /= 2) HeapElemi = HeapElemi/2; HeapElemi = newNode; HeapNode MaxHeap:DeleteMax(HeapNode *&N) if(size 0 ) N = HeapElem1; int i = 1; while(i si

9、ze) if(i*2 +1) uprofit HeapElemi*2 +1-uprofit) HeapElemi = HeapElemi*2; i = i*2; else if(i*2 = size) HeapElemi = HeapElemi*2; i = i*2; else break; if(i size) HeapElemi = HeapElemsize; size-; return *N; Typep Knap:MaxKnapsack() H = new MaxHeap(10000); bestx = new int n+1; int i = 1; E = 0; cw = 0; cp

10、 = 0; Typep bestp = 0; Typep up = Bound(1); while (i != n+1) Typew wt = cw + wi; if(wt bestp) bestp = cp + pi; AddLiveNode(up, cp + pi, cw + wi, 1, i); up = Bound(i + 1); if(up = bestp) AddLiveNode(up, cp, cw, 0, i); HeapNode* N; H-DeleteMax(N); E = N-elemPtr; cw = N-weight; cp = N-profit; up = N-up

11、rofit; i = N-level + 1; for (int i = n; i 0; i-) bestxi = E-LChild; E = E-parent; return cp; Typep Knap:Bound(int i) Typew cleft = c - cw; Typep b = cp; while (i=n & wi = cleft) cleft -= wi; b += pi; i+; if(iparent=E; b-LChild=ch; HeapNode *N = new HeapNode; N-uprofit=up; N-profit=cp; N-weight=cw; N

12、-level=level; N-elemPtr=b; H-InsertMax(N); /Knapsack返回最大价值，最优值保存在bestx Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx) Typew W = 0; Typep P = 0; Object *Q = new Objectn; for(int i =1; i=n; i+) Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if (W = c) for(int i =1; i=n; i+) bestxi

13、= pi; return P; for(int i = 1; in; i+) for(int j = 1; j= n-i; j+) if(Qj-1.d Qj.d) Object temp = Qj-1; Qj-1 = Qj; Qj = temp; Knap K; K.p = new Typep n+1; K.w = new Typew n+1; for(int i = 1; i=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; Typep bestp = K.MaxKnapsack();

14、 for(int i = 1; i=n; i+) bestxQi-1.ID = K.bestxi; delete Q; delete K.w; delete K.p; delete K.bestx; delete K.H; return bestp; 测试结果1、测试自己输入的小规模数据2、测试随机生成1003、随机生成1000数据4、随机生成1000数据实验心得在做本次实验之前，我对分支限界法的原理并不是很理解，经过查看课件及网上查找资料，同时结合自己对回溯法等的理解，我对分支限界法有了一个较好的理解，知道了两种主要的分支限界法及分支限界法如何应用于解01背包问题。在查找资料的过程中，我查看

15、了许多网上的别人的代码实现，结合课本上的代码完成了该实验。通过本次试验，我基本上掌握了优先队列分支限界法解0-1背包问题的原理，同时锻炼了自己动手编写及调试代码的能力，收获良多。实验得分助教签名附录：完整代码#include #include#include#includeusing namespace std; ifstream in(input.txt);ofstream out(output.txt);typedef int Typew; typedef int Typep; /物品类 class Object friend Typep Knapsack(Typew *, Typep *

16、, Typew, int, int *); public: int operator = a.d); private: int ID; /物品编号 float d; /单位重量价值 ; /树结点类 class bbnode friend class Knap; friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); private: bbnode *parent; /指向父节点的指针 int LChild; ; /堆结点类 class HeapNode friend class Knap; friend class MaxHeap

17、; public: operator Typep()constreturn uprofit; private: Typep uprofit, /结点的价值上界 profit; /结点所相应的价值 Typew weight; /结点所相应的重量 int level; /活结点在子集树中所处的层序号 bbnode *elemPtr; /指向该活结点在子集树中相应结点的指针 ; /最大堆类 class MaxHeap public: MaxHeap(int maxElem) HeapElem = new HeapNode* maxElem+1; /下标为0的保留 capacity = maxElem

18、; size = 0; void InsertMax(HeapNode *newNode); HeapNode DeleteMax(HeapNode* &N); private: int capacity; int size; HeapNode *HeapElem; ; /0-1背包问题的主类 class Knap friend Typep Knapsack(Typew *, Typep *, Typew, int, int *); public: Typep MaxKnapsack(); private: MaxHeap *H; Typep Bound(int i); void AddLiv

19、eNode(Typep up, Typep cp, Typew cw, int ch, int level); bbnode *E; /指向扩展结点的指针 Typew c; /背包容量 int n; /物品总数 Typew *w; /物品重量数组（以单位重量价值降序） Typep *p; /物品价值数组（以单位重量价值降序） Typew cw; /当前装包重量 Typep cp; /当前装包价值 int *bestx; /最优解 ; void MaxHeap:InsertMax(HeapNode *newNode) int i = 1; for (i = +size; i/2 0 & Heap

20、Elemi/2-uprofit uprofit; i /= 2) HeapElemi = HeapElemi/2; HeapElemi = newNode; HeapNode MaxHeap:DeleteMax(HeapNode *&N) if(size 0 ) N = HeapElem1; int i = 1; while(i size) if(i*2 +1) uprofit HeapElemi*2 +1-uprofit) HeapElemi = HeapElemi*2; i = i*2; else if(i*2 = size) HeapElemi = HeapElemi*2; i = i*

21、2; else break; if(i size) HeapElemi = HeapElemsize; size-; return *N; Typep Knap:MaxKnapsack() H = new MaxHeap(10000); bestx = new int n+1; int i = 1; E = 0; cw = 0; cp = 0; Typep bestp = 0; Typep up = Bound(1); while (i != n+1) Typew wt = cw + wi; if(wt bestp) bestp = cp + pi; AddLiveNode(up, cp +

22、pi, cw + wi, 1, i); up = Bound(i + 1); if(up = bestp) AddLiveNode(up, cp, cw, 0, i); HeapNode* N; H-DeleteMax(N); E = N-elemPtr; cw = N-weight; cp = N-profit; up = N-uprofit; i = N-level + 1; for (int i = n; i 0; i-) bestxi = E-LChild; E = E-parent; return cp; Typep Knap:Bound(int i) Typew cleft = c

23、 - cw; Typep b = cp; while (i=n & wi = cleft) cleft -= wi; b += pi; i+; if(iparent=E; b-LChild=ch; HeapNode *N = new HeapNode; N-uprofit=up; N-profit=cp; N-weight=cw; N-level=level; N-elemPtr=b; H-InsertMax(N); /Knapsack返回最大价值，最优值保存在bestx Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx

24、) Typew W = 0; Typep P = 0; Object *Q = new Objectn; for(int i =1; i=n; i+) Qi-1.ID = i; Qi-1.d = 1.0*pi/wi; P += pi; W += wi; if (W = c) for(int i =1; i=n; i+) bestxi = pi; return P; for(int i = 1; in; i+) for(int j = 1; j= n-i; j+) if(Qj-1.d Qj.d) Object temp = Qj-1; Qj-1 = Qj; Qj = temp; Knap K;

25、K.p = new Typep n+1; K.w = new Typew n+1; for(int i = 1; i=n; i+) K.pi = pQi-1.ID; K.wi = wQi-1.ID; K.cp = 0; K.cw = 0; K.c = c; K.n = n; Typep bestp = K.MaxKnapsack(); for(int i = 1; i=n; i+) bestxQi-1.ID = K.bestxi; delete Q; delete K.w; delete K.p; delete K.bestx; delete K.H; return bestp; int main() cout请在input.txt文件中输入物品数量、背包容量N; Typew c; /背包容量 inc; int bestxN+1; /最优解 int bestp; /最优值 Typep pN+1;/物品价值 Typew wN+1;/物品重量 cout在input.txt文件中读取的物品总数N = N,背包容量C = cendl; cout请选择生成数据的规模大小：200请输入1,2000请输入2，20000请输入3x;if(x=1)ofstream in1(input1.txt);srand(time(NULL); int n=200; int *a=n