算法設(shè)計與分析 背包問題

1、0101背包問題的分枝－限界法背包問題的分枝－限界法用優(yōu)先隊列式分枝限界法解決01背包問題(作為極大化問題)，需要確定以下四個問題：解空間樹中結(jié)點的結(jié)構(gòu)、如何生成一個給定結(jié)點的兒子、如何組織活結(jié)點表、如何識別答案結(jié)點。我們采用完整的二叉樹作為解空間樹，放在活結(jié)點表中的每個結(jié)點具有6個信息段：Parent、Level、Tag、CC、CV、CUB。其中Parent是結(jié)點X的父親結(jié)點連接指針；Level標志出結(jié)點X在解空間樹中的級數(shù)，通過置表

2、1)(?XLevelX示生成X的左兒子，置表示生成X的右兒子；信息段Tag用來輸出0)(?XLevelX最優(yōu)解各個分量的值；信息段CC記錄背包在結(jié)點X處的可用空間(即剩余空ix間)，在確定X左兒子的可行性時用；CV記錄在結(jié)點X處背包中已裝物品的價值(或效益值)，等于；信息段CUB用來存放結(jié)點X的Pvu值。這里，???)(1XLeveliiixpPvu表示在結(jié)點X所表示的狀態(tài)下，可行解所能達到的可能值的上界。也即是說，當?shù)闹荡_定后，可行解

3、所能達到的效益值的上界。11?lxx?nllxxxx??11?類似地，當?shù)闹荡_定后，可行解所能達到的最大效益11?lxx?nllxxxx??11?值的下界記做Pvl。如果到目前為止所知道的可行解的最大效益值CV不小于Pvl，則當PvuCV時，就應(yīng)該殺死結(jié)點X。所以，Pvu(X)可以作為限界函數(shù)和優(yōu)先級函數(shù)。關(guān)于它們的計算將由一個子程序給出。作為極大化問題處理的優(yōu)先隊列式分枝限界法解01背包問題的程序LCKNAP采用了六個子程序：LUBo

4、und、NewNode、Finish、Init、GetNode和Largest。子程序LUBound計算Pvl和Pvu之用；NewNode生成一個具有六個信息段的結(jié)點，給各個信息段置入適當?shù)闹?，并將此結(jié)點加入結(jié)點表；Finish打印出最優(yōu)解的值和此最優(yōu)解中的物品；Init對可用結(jié)點表和活結(jié)點表置1?ix初值；GetNode取一個可用結(jié)點；Largest在活結(jié)點表中取一個具有最大Pvu值結(jié)點作為下一個擴展結(jié)點。程序82101背包問題的優(yōu)先

5、隊列式分枝限界算法LCKNAP(PWMN?)假定物品的排列順序遵循P[i]W[i]?P[i1]W[i1]；realrealP[1:N]W[1:N]MCLPvlPvucapcvprevintegerintegerANS，X，N；prev=Pvl?Pvu，所以將X加入活結(jié)點表。由于左兒子的下界、上界與E的相同，因而不必再計算。但是右兒子則不同，所以需要調(diào)用函數(shù)LUBound來獲取CUB(Y)=Pvu.如果Pvu?prev則殺死結(jié)點Y(即，不

6、放在結(jié)點表中)。否則，將結(jié)點Y加入活結(jié)點表，并修改prev的值（第19行）。以下附上前面提到的幾個子程序。程序822計算結(jié)點狀態(tài)下的可能取得最大效益值的上、下界LUBound(PWrwcpNkPvlPvu)rw是背包的剩余容量，cp是已取得的效益值，還有物品k…N要考慮Pvl=cpc=rwffifromfromktotoNdodoififcW[i]thenthenPvu=PvlcP[i]W[i]從第k件到第N件至少有一件物品不能裝進背包

7、的情形出現(xiàn)ffjfromfromi1totoNdodoififc?W[j]thenthenc=cW[j]Pvl=PvlP[j]endifendifendfendfreturnreturn此時PvlPvuendifendifc=cW[i]Pvl=PvlP[i]endfendfPvu=Pvl從第k件物品到第N件物品都能裝進背包的情形出現(xiàn)endendLUBound程序823程序生成新結(jié)點算法NewNodeNewNode(parlevtcapc