一．0／l的基本概念

    本節(jié)將使用向后處理法來(lái)求解第一課時(shí)節(jié)定義的0／1背包問(wèn)題。對(duì)于0／1背包問(wèn)題，可以通過(guò)作出變量x1，x2，…，xi的一個(gè)決策序列來(lái)得到它的解。而對(duì)變量x的決策就是決定它是取0值還是取1值。假定決策這些x的次序?yàn)閤n，xn-1：，…，x_l。在對(duì)xn作出決策之后，問(wèn)題處于下列兩種狀態(tài)之一：背包的剩余容量是m，沒(méi)產(chǎn)生任何效益；剩余容量是m—w，效益值增長(zhǎng)了p。顯然，剩余下來(lái)對(duì)xn-1，xn-2，…，x₁的決策相對(duì)于決策x所產(chǎn)生的問(wèn)題狀態(tài)應(yīng)該是最優(yōu)的，否則xn，…，x1就不可能是最優(yōu)決策序列。如果設(shè)fj(x)是knaP(1，j，x)最優(yōu)解的值，那末fn(m)就可表示為

    f_n(m)=max{{f_n-1—l(m)，f_n-1—l(m—wn)+Pn}    (13)

    對(duì)于任意的f_i(x)，這里i>o，則有

    fi(x)＝max{f_n-1(x)，f_n-1(x—w_i)+Pi}    (14)

    為了能由前向后遞推而最后求解出f_n(m)，需從f₀(x)開(kāi)始。對(duì)于所有的x≥0，有f₀(x)

＝0，當(dāng)x<0時(shí)，有f₀(x)＝一∞。根據(jù)(14)，馬上可求解出0≤x<w₁和x≥w₁情況下f₁(x)的值。接著又可由(14)不斷遞推求出f₂,f₃…，f。在x相應(yīng)取值范圍內(nèi)的值。

二．0／1背包問(wèn)題的實(shí)例分析

    例11 考慮以下情況的背包問(wèn)題，n=3，(w₁，w₂,w₃)＝(2，3，4)，(p2，p3，p4)＝(1，2，5)和m=6。

    利用(14)式遞推求解如下：

                   f₀(x)=         

f₁(x)=

f₂(x)=           

f₃(m)=max{3,1+5}=6

 因此，背包問(wèn)題knaP(1，3，6)的最優(yōu)解為6。通過(guò)檢查f_i的取值情況可以確定獲得最優(yōu)解的最優(yōu)決策序列。x₃的取值很容易確定，因?yàn)閒₃(m)＝6是在x₃=1的情況下取得的，所以x₃＝1。f₃(m)-p3＝1，f₂(x)和f₁(x)都可取值1，因此x₂＝0。f。不能取1，故x₁＝1。于是最優(yōu)決策序列(x₁，x₂，x₃)＝(1，0，1)。

事實(shí)上，此問(wèn)題用圖解法求解是非常容易的。圖4.10顯示了f₁,f₂和f₃的圖解過(guò)程。第一列的圖給出了函數(shù)f_i-1(x—wi)+P_i的圖像，將f_i-1(x)在x軸上右移w_i個(gè)單位然后上移P_i個(gè)單位就得到它的圖像。第二列給出由(14)式所得到的函數(shù)f_i(x)，即它由f_i-1 (x)和f_i-1(x-w_i)+p_i的函數(shù)曲線按x相同時(shí)取大值的規(guī)則歸并而成。

     （演示）

圖10

    由圖10可以看出以下幾點(diǎn)：每一個(gè)f_i完全由一些序偶(P_j，w_j)力組成的集合所說(shuō)明，其中w_j是使f_i在其處產(chǎn)生一次階躍的x值，P_j＝f_i(w)力。第一對(duì)序偶是(P。，w。)＝(0,0)。如果有r次階躍，就還要知道r對(duì)序偶(P_j，w_j)，1≤j≤r。如果假定w_j<wj+1，0≤j<r，那末，由(14)式可得P_j<Pj+1。此外，在0≤j<r的情況下，對(duì)于所有使得wj≤x<wj+1的x ,有f_i(x)＝f_i(w_j)。而對(duì)于所有滿足x≥w_r的x，有f_i(x)＝f_i(w_r)。設(shè)s^i-1是f_i-1的所有序偶的集合，s 是f_i-1(x-wi)+Pi的所有序偶的集合。把序偶(Pi，w_i) 加到s^i-1中，每一對(duì)序偶就得到s 。

           s ＝{(P，w)|(P—pi，w—wi) s^i-1}。    (15)

    在(14)式中，取f_i-1(x)和f_i-1(x—w) +P的最大值，在這里相當(dāng)于在下述支配規(guī)則下將s^i-1和s 歸并成sⁱ。如果s^i-1和s 之一有序偶(P_j,w_j)，另一有序偶(P_k，w_k)，并且在w_j≥wk的同時(shí)有P_j≤Pk，那末，序偶(P_j，w_j)被舍棄。顯然，這就是(4.14)式的求最大值的運(yùn)算。fi(wj)＝max{Pj，Pk}＝Pk。

    例4．12 對(duì)于例4.11的數(shù)據(jù)，有

    s ={(0，0)}    s ＝{(1，2)}；

    s ＝{(0，0)，(1，2)}    s ={(2，3)，(3，5))

    s ＝{(0，0)，(1，2)，(2，3)，(3，5)}

    s ＝{(5，4)，(6，6)，(7，7)，(8，9)}

    s ＝{(0，0)，(1，2)，(2，3)，(5，4)，(6，6)，(7，7)，(8，9)}

根據(jù)支配規(guī)則，在s 中刪去了序偶(3，5)。

    s 的上述計(jì)算過(guò)程也可由以下推理得出。在用直接枚舉法求解0／1背包問(wèn)題時(shí)，由于每個(gè)xi的取值只能為0或1，因此x1，x2，…，xn有2 個(gè)不同的0、1值序列。對(duì)于每一序列，若把 記為wj， 記為Pj，則此序列產(chǎn)生一對(duì)與之對(duì)應(yīng)的序偶(Pj，wj)。在這2 個(gè)序偶中，滿足wj≤m，且使Pj取最大值的序偶就是背包問(wèn)題的最優(yōu)解。在用動(dòng)態(tài)規(guī)劃的向后處理法求解0／1背包問(wèn)題時(shí)，假定s 是以下序偶所組成的集合，這些序偶是由x1，xc2…xi-1的2 個(gè)決策序列中一些可能的序列所產(chǎn)生的序偶(Pj，wj)。那末，s 可按下述步驟得到。在xi=0的情況下，產(chǎn)生的序偶集與s 相同。而在xi取1值的情況下，產(chǎn)生的序偶集是將(pi，wi)加到s 的每一對(duì)序偶(Pj，wj)得到的，這序偶集就是(15)式所描述的s 。然后根據(jù)支配規(guī)則將s 和s 歸并在一起就得到s 。這樣歸并的正確性證明如下：假定s 和s 之一包含(Pj,wj)，另一包含(Pk，wk)，并且有wj≥wk和Pj≤Pk。由于任何可行的子決策序列xi+1…，xn都必須滿足 ，當(dāng)然也需滿足 。在這種情況下， 它表明(Pj，wj)導(dǎo)致的解比(Pk，wk)能得到的最好解要差，因此根據(jù)支配規(guī)則在歸并和s 時(shí)舍棄(Pj,wj)是正確的。這里稱(pk，wk)支配(Pj，wj)。此外，在生成序偶集s 的時(shí)候，還應(yīng)將w>m的那些序偶(P，w)也清除掉，因?yàn)橛伤鼈儾荒軐?dǎo)出滿足約束條件的可行解。

     這樣生成的s的所有序偶，是背包問(wèn)題knaP(1,i,x)在0≤x≤m各種取值下的最優(yōu)解(注意s 是由一些序偶構(gòu)成的有序集合)。通過(guò)計(jì)算s 可以找到knaP(1，n,x)，0≤x≤m的所有解。knaP(1，n，m)的最優(yōu)解f(m)由s 的最后一對(duì)序偶的P值給出。

    由于實(shí)際上只需要knaP(1，n，m)的最優(yōu)解，它是由s 的最末序偶(P，w)給出的。而s 的這最末序偶或者是s 的最末序偶，或者是(Pj十Pn, wj+wn)，其中(Pj，wj)∈s 且wj是s 中滿足wj+wn≤m的最大值。因此只需按上述求出s 的最末序偶，無(wú)需計(jì)算出s也一樣滿足求knaP(1，n，m)最優(yōu)解的要求，

    如果已找出s 的最末序偶(P1，w1)，那末，使 的x1，…．，xn的決策值可以通過(guò)檢索這些s 來(lái)確定。若(P1．，w1)∈s ，則置xn=0若(Pl，wi) s ，則(Pl—Pn，w1一wn)∈s ,并且置xn=1。然后，再判斷留在s 中的序偶(P1，w1)或者(Pl—pn,w1一wn)是否屬于 以確定x 的取值，等等。

    例4。13 由例4．12，在m=6的情況下，f (6)的值由s 中的序偶(6，6)給出。(6,6) s 因此應(yīng)置x3=1。序偶(6，6)是由序偶(6一p ，6一w )＝(1，2)得到的，因此(1,2)∈s 。又，(1，2)∈s ，于是應(yīng)置x2=0.但(1，2) s ，從而得到xl＝1放最優(yōu)解f (6)=決策序列是(xl，x2，x3)=(1，0，1)。

    對(duì)于以上所述的內(nèi)容可以用一種非形式的算法過(guò)程dkP來(lái)描述。為了實(shí)現(xiàn)dkP，需要給出表示序偶集s 和s 的結(jié)構(gòu)形式，而且要將merge—Purge過(guò)程具體化，使它能按要求歸并s 和s ，且清除一些序偶。此外，還要給出一個(gè)沿著s ，…，s 回溯以確定xn，…，x1的0、1值的算法。

    算法6 非形式化的背包算法

    line procedure dkP(p，w，n，m)

1    s <--{(0，0)}

2    for i+1 to n一1 do

3    s ß{(P1，w1)/(P1一Pi，wl—wi)∈ and w1≤m}

4    si<--merge—Purge(s ，s )

5    repeat

6    (Px，wx)ßs 的最末序偶

7    (wy>Py)ß(P1+pn,w1+wn)其中，w1是s 中使得w+wn≤m的序偶中取最大值w

／／沿s ，…，s 回溯確定xn，xn-1,...，x1的取值／／

8    if Px>Py then xn<--0 ／／Px是s 的最末序偶／／

9     else xn<--1 ／／Py是s’的最末序偶／／

10    endif

11    回溯確定xn-1，…，xl

12    end dkP