随笔-48  评论-259  文章-1  trackbacks-0

一.0/l的基本概念

    本节将使用向后处理法来求解第一课时节定义的0/1背包问题。对于0/1背包问题,可以通过作出变量x1,x2,xi的一个决策序列来得到它的解。而对变量x的决策就是决定它是取0值还是取1值。假定决策这些x的次序为xn,xn-1:,xl。在对xn作出决策之后,问题处于下列两种状态之一:背包的剩余容量是m,没产生任何效益;剩余容量是mw,效益值增长了p。显然,剩余下来对xn-1,xn-2,x1的决策相对于决策x所产生的问题状态应该是最优的,否则xn,x1就不可能是最优决策序列。如果设fj(x)是knaP(1,j,x)最优解的值,那末fn(m)就可表示为

    fn(m)=max{{fn-1l(m),fn-1l(mwn)+Pn}    (13)

    对于任意的fi(x),这里i>o,则有

    fi(x)=max{fn-1(x),fn-1(xwi)+Pi}    (14)

    为了能由前向后递推而最后求解出fn(m),需从f0(x)开始。对于所有的x0,有f0(x)

0,当x<0时,有f0(x)=一。根据(14),马上可求解出0x<w1xw1情况下f1(x)的值。接着又可由(14)不断递推求出f2,f3f。在x相应取值范围内的值。

二.0/1背包问题的实例分析

    例11 考虑以下情况的背包问题,n=3,(w1w2,w3)=(2,3,4),(p2,p3,p4)=(1,2,5)和m=6。

    利用(14)式递推求解如下:

                   f0(x)=         

f1(x)=

f2(x)=           

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

 因此,背包问题knaP(1,3,6)的最优解为6。通过检查fi的取值情况可以确定获得最优解的最优决策序列。x3的取值很容易确定,因为f3(m)=6是在x3=1的情况下取得的,所以x31。f3(m)-p3=1,f2(x)和f1(x)都可取值1,因此x20。f。不能取1,故x11。于是最优决策序列(x1x2x3)=(1,0,1)。

事实上,此问题用图解法求解是非常容易的。图4.10显示了f1,f2f3的图解过程。第一列的图给出了函数fi-1(xwi)+Pi的图像,将fi-1(x)在x轴上右移wi个单位然后上移Pi个单位就得到它的图像。第二列给出由(14)式所得到的函数fi(x),即它由fi-1 (x)和fi-1(x-wi)+pi的函数曲线按x相同时取大值的规则归并而成。

     (演示)

10

    由图10可以看出以下几点:每一个fi完全由一些序偶(Pj,wj)力组成的集合所说明,其中wj是使fi在其处产生一次阶跃的x值,Pjfi(w)力。第一对序偶是(P。,w。)=(0,0)。如果有r次阶跃,就还要知道r对序偶(Pj,wj),1jr。如果假定wj<wj+1,0j<r,那末,由(14)式可得Pj<Pj+1。此外,在0j<r的情况下,对于所有使得wjx<wj+1x ,有fi(x)=fi(wj)。而对于所有满足xwrx,有fi(x)=fi(wr)。设si-1fi-1的所有序偶的集合,s fi-1(x-wi)+Pi的所有序偶的集合。把序偶(Pi,wi) 加到si-1中,每一对序偶就得到s

           s ={(P,w)|(Ppi,wwi) si-1}。    (15)

    在(14)式中,取fi-1(x)和fi-1(xw) +P的最大值,在这里相当于在下述支配规则下将si-1和s 归并成si。如果si-1和s 之一有序偶(Pj,wj),另一有序偶(Pk,wk),并且在wjwk的同时有PjPk,那末,序偶(Pj,wj)被舍弃。显然,这就是(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 个序偶中,满足wjm,且使Pj取最大值的序偶就是背包问题的最优解。在用动态规划的向后处理法求解0/1背包问题时,假定s 是以下序偶所组成的集合,这些序偶是由x1,xc2xi-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),并且有wjwk和PjPk。由于任何可行的子决策序列xi+1xn都必须满足 ,当然也需满足 。在这种情况下, 它表明(Pj,wj)导致的解比(Pk,wk)能得到的最好解要差,因此根据支配规则在归并和s 时舍弃(Pj,wj)是正确的。这里称(pk,wk)支配(Pj,wj)。此外,在生成序偶集s 的时候,还应将w>m的那些序偶(P,w)也清除掉,因为由它们不能导出满足约束条件的可行解。

     这样生成的s的所有序偶,是背包问题knaP(1,i,x)在0xm各种取值下的最优解(注意s 是由一些序偶构成的有序集合)。通过计算s 可以找到knaP(1,n,x),0xm的所有解。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+wnm的最大值。因此只需按上述求出s 的最末序偶,无需计算出s也一样满足求knaP(1,n,m)最优解的要求,

    如果已找出s 的最末序偶(P1,w1),那末,使 的x1,.,xn的决策值可以通过检索这些s 来确定。若(P1.,w1)s ,则置xn=0若(Pl,wi) s ,则(PlPn,w1一wn)s ,并且置xn=1。然后,再判断留在s 中的序偶(P1,w1)或者(Plpn,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 的结构形式,而且要将mergePurge过程具体化,使它能按要求归并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,wlwi) and w1m}

4    si<--mergePurge(s ,s )

5    repeat

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

7    (wy>Py)ß(P1+pn,w1+wn)其中,w1是s 中使得w+wnm的序偶中取最大值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                                                            

 

 

posted on 2007-06-19 12:05 星梦情缘 阅读(6137) 评论(0)  编辑 收藏 引用 所属分类: 算法分析

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理