《0036算法笔记——【分支限界法】0-1背包问题》由会员分享，可在线阅读，更多相关《0036算法笔记——【分支限界法】0-1背包问题（12页珍藏版）》请在金锄头文库上搜索。
1、 问题描述给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?形式化描述：给定 c 0, wi 0, vi 0 , 1in.要求找一 n 元向量(x1,x2,xn,), xi0,1, wi xic,且 vi xi 达最大.即一个特殊的整数规划问题。算法设计首先，要对输入数据进行预处理，将各物品依其 单位重量价值从大到小进行排列 。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是
2、可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。例如： 0-1 背包问题，当 n=3 时，w=16,15,15, p=45,25,25, c=30。优先队列式分支限界法：处理法则:价值大者优先。AB,CC，D，EC，EC，J，KCF，GG， L，MG，MG N，O O 算法代码实现如下：1、MaxHeap.hcpp view plain copy1. template 2. class MaxHeap 3. 4. public: 5. MaxHeap(int M
3、axHeapSize = 10); 6. MaxHeap() delete heap; 7. int Size() const return CurrentSize; 8. 9. T Max() 10. /查 11. if (CurrentSize = 0) 12. 13. throw OutOfBounds(); 14. 15. return heap1; 16. 17. 18. MaxHeap /增 19. MaxHeap /删 20. 21. void Initialize(T a, int size, int ArraySize); 22. 23. private: 24. int C
4、urrentSize, MaxSize; 25. T *heap; / element array 26. ; 27. 28. template 29. MaxHeap:MaxHeap(int MaxHeapSize) 30. / Max heap constructor. 31. MaxSize = MaxHeapSize; 32. heap = new TMaxSize+1; 33. CurrentSize = 0; 34. 35. 36. template 37. MaxHeap& MaxHeap:Insert(const T& x) 38. / Insert x into the ma
5、x heap. 39. if (CurrentSize = MaxSize) 40. 41. cout heapi/2) 49. 50. / i 不是根节点，且其值大于父节点的值，需要继续调整 51. heapi = heapi/2; / 父节点下降 52. i /= 2; / 继续向上，搜寻正确位置 53. 54. 55. heapi = x; 56. return *this; 57. 58. 59. template 60. MaxHeap& MaxHeap:DeleteMax(T& x) 61. / Set x to max element and delete max element
6、 from heap. 62. / check if heap is empty 63. if (CurrentSize = 0) 64. 65. cout= heapci) 86. 87. break; / 是，i 就是 y 的正确位置，退出 88. 89. 90. / 否，需要继续向下，重整堆 91. heapi = heapci; / 大于父节点的孩子节点上升 92. i = ci; / 向下一层，继续搜索正确位置 93. ci *= 2; 94. 95. 96. heapi = y; 97. return *this; 98. 99. 100. template 101. void M
7、axHeap:Initialize(T a, int size,int ArraySize) 102. / Initialize max heap to array a. 103. delete heap; 104. heap = a; 105. CurrentSize = size; 106. MaxSize = ArraySize; 107. 108. / 从最后一个内部节点开始，一直到根，对每个子树进行堆重整 109. for (int i = CurrentSize/2; i = 1; i-) 110. 111. T y = heapi; / 子树根节点元素 112. / find p
8、lace to put y 113. int c = 2*i; / parent of c is target 114. / location for y 115. while (c = heapc) 124. 125. break; / yes 126. 127. 128. / no 129. heapc/2 = heapc; / move child up 130. c *= 2; / move down a level 131. 132. heapc/2 = y; 133. 134. 2、6d5.cppcpp view plain copy1. /0-1 背包问题 分支限界法求解 2.
9、#include stdafx.h 3. #include MaxHeap.h 4. #include 5. using namespace std; 6. 7. class Object 8. 9. template 10. friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); 11. public: 12. int operator =a.d; 15. 16. private: 17. int ID; 18. float d;/单位重量价值 19. ; 20. 21. template class Knap; 22
10、. 23. class bbnode 24. 25. friend Knap; 26. template 27. friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx); 28. private: 29. bbnode * parent; /指向父节点的指针 30. bool LChild; /左儿子节点标识 31. ; 32. 33. template 34. class HeapNode 35. 36. friend Knap; 37. public: 38. operator Typep() const 39. 40
11、. return uprofit; 41. 42. private: 43. Typep uprofit, /节点的价值上界 44. profit; /节点所相应的价值 45. Typew weight; /节点所相应的重量 46. int level; /活节点在子集树中所处的层序号 47. bbnode *ptr; /指向活节点在子集中相应节点的指针 48. ; 49. 50. template 51. class Knap 52. 53. template 54. friend Typep Knapsack(Typep p,Typew w,Typew c,int n, int bestx
12、); 55. public: 56. Typep MaxKnapsack(); 57. private: 58. MaxHeap *H; 59. Typep Bound(int i); 60. void AddLiveNode(Typep up,Typep cp,Typew cw,bool ch,int lev); 61. 62. bbnode *E; /指向扩展节点的指针 63. Typew c; /背包容量 64. int n; /物品数 65. 66. Typew *w; /物品重量数组 67. Typep *p; /物品价值数组 68. Typew cw; /当前重量 69. 70. Typep cp; /当前价值 71.
