动态规划解决背包问题

    背包问题(Knapsack problem)是一个动态规划问题,假设有n种货物,每种货物的的价值是v[i],重量是w[i],需要在背包负载有限的前提下求出具有最大货值的组合(策略),使用暴力算法也可以求出背包问题最优解,而利用动态规划可以将算法的复杂度降至接近于多项式复杂度,背包问题根据每种货物的数量限制可分为以下几种:

0-1背包问题:每种货物数量1件,选择每种货物的策略是取(1)还是不取(0)。

完全背包问题每种货物数量有无限个,最终的策略是每种货物取多少件。

多重背包问题每种货物的数量为有限个,但各种货物数量不一样,比如第i种货物的数量为a[i]件。

解决了完全背包问题后,通过引入数量的判断条件,就可解决其他两种背包问题。介绍背包问题算法之前先来了解一些动态规划的相关知识及术语。

一、动态规划

1.1、概念介绍

    线性规划为静态规划,而动态规划显著的特点是问题有阶段性,以下面的最短路线问题为例:

路线.png

上图中圈号代表具体的地址结点,两个结点间连线代表两地距离,最短路线问题需要求出,从出发点A到目的地E哪条路径最短。上图到达目的地可分为四个阶段,A出发选B1或B2为第一阶段,从Bi到Ci为第二阶段,Ci到Di为第三个阶段,Di到E为第四个阶段;圈内字母代表状态,每个阶段初始状态集合称为该阶段的状态,例如第一阶段状态S1={A},第二阶段状态S2={B1,B2},第三阶段状态S3={C1,C2,C3},第四阶段状态S4={D1,D2},每个阶段向下一个阶段前进时,面临着多种选择,如第一阶段向第二阶段变化时可选择A到B1或A到B2,每一种选择称为决策,决策产生新的状态用小写s表示,而每个阶段决策用小写u表示,例如选择从A到B1则有s2=B1,而选择从A到B2则有s2=B2,状态sk选择具体的决策uk后,下个阶段k+1状态往往是能确定的,称sk+1=T(sk,uk)为状态转移方程。从A到E每个阶段选择不同的决策构成一个状态序列p1,n(s1)称为策略,从k阶段开始策略称为子策略用pk,n(sk)表示,显而易见,从出发点A到目的地E有许多种策略。

    以上介绍了动态规划中状态、决策、状态转移方程、策略的概念,接下来再看与策略优化相关的概念,对于最短路线问题而言,最优的策略显然要求各个阶段路程之和最小。假设在k阶段状态为sk,采用了决策uk后得到k+1阶段的状态sk+1,用一个阶段指标函数阶段指标函数.png来量化决策uk,例如从A到B1节点有:

V阿布.png

与此类似,如决策采用A到B2节点则有:

Vb2.png

假设k阶段状态为sk,采取策略pk,n(sk)产生的一系列阶段函数之和称为指标函数:VKN.png,具体形式为:

指标函数.png

从k阶段的状态sk到最终状态sn有许多策略可用,就最短路线问题而言,最优的策略显然是指标函数值最小的策略,引入最优指标函数fk(sk):

指标函数2.png

动态规划问题归结为求解最优指标函数f1(s1),得到f1(s1)后即可得到最优策略

1.2、逆推法

    求解动态规划常用方法有逆推法和顺推法,设动态规划问题一共有n个阶段,逆推法从n阶段向前逆向推导每个阶段的最优决策,直至推导出最优指标函数f1(s1),然后利用已推导的最优决策,从开始阶段顺次得到各个阶段最优状态。以开头最短路线问题为例:

路线.png

从E点出发即k=4时:

针对D1指标函数f4(D1)=8,状态转移方程E=T(D1,u4(D1)),针对D2f4(D2)=4,状态转移方程E=T(D2,u4(D2))。

 k=3时:

f3(C1)=min{6+f4(D1),5+f4(D2)}=min{6+8,5+4}=9,从C1出发到下个阶段最优决策是选择D2,记u3(C1)=D2,在确保最短短路程的前提下,有状态转移方程D2=T(C1,u3(C1))

f3(C2)=min{2+f4(D1),3+f4(D2)}=min{2+8,3+4}=7,记u3(C2)=D2。 

f3(C3)=min{8+f4(D1),5+f4(D2)}=min{8+8,5+4}=9,记u3(C3)=D2

k=2时:

f2(B1)=min{2+f3(C1),3+f3(C2)}=min{2+9,3+7}=10,记u2(B1)=C2

f2(B2)=min{4+f3(C1),5+f3(C3)}=min{4+9,5+9}=13,记u2(B1)=C1

k=1时:

f1(A)=min{5+f2(B1),3+f2(B2)}=min{5+10,3+13}=15,记u1(A)=B1

得到最优指标函数f1(A)后即得到了问题最优值,接下来再从A出发,利用每个阶段的最优决策求出每个阶段的状态:

k=1时,由u1(A)=B1,确定路线A到B1

k=2时,由u2(B1)=C2,确定路线B1C2

k=3时,由u3(C2)=D2,确定路线C2D2

k=4时,由u4(D2)=E,确定路线D2E

综上所述,该动态规划最优路线为AB1C2D2E。

1.3、顺推法

    顺推法顾名思义是从k=1阶段开始顺序推导至k=n阶段,首先引入一个新的最优指标函数:

新指标函数.png 

上式中k表示第k阶段结束状态为sk+1时最优函数。以上图为例,C1同时连接B1和B2B1、B2是第一阶段结束状态可选集合,同时B1、B2又是第二阶段开始状态集合;而C1属于第三阶段的状态同时也是第二阶段结束状态之一。根据新指标函数.png定义有:f2(C1)=min{2+f1(B1),4+f1(B2)},逆推法的最优指标函数以开始状态作为标识,而顺推法的最优指标函数以结束状态作为标识,选择的标识不同是因两者算法差异造成的,新指标函数.png用公式可表达为:

指标函数公式.png 

①式中sk是一个变量,sk+1是一个定值,kk1.png表示状态sksk+1之间的阶段指标函数集合.png表达的是一个集合,公式中含义可根据f2(C1)的表达式对号入座来理解,特别的,设初始状态f0(s1)=0。顺推法求解上面最短路线问题即为求解最优指标函数f4(E),接下来用顺推法解决之前的最短路线问题。

k=1时,有

f1(B1)=5,u1(B1)=A;f1(B2)=3,u1(B2)=A

k=2时,有

f2(C1)=min{2+f1(B1),4+f1(B2)}=min{2+5,4+3}=7,u2(C1)=B1B2

f2(C2)=min{3+f1(B1)}=8,u2(C2)=B1

f2(C3)=min{5+f1(B1)}=8,u2(C3)=B2

k=3时,有

f3(D1)=min{6+f2(C1),2+f2(C2),8+f2(C3)}=min{6+7,2+8,8+8}=10

u3(D1)=C2

f3(D2)=min{5+f2(C1),3+f2(C2),5+f2(C3)}=min{7+7,3+8,7+8}=10

u3(D2)=C2

k=4时

f4(E)=min{8+f3(D1), 4+f3(D2)}=min{8+10,4+11}=15,u4(E)=D2

注意到顺推法得到的最优指标函数f4(E)等于逆推法得到f1(A),这是很容易理解的,A到E等效于E到A,而由决策序列:

u4(E)=D2 ,u3(D2)=C2u2(C2)=B1 ,u1(B1)=A 

可知最优策略为AB1C2D2E。

    可根据目标最优指标函数来区分使用的是逆推还是顺推法,如目标函数是形式f1(A),即以初始状态和初始阶段为最优指标函数标识符的,使用的是逆推法;而类似f4(E)以最终阶段和最终状态为函数标识符的是顺推法。

二、动态规划解决背包问题

2.1、完全背包问题

    前面介绍过,完全背包问题指的是每种货物数量不限,以下面这个问题为例,假设一辆汽车最多可运7吨货物,有甲、乙、丙三种物资,每种物资货值及重量如下表:

背包问题.png

要求出在规定核载吨位下最大货值的组合。

上述问题可转化为下面的动态规划问题:

正数规划.png

x1,x2,x3都是件数、皆为整数。对物资甲、乙、丙分三阶段分配数量,起始状态s1≤7代表待分配吨位不大于7吨,x1,x2,x3件数作为决策变量,分配完物资甲后第二阶段初始状态s2=s1-x1,与此类似,分配完物资乙后第三阶段状态s3=s2-2x2,分配完丙后s4=s3-3x3=0,有了状态转移方程之后引入最优指标函数fk(s),其意义指在装载能力不大于s的前提下,k阶段到最后第3阶段的最大货值,显然f1(7)的值即为所求的最大货值,由目标最优指标函数形式可知,将使用逆推法求解该问题,f1(7)表达式为:

f17.png

f1(7)中根据状态转移方程s2=s1-x1确定了第二阶段可分配重量,接下来逐个分析其中多项式,以f2(7)为例,f2(7)代表在第一阶段货物甲分配了0件:

f27.png

f2(6)代表第一阶段甲分配了1件

f26.png

依次可得下列公式

发22.png

f3(s3)代表第三阶段对货物丙进行分配,如f3(7)代表甲、乙都没有分配,留给货物丙的配载能力是7吨

f37.png

f3(6)代表第三阶段可分配重量为6吨

f36.png

相应的可得到第三阶段其他的指标函数

3333.png

接下来就是逆推过程了,将f3(s3)各个值代入f2(s2)各个表达式中:

f21.png

f2(s2)各个值代入f1(7)中有:

法7啊.png

如此就得到了最大货物价值为18,再来看最优策略的产生:

x1=1时即甲为1件时,对应于第二阶段f2(6):

指标f26.png

从指标函数可以看出第二阶段最优决策是x2=0,由状态方程s3=s2-2x2知,s3=6,f3(6)表达式为:

f36.png

综上所述最优策略为x1=1,x2=0,x3=2,即甲1件,乙0件,丙2件。

另外一个最优策略是当x1=0时,此时f2(7):

指标函数发77.png

第二阶段最优决策为x2=2,由状态方程s3=s2-2x2知,s3=7-4,f3(3)表达式为

份饭331.png

另一个最优策略为x1=0,x2=2,x3=1,即甲0件,乙2件,丙1件.

将上述分析利用代码实现如下:

import  numpy as np
import math
#指标函数类fk(w)
class funclass(object):
    def __init__(self,stage, weight,prevalue,laststageAmount ):
        #阶段
        self.stage=stage
        #本阶段到最后总计可分配重量
        self.weight=weight
        #子指标函数类
        self.child=[]
        #最大值
        self.value = None
        #本阶段数量上限
        self.limitamount = None
        #上一个状态下背包价值
        self.lastvalue =prevalue
        # 上一个状态下已分配数量
        self.laststageAmount=laststageAmount

#状态转移方程
def Statetransitionequation(w,v,retraint, stage, lastvaluevalue,laststageAmount  ):
    limit=math.floor(retraint/w[:,stage-1])
    f=funclass(stage  ,retraint,lastvaluevalue,laststageAmount   )
    f.limitamount=limit
    if(stage==w.shape[1]):
        f.child=None
        f.value=limit*v[:, stage - 1]
        return f
    for i in range(0,limit+1):
        f.child.append(Statetransitionequation(w, v, retraint - w[:, stage - 1] * i, stage + 1,  i * v[:, stage - 1],i))
    return f

#逆推获得每个阶段最大价值函数
def setMaxValue(f):
    if (f.child is None):
        return  f.value
    else:
        v=[]
        for c in f.child:
            if (c.value ==None):
                c.value = setMaxValue(c)
            v.append(c.lastvalue + c.value)
        return max(v)

if __name__=='__main__':
    fc=[]
    weights=np.array([[1,2,3]],dtype=np.float)
    values=np.array([[2,5,8]],dtype=np.float)
    limits=7
    root=Statetransitionequation(weights,values,limits,1, 0,0)
    #逆推法设置每个阶段最大价值
    maxvalue =setMaxValue(root)
    print('背包最大价值:%.0f'%(maxvalue))
    print('最优策略:'  )
    print('-' * 100)
    #顺推得到每个阶段件数最优值
    for s2 in root.child:
        if(s2.value+s2.lastvalue==maxvalue):
            print('x%d=%0.f' % (s2.stage-1,s2.laststageAmount ))
            for s3 in s2.child:
                if (s3.value + s3.lastvalue == s2.value):
                    print('x%d=%0.f ' % (s3.stage - 1, s3.laststageAmount ))
                    print('x%d=%0.f ' % (s3.stage  , s3.limitamount))
                    print('-'*100)



运行结果如下图

image.png

程序说明:

    funclass是阶段最优指标函数类,属性stage代表所属的阶段,weight代表从本阶段起最大可分配的重量,这两个属性分布代表最优指标函数fk(s)中的k和s,child代表下一个阶段最优指标函数集合,以f1(7)为例,child为下面集合:

-免费试读结束-
登录|注册后打赏作者吧! 0.8元