算法设计与分析 背包问题.doc

0/1背包问题的分枝限界法用优先队列式分枝限界法解决0/1背包问题(作为极大化问题)，需要确定以下四个问题：解空间树中结点的结构、如何生成一个给定结点的儿子、如何组织活结点表、如何识别答案结点。 我们采用完整的二叉树作为解空间树，放在活结点表中的每个结点具有6个信息段：Parent、Level、Tag、CC、CV、CUB。其中Parent是结点X的父亲结点连接指针；Level标志出结点X在解空间树中的级数，通过置表示生成X的左儿子，置表示生成X的右儿子；信息段Tag用来输出最优解各个分量的值；信息段CC记录背包在结点X处的可用空间(即剩余空间)，在确定X左儿子的可行性时用；CV记录在结点X处背包中已装物品的价值(或效益值)，等于；信息段CUB用来存放结点X的Pvu值。这里，Pvu表示在结点X所表示的状态下，可行解所能达到的可能值的上界。也即是说，当的值确定后，可行解所能达到的效益值的上界。类似地，当的值确定后，可行解所能达到的最大效益值的下界记做Pvl。如果到目前为止所知道的可行解的最大效益值CV不小于Pvl，则当Pvuprev then11. prev=cv; ANS=E;12. endif13. :else: /E是内部结点，有两个儿子14 if capWi then /左儿子可行15 NewNode(E,i+1,1,cap-Wi,cv+Pi,CUB(E);16. endif17. LUBound(P,W,cap,cv,N,i+1,Pvl,Pvu);18. if Pvuprev then /右儿子会活19. NewNode(E,i+1,0,cap,cv,Pvu); prev=max(prev,Pvl-e);20. endif21. endcase22. if 不再有活结点 then exit endif23. Largest(E)；/取下一个扩展结点24. until CUB(E) prev endloop25. Finish(cv,ANS,N);26. end LCKNAP算法中有两点值得注意：(1).第624行的循环依次检查所生成的每个结点。此循环在以下两种情况下终止：或者活结点队列为空，或者为了扩展而选择的结点E（扩展结点）满足CUB(E) prev.在后一种情况下，由扩展结点的选法可知，对所有的扩展结点X均有CUB(X) CUB(E) prev，因而它们都不能导致其值比prev更大的解。(2).在左儿子X可行的情况下，由LUBound算出它的上界，并由此而得CUB(X)=CUB(E).因为CUB(E)prev或者prev=Pvl-e Pvu，所以将X加入活结点表。由于左儿子的下界、上界与E的相同，因而不必再计算。但是右儿子则不同，所以需要调用函数LUBound来获取CUB(Y)= Pvu.如果Pvuprev,则杀死结点Y(即，不放在结点表中)。否则，将结点Y加入活结点表，并修改prev的值（第19行）。以下附上前面提到的几个子程序。 程序8-2-2 计算结点状态下的可能取得最大效益值的上、下界 LUBound(P,W,rw,cp,N,k,Pvl,Pvu)/rw是背包的剩余容量，cp是已取得的效益值，还有物品k,N要考虑 Pvl=cp; c=rw; for i from k to N doif cWi then Pvu=Pvl+c*Pi/Wi;/ 从第k件到第N件至少有一件物品不能装进背包的情形出现 for j from i+1 to N do if cWj then c=c-Wj; Pvl=Pvl+Pj; endif endfor return /此时Pvl Pvuendifc=c-Wi; Pvl=Pvl+Pi; endfor Pvu= Pvl; / 从第k件物品到第N件物品都能装进背包的情形出现, end LUBound 程序8-2-3 程序生成新结点算法NewNode(par,lev,t,cap,cv,ub)/生成一个新结点J，并把它加到/活结点表 GetNode(J); Parent(J)=par;Level(J)=lev;Tag(J)=t; CC(J)=cap; CV(J)=cv; CUB(J)=ub; Add(J);end NewNode 程序8-2-4 打印答案程序Finish(CV,ANS,N)/输出解 real CV; global Tag,Parent; print(OBJECTS IN KNAPSACK ARE)for j from N by 1 to 1 do if Tag(ANS)=1 then print(j); end