算法设计与分析 背包问题

《算法设计与分析 背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0/1背包问题的分枝－限界法用优先队列式分枝限界法解决0/1背包问题(作为极大化问题)，需要确定以下四个问题：解空间树中结点的结构、如何生成一个给定结点的儿子、如何组织活结点表、如何识别答案结点。我们采用完整的二叉树作为解空间树，放在活结点表中的每个结点具有6个信息段：Parent、Level、Tag、CC、CV、CUB。其中Parent是结点X的父亲结点连接指针；Level标志出结点X在解空间树中的级数，通过置表示生成X的左儿子，置表示生成X的右儿子；信息段Tag用来输出最优解各个分量的值；信息段CC记录背包在结点X处的可用空

2、间(即剩余空间)，在确定X左儿子的可行性时用；CV记录在结点X处背包中已装物品的价值(或效益值)，等于；信息段CUB用来存放结点X的Pvu值。这里，Pvu表示在结点X所表示的状态下，可行解所能达到的可能值的上界。也即是说，当的值确定后，可行解所能达到的效益值的上界。类似地，当的值确定后，可行解所能达到的最大效益值的下界记做Pvl。如果到目前为止所知道的可行解的最大效益值CV不小于Pvl，则当Pvu

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-e

8、个子程序。程序8-2-2计算结点状态下的可能取得最大效益值的上、下界LUBound(P,W,rw,cp,N,k,Pvl,Pvu)//rw是背包的剩余容量，cp是已取得的效益值，还有物品k,…,N要考虑Pvl=cp;c=rw;forifromktoNdoifc