算法设计与分析 背包问题.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，则当Pvu<CV时，就应该杀死结点X。所以，Pvu(X)可以作为限界函数和优先级函数。关于它们的计算将由一个子程序给出。
作为极大化问题处理的优先队列式分枝限界法解0/1背包问题的程序LCKNAP采用了六个子程序：LUBound、NewNode、Finish、Init、GetNode和Largest。子程序LUBound计算Pvl和Pvu之用；NewNode生成一个具有六个信息段的结点，给各个信息段置入适当的值，并将此结点加入结点表；Finish打印出最优解的值和此最优解中的物品；Init对可用结点表和活结点表置初值；GetNode取一个可用结点；Largest在活结点表中取一个具有最大Pvu值结点作为下一个扩展结点。

程序8-2-1 0/1背包问题的优先队列式分枝限界算法
LCKNAP(P,W,M,N,e)//假定物品的排列顺序遵循 P[i]/W[i]³P[i+1]/W[i+1]；
real P[1:N],W[1:N],M,CL,Pvl,Pvu,cap,cv,prev;
integer ANS，X，N；
1． Init；//初始化可用结点表及活结点表
2． GetNode(E)；//生成根结点
3． Parent(E)=0;Level=1;CC(E)=M;CV(E)=0;
4． LUBound(P,W,M,0, N,1,Pvl,Pvu);
5． prev=Pvl-e;CUB(E)=Pvu;
6． Loop
7． i=Level(E); cap=CC(E); cv=CV(E);
8. case
9. :i=N+1: //解结点
10. if cv>prev then
11. prev=cv; ANS=E;
12. endif
13. :else: //E是内部结点，有两个儿子
14． if cap³W[i] then //左儿子可行
15． NewNode(E,i+1,1,cap-W[i],cv+P[i],CUB(E));
16. endif
17. LUBound(P,W,cap,cv,N,i+1,Pvl,Pvu);
18. if Pvu>prev then //右儿子会活
19. NewNode(E,i+1,0,cap,cv,Pvu);
prev=max(prev,Pvl-e);
20. endif
21. endcase
22. if 不再有活结点 then exit endif
23. Largest(E)；//取下一个扩展结点
24. until CUB(E)£ prev endloop
25. Finish(cv,ANS,N);
26. end LCKNAP
算法中有两点值得注意：(1).第6～24行的循环依次检查所生成的每个结点。此循环在以下两种情况下终止：或者活结点队列为空，或者为了扩展而选择的结点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.如果Pvu£prev,则杀死结点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 do
if c<W[i] then Pvu=Pvl+c*P[i]/W[i];
// 从第k件到第N件至少有一件物品不能装进背包的情形出现
for j from i+1 to N do
if c³W[j] then
c=c-W[j]; Pvl=Pvl+P[j];
endif
endfor
return //此时Pvl < Pvu
endif
c=c-W[i]; Pvl=Pvl+P[i];
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);
endif
ANS=Parent(ANS);
endfor
end Finish

例子 n=4, P=(10,10,13,18), W=(2,4,6,9), M=15. 试绘出算法LCKNAP求最优解的检索过程。