一．0／l的基本概念

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

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

    對于任意的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)開始。對于所有的x≥0，有f₀(x)

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

二．0／1背包問題的實例分析

    例11 考慮以下情況的背包問題，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

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

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

     （演示）

圖10

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

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

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

    例4．12 對于例4.11的數據，有

    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)}

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

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

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

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

    如果已找出s 的最末序偶(P1，w1)，那末，使 的x1，…．，xn的決策值可以通過檢索這些s 來確定。若(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 因此應置x3=1。序偶(6，6)是由序偶(6一p ，6一w )＝(1，2)得到的，因此(1,2)∈s 。又，(1，2)∈s ，于是應置x2=0.但(1，2) s ，從而得到xl＝1放最優解f (6)=決策序列是(xl，x2，x3)=(1，0，1)。

    對于以上所述的內容可以用一種非形式的算法過程dkP來描述。為了實現dkP，需要給出表示序偶集s 和s 的結構形式，而且要將merge—Purge過程具體化，使它能按要求歸并s 和s ，且清除一些序偶。此外，還要給出一個沿著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