3、队列式分枝限界法解0/1背包问题的程序LCKNAP采用了六个子程序:LUBound、NewNode、Finish、Init、GetNode和Largest。子程序LUBound计算Pvl和Pvu之用;NewNode生成一个具有六个信息段的结点,给各个信息段置入适当的值,并将此结点加入结点表;Finish打印出最优解的值和此最优解中的物品;Init对可用结点表和活结点表置初值;GetNode取一个可用结点;Largest在活结点表中取一个具有最大Pvu值结点作为下一个扩展结点。程序8-2-10/1背包问题的优先队列式分枝限界算法L
4、CKNAP(P,W,M,N,e)//假定物品的排列顺序遵循P[i]/W[i]³P[i+1]/W[i+1];realP[1:N],W[1:N],M,CL,Pvl,Pvu,cap,cv,prev;integerANS,X,N;1.Init;//初始化可用结点表及活结点表1.GetNode(E);//生成根结点2.Parent(E)=0;Level=1;CC(E)=M;CV(E)=0;3.LUBound(P,W,M,0,N,1,Pvl,Pvu);4.prev=Pvl-e;CUB(E)=Pvu;5.Loop6.i=Level(E);ca
5、p=CC(E);cv=CV(E);8.case9.:i=N+1://解结点10.ifcv>prevthen11.prev=cv;ANS=E;12.endif13.:else://E是内部结点,有两个儿子14.ifcap³W[i]then//左儿子可行15.NewNode(E,i+1,1,cap-W[i],cv+P[i],CUB(E));16.endif17.LUBound(P,W,cap,cv,N,i+1,Pvl,Pvu);18.ifPvu>prevthen//右儿子会活19.NewNode(E,i+1,0,cap,cv,Pvu
6、);prev=max(prev,Pvl-e);20.endif21.endcase22.if不再有活结点thenexitendif23.Largest(E);//取下一个扩展结点24.untilCUB(E)£prevendloop25.Finish(cv,ANS,N);26.endLCKNAP算法中有两点值得注意:(1).第6~24行的循环依次检查所生成的每个结点。此循环在以下两种情况下终止:或者活结点队列为空,或者为了扩展而选择的结点E(扩展结点)满足CUB(E)£prev.在后一种情况下,由扩展结点的选法可知,对所有的扩展结
7、点X均有CUB(X)£CUB(E)£prev,因而它们都不能导致其值比prev更大的解。(2).在左儿子X可行的情况下,由LUBound算出它的上界,并由此而得CUB(X)=CUB(E).因为CUB(E)>prev或者prev=Pvl-e8、个子程序。程序8-2-2计算结点状态下的可能取得最大效益值的上、下界LUBound(P,W,rw,cp,N,k,Pvl,Pvu)//rw是背包的剩余容量,cp是已取得的效益值,还有物品k,…,N要考虑Pvl=cp;c=rw;forifromktoNdoifc