一．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