背包问题

2020-02-07 本文已影响0人 0HP

0-1背包问题

基本模型：有n种物品，1个背包；n种物品各有价值 $v_i$ 与重量 $w_i$ ，背包有容量限制 $W$ 。求用该背包放哪些物品使得价值最高，且每种物品只有一个。
即解题思路是：对于每种件物品，要么放入背包，要么不放两种状态。故称零幺背包问题。

解题方法：动态规划思想（拒绝暴力）

每一步的新状态（针对每种物件）为：维持原状态或取该物件，以此不断递归。
即状态转移基本模型为：
$Bag[i][j]= \begin{cases} Bag[i-1][j]& \text {j<w[i]}\\[2ex] max(Bag[i-1][j],Bag[i-1][j-w[i]]+v[i]) & \text {j>=w[i]}\\ \end{cases}$
其中 $i$ 表示物品的序号， $j$ 表示背包空间， $Bag[x][y]$ 表示当前总价值。 $Bag[i-1][j]$ 表示上一状态总价值， $Bag[i-1][j-w[i]]+v[i]$ 表示取当前物品，加上取该物品后，背包剩余空间时的最优状态（因为每一步都是取最优，整体亦是最优）。
具体解题时，用一个二维表表示，行为物品，列为空间，按行依次遍历。

例题：

有4件物品，重量分别为 $[2,1,3,2]$ ，价值分别为 $[3,2,4,2]$ ，背包空间为5。
按以上公式结合二维表解题

bag.jpg

解题分析：右下角的7为最终结果，其由第三行的7通过 $Bag[i][j]=Bag[i-1][j]$ 得来。而第三行的7是通过 $Bag[i][j]=Bag[i-1][j-w[i]]+v[i]$ 得来。直观理解为把第三件物品放入包后（价值为4），包剩下空间2，那么加上背包空间为2时的最优状态，即第二行第三列黑色的3，依次思想解题。

伪代码如下：

def Bag(w,v,W):
    #初始化第一行
    for j in range(W+1):
        bag[0][j]=0
    #初始化第一列
    for i in range(len(v)+1):
        bag[i][0]=0

    for i in range(1,len(v)+1):
        for j in range(1,W+1):
            if j<w[i]:
                bag[i][j]=bag[i-1][j]
            else:
                bag[i][j]=max(bag[i-1][j],bag[i-1][j-w[i]]+v[i])
    return bag[len(v)][W]

背包问题的空间优化

上述解法采用二维数组，其空间复杂度为 $O(nW)$ （二维表的空间）。而仔细观察模型解题过程，其实 $Bag[i][]$ 只是与 $Bag[i-1][]$ 有关，换言之，当前数组只与上一数组的值有关，与 $Bag[i-2][]$ 无关，即言其他的其实不用存储。只需要有一个一维数组存储即可。
伪代码如下：

def bag(w,v,W):
    count=len(w)
    dp=[0 for i in range(W+1)]

    for i in range(count):
        j=W
        while not j<w[i]:
            dp[j]=max(dp[j],dp[j-w[i]]+v[i])
            j-=1
    return dp[-1]

注意：用一维数组表示时，必须逆序更新。
其直观理解为：一个背包的当前状态（当前剩余空间），取决于装下当前物品后价值是否更高。若是，则更新，若不是，便保持原状。

完全背包问题

问题模型：在零幺背包问题的基础上，修改为每种物品数量有任意个。
即背包允许放多个同种物品，使得总价值最优，此种条件下，每一种物品便不止只有两种状态，而有 $k$ 种状态，其中 $k$ 满足 $0<=k\ \& \ k*w[i]<j$ 。

那么状态转移方程便改为：
$Bag[i][j]= \begin{cases} Bag[i-1][j]& \text {$j<w[i]$}\\[2ex] max(Bag[i-1][j],Bag[i-1][j-k \cdot w[i]]+k \cdot v[i]) & \text {$j>=k \cdot w[i]$}\\ \end{cases}$
伪代码为：

def Bag(w,v,W):
    #初始化第一行
    for j in range(W+1):
        bag[0][j]=0
    #初始化第一列
    for i in range(len(v)+1):
        bag[i][0]=0

    for i in range(1,len(v)+1):
        for j in range(1,W+1):
            if j<w[i]:
                bag[i][j]=bag[i-1][j]
            else:
                for k in range(W//w[i]):
                    bag[i][j]=max(bag[i-1][j],bag[i-1][j-k*v[i]]+k*v[i])
                
    return bag[len(v)][W]

但是这样搞时间复杂度非常高：为 $O(nW^2)$ ，所以为了人与电脑和谐相处，必须优化。

完全背包问题时间优化

实质上，问题仅是转化为：从取0个当前物品，取1个当前物品......取k个当前物品这k+1个情况中，选择价值最大一那个，即
$Bag[i][j]=max(Bag[i-1][j-k*w[i]]+k*v[i])$
其中 $k$ 满足 $0<=k\ \&\ k*w[i]<j$ 。换言之，可选方案如下：

$Bag[i-1][j-0*w[i]]+0*v[i]\\ Bag[i-1][j-1*w[i]]+1*v[i]\\ Bag[i-1][j-2*w[i]]+2*v[i]\\ ......\\ Bag[i-1][j-k*w[i]]+k*v[i]$

亦可写成
$Bag[i-1][j]\\ Bag[i-1][j-w[i]]+v[i]\\ Bag[i-1][j-w[i]-w[i]]+v[i]+v[i]\\ ......\\ Bag[i-1][j-w[i]-(k-1)w[i]]+(k-1)*v[i]+v[i]\\$
利用换元法：令 $j-w[i]=t,k-1=c$ 得以上方程，除第零行外，其余可表示为
$(Bag[i-1][t])+v[i]\\ (Bag[i-1][t-w[i]]+v[i])+v[i]\\ .......\\ (Bag[i-1][t-c*w[i]]+c*v[i])+v[i]$
将 $t=j-w[i]$ 代回去，得到 $Bag[i-1][j-w[i]-c*w[i]]+c*v[i]+v[i]$ ，
$由于Bag[i][j]=max(Bag[i-1][j-k*w[i]]+k*v[i])$
$得Bag[i][j-w[i]]=max(Bag[i-1][j-w[i]-c*w[i]]+c*v[i])$
$总之：得Bag[i][j]=max(Bag[i-1][j](第零行),max(Bag[i][j-w[i]]+v[i]))$
伪代码如下：

def Bag(w,v,W):
    #初始化第一行
    for j in range(W+1):
        bag[0][j]=0
    #初始化第一列
    for i in range(len(v)+1):
        bag[i][0]=0

    for i in range(1,len(v)+1):
        for j in range(1,W+1):
            if j<w[i]:
                bag[i][j]=bag[i-1][j]
            else:
                bag[i][j]=max(bag[i-1][j],bag[i][j-w[i]]+v[i])
                
    return bag[len(v)][W]

多重背包问题

多重背包问题与完全背包问题类似，只不过是每件物品有数量限制，而非完全背包的无限个。
即问题描述为：有一个背包载重为 $W$ ， $n$ 种物品质量和价值分别为 $w[i],v[i]$ ，且每种物品各有 $M[i]$ 个。求背包价值最高状态。

其实，解题思路仅是从完全背包问题基础上，对数量 $k$ 加一限制即可
$Bag[i][j]=max(Bag[i-1][j],Bag[i-1][j-k*w[i]]+k*v[i])(k\in [0,M[i]])$

然而这样时空复杂度都较高，需要优化

多重背包二进制优化

此种优化主要是将 $k$ 分解，类似于快乘法的思想。将 $k$ 分解成用2的次方之和表示，然后结合一维数组的优化。得以下伪代码

def MulBag(w,v,num,W):
    count=len(w)
    dp=[0 for in range(W+1)]

    for i in range(count):
        k=1
        while num[i]:
            if num[i]<k:
                k=num[i]#不能用2的整次幂表示
            num[i]=num[i]-k#剩下几个
            j=W
            while not j<w[i]:
                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])
                j=-1
            k=k<<1#算术左移，即乘二