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

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

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

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

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

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

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

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