0036算法笔记——【分支限界法】0-1背包问题.docx

问题描述 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c 0, wi 0, vi 0 , 1in.要求找一n元向量(x1,x2,xn,), xi0,1, wi xic,且 vi xi达最大.即一个特殊的整数规划问题。 算法设计 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。 例如：0-1背包问题，当n=3时，w=16,15,15, p=45,25,25, c=30。优先队列式分支限界法：处理法则:价值大者优先。AB,CC，D，EC，EC，J，KCF，GG，L，MG，MGN，OO 算法代码实现如下： 1、MaxHeap.hcppview plaincopy1. template2. classMaxHeap3. 4. public:5. MaxHeap(intMaxHeapSize=10);6. MaxHeap()deleteheap;7. intSize()constreturnCurrentSize;8. 9. TMax()10. /查11. if(CurrentSize=0)12. 13. throwOutOfBounds();14. 15. returnheap1;16. 17. 18. MaxHeap&Insert(constT&x);/增19. MaxHeap&DeleteMax(T&x);/删20. 21. voidInitialize(Ta,intsize,intArraySize);22. 23. private:24. intCurrentSize,MaxSize;25. T*heap;/elementarray26. ;27. 28. template29. MaxHeap:MaxHeap(intMaxHeapSize)30. /Maxheapconstructor.31. MaxSize=MaxHeapSize;32. heap=newTMaxSize+1;33. CurrentSize=0;34. 35. 36. template37. MaxHeap&MaxHeap:Insert(constT&x)38. /Insertxintothemaxheap.39. if(CurrentSize=MaxSize)40. 41. coutnospace!heapi/2)49. 50. /i不是根节点，且其值大于父节点的值，需要继续调整51. heapi=heapi/2;/父节点下降52. i/=2;/继续向上，搜寻正确位置53. 54. 55. heapi=x;56. return*this;57. 58. 59. template60. MaxHeap&MaxHeap:DeleteMax(T&x)61. /Setxtomaxelementanddeletemaxelementfromheap.62. /checkifheapisempty63. if(CurrentSize=0)64. 65. coutEmptyheap!endl;66. return*this;67. 68. 69. x=heap1;/删除最大元素70. /重整堆71. Ty=heapCurrentSize-;/取最后一个节点，从根开始重整72. 73. /findplaceforystartingatroot74. inti=1,/currentnodeofheap75. ci=2;/childofi76. 77. while(ci=CurrentSize)78. 79. /使ci指向i的两个孩子中较大者80. if(ciCurrentSize&heapci=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. template101. voidMaxHeap:Initialize(Ta,intsize,intArraySize)102. /Initializemaxheaptoarraya.103. deleteheap;104. heap=a;105. CurrentSize=size;106. MaxSize=ArraySize;107. 108. /从最后一个内部节点开始，一直到根，对每个子树进行堆重整109. for(inti=CurrentSize/2;i=1;i-)110. 111. Ty=heapi;/子树根节点元素112. /findplacetoputy113. intc=2*i;/parentofcistarget114. /locationfory115. while(c=CurrentSize)116. 117. /heapcshouldbelargersibling118. if(cCurrentSize&heapc=heapc)124. 125. break;/yes126. 127. 128. /no129. heapc/2=heapc;/movechildup130. c*=2;/movedownalevel131. 132. heapc/2=y;133. 134. 2、6d5.cppcppview plaincopy1. /0-1背包问题分支限界法求解2. #includestdafx.h3. #includeMaxHeap.h4. #include5. usingnamespacestd;6. 7. classObject8. 9. template10. friendTypepKnapsack(Typepp,Typeww,Typewc,intn,intbestx);11. public:12. intoperator=a.d;15. 16. private:17. intID;18. floatd;/单位重量价值19. ;20. 21. templateclassKnap;22. 23. classbbnode24. 25. friendKnap;26. template27. friendTypepKnapsack(Typepp,Typeww,Typewc,intn,intbestx);28. private:29. bbnode*parent;/指向父节点的指针30. boolLChild;/左儿子节点标识31. ;32. 33. template34. classHeapNode35. 36. friendKnap;37. public:38. operatorTypep()const39. 40. returnuprofit;41. 42. private:43. Typepuprofit,/节点的价值上界44. profit;/节点所相应的价值45. Typewweight;/节点所相应的重量46. intlevel;/活节点在子集树中所处的层序号47. bbnode*ptr;/指向活节点在子集中相应节点的指针48. ;49. 50. template51. classKnap52. 53. template54. friendTypepKnapsack(Typepp,Typeww,Typewc,intn,intbestx);55. public:56. TypepMaxKnapsack();57. private:58. MaxHeapHeapNode*H;59. TypepBound(inti);60. voidAddLiveNode(Typepup,Typepcp,Typewcw,boolch,intlev);61. 62. bbnode*E;/指向扩展节点的指针63. Typewc;/背包容量64. intn;/物品数65. 66. Typew*w;/物品重量数组67. Typep*p;/物品价值数组68. Typewcw;/当前重量69. 70. Typepcp;/当前价值71. int*bestx;/最优解72. ;73. 74. template75. inlinevoidSwap(Type&a,Type&b);76. 77. template78. voidBubbleSort(Typea,intn);79. 80. intmain()81. 82. intn=3;/物品数83. intc=30;/背包容量84. intp=0,45,25,25;/物品价值下标从1开始85. intw=0,16,15,15;/物品重量下标从1开始86. intbestx4;/最优解87. 88. cout背包容量为：cendl;89. cout物品重量和价值分别为：endl;90. 91. for(inti=1;i=n;i+)92. 93. cout(wi,pi);94. 95. coutendl;96. 97. cout背包能装下的最大价值为：Knapsack(p,w,c,n,bestx)endl;98. cout此背包问题最优解为:endl;99. for(inti=1;i=n;i+)100. 101. coutbestxi;102. 103. coutendl;104. return0;105. 106. 107. template108. TypepKnap:Bound(inti)/计算节点所相应价值的上界109. 110. Typewcleft=c-cw;/剩余容量高111. Typepb=cp;/价值上界112. /以物品单位重量价值递减序装填剩余容量113. while(i=n&wi=cleft)114. 115. cleft-=wi;116. b+=pi;117. i+;118. 119. 120. /装填剩余容量装满背包121. if(i=n)122. 123. b+=pi/wi*cleft;124. 125. 126. returnb;127. 128. 129. /将一个活节点插入到子集树和优先队列中130. template131. voidKnap:AddLiveNode(Typepup,Typepcp,Typewcw,boolch,intlev)132. 133. bbnode*b=newbbnode;134. b-parent=E;135. b-LChild=ch;136. 137. HeapNodeN;138. N.uprofit=up;139. N.profit=cp;140. N.weight=cw;141. N.level=lev;142. N.ptr=b;143. 144. H-Insert(N);145. 146. 147. /优先队列式分支限界法，返回最大价值，bestx返回最优解148. template149. TypepKnap:MaxKnapsack()150. 151. H=newMaxHeapHeapNode(1000);152. 153. /为bestx分配存储空间154. bestx=newintn+1;155. 156. /初始化157. inti=1;158. E=0;159. cw=cp=0;160. Typepbestp=0;/当前最优值161. Typepup=Bound(1);/价值上界162. 163. /搜索子集空间树164. while(i!=n+1)165. 166. /检查当前扩展节点的左儿子节点167. Typewwt=cw+wi;168. if(wtbestp)171. 172. bestp=cp+pi;173. 174. AddLiveNode(up,cp+pi,cw+wi,true,i+1);175. 176. 177. up=Bound(i+1);178. /检查当前扩展节点的右儿子节点179. if(up=bestp)/右子树可能含有最优解180. 181. AddLiveNode(up,cp,cw,false,i+1);182. 183. 184. /取下一扩展节点185. HeapNodeN;186. H-DeleteMax(N);187. E=N.ptr;188. cw=N.weight;189. cp=N.profit;190. up=N.uprofit;191. i=N.level;192. 193. 194. /构造当前最优解195. for(intj=n;j0;j-)196. 197. bestxj=E-LChild;198. E=E-parent;199. 200. returncp;201. 202. 203. /返回最大价值，bestx返回最优解204. template205. TypepKnapsack(Typepp,Typeww,Typewc,intn,intbestx)206. 207. /初始化208. TypewW=0;/装包物品重量209. TypepP=0;/装包物品价值210. 211. /定义依单位重量价值排序的物品数组212. Object*Q=newObjectn;213. for(inti=1;i=n;i+)214. 215. /单位重量价值数组216. Qi-1.ID=i;217. Qi-1.d=1.0*pi/wi;218. P+=pi;219. W+=wi;220. 221. 222. if(W=c)223. 224. returnP;/所有物品装包225. 226. 227. /依单位价值重量排序228. BubbleSort(Q,n);229. 230. /创建类Knap的数据成员231. KnapK;232. K.p=newTypepn+1;233. K.w=newTypewn+1;234. 235. for(inti=1;i=n;i+)236. 237. K.pi=pQi-1.ID;238. K.wi=wQi-1.ID;239. 240. 241. K.cp=0;24