动态规划算法03-背包问题

背包问题

简介

背包问题一个很著名的动态规划问题，也称为0-1背包问题，很多题都是以此为模板进行魔改的。

问题描述

有N个重量为w1，w2，w3，，，wn且价值为v1，v2，v3，，，vn的物品和一个承重量为W的背包，求让背包里装入的物品具有最大的价值总和的物品子集。

题解思路

看到这种最优解求解的题目，很容易想到动态规划思路。为了设计动态规划算法，需要推导出一个递推关系以构造递推函数，用较小子问题的解的形式来表示背包问题的当前问题的解。

首先考虑一个有前$i$($1\le i\le N$)个物品定义的实例，物品的重量分别为$w_1，w_2，，，w_i$，价值为$v_1，v_2，，，v_i$，背包目前的承重量为$j$($1\le j\le W$)。

设$F(i,j)$为组成该实例最优解的物品的总价值，也就是说能够放进承重量为$j$的背包中的前$i$个物品中最有价值的子集的总价值。（注意，在这里还没有出现题目想要的解的形式，）

在这里，可以把前$i$个物品中能够放进承重量为$j$的背包中的子集分为两种类别：包括第$i$个物品的子集和不包括第$i$个物品的子集。于是可以得到以下结论：

• 根据定义，在不包括第$i$个物品的子集中，最优子集的价值是$F(i-1,j)$。
• 在包括第i个物品的子集中（$j-w_i\ge 0$)，最优子集为该物品和前$i-1$个物品中能够放进承重量为$j-w_i$的背包的最优子集组成。这种最优子集的总价值等于$v_i+F(i-1,j-w_i)$。

因此，在前i个物品中，最优解的总价值等于以上两种情况的最大值，这就是最优子结构了。当然，如果第$i$个物品不能放进背包中，那么从前i个物品中选出的最优子集的总价值即等于从前$i-1$个物品中选出的最优子集的总价值。于是得到下面的递推式，也是状态转移函数。
F ( i , j ) = m a x { F ( i − 1 , j ) , v i + F ( i − 1 , j − w i ) } , j − w i > = 0 F(i,j)=max\{F(i-1,j),v_i+F(i-1,j-w_i)\},j-w_i>=0 F(i,j)=max{F(i−1,j),vi​+F(i−1,j−wi​)},j−wi​>=0
$$F(i,j)=F(i-1,j),j-w_i<0$$

同时可以得到边界。
$$F(0,j)=0,j>=0$$
$$F(i,0)=0,i>=0$$

至此，动态规划的三要素寻找完成，我们的目标不仅仅是求F的值，还有$F$取值时的物品组合。

实例分析

假设物品数量为5，背包承重量为10，各个物品信息如下表。

动态规划的原理与分治法常常类似，但是分治法将子问题和子子问题反复求解多次，动态规划擅长的则是记录之前问题的解，即填表。

可以看到，当输入为5,10的时候，最优解为15，这是正确的。

回溯求序列

一般，动态规划用来求最优解，利用递归构造可以很方便的找到最后的答案。注意：一旦，动态规划的题目出现输入序列，那么就不是找到答案那么简单，除了正向找到最优解，构造解表，还要反向寻找最优解的构成。 以上面这个例子为例，最后rst[5,10]是15，这是答案，此时定义一个物品长度的序列x并使每个元素为False。

对表格的每一行做遍历，指定w为最高权重10。逆序遍历表格每一行，最后一行根据函数判断rst[m][w]（m为遍历下标）是否等于rst[m-1][w]若相等，则代表当前行对应的物品没有选中（原理是依据状态转移函数），否则代表选中，w-=当前行对应物品的权重，x[m]置为True，按此顺序，遍历结束。输出为True的对应下标，即为最优解序列。在这个过程中x的取值要么为True要么为False，这就是为什么叫做0-1背包问题。

def bag(i, j, w, v, out):
    if i == 0 and j >= 0:
        out[i][j] = 0
        return 0
    if i >= 0 and j == 0:
        out[i][j] = 0
        return 0
    if j - w[i-1] >= 0:
        out[i][j] = max(bag(i-1, j, w, v, out), v[i-1] + bag(i-1, j-w[i-1], w, v, out))
        return out[i][j]
    if j - w[i-1] < 0:
        out[i][j] = bag(i-1, j, w, v, out)
        return out[i][j]


def search(rst, i, j):
    x = [False for m in range(i+1)]
    for m in range(i, -1, -1):
        if rst[m][j] == rst[m-1][j]:
            # 此时代表没有选中当前
            pass
        else:
            x[m] = True
            j -= w[m-1]
    for i in range(len(x)):
        if x[i]:
            print("选择了第{}个物品".format(i))


if __name__ == '__main__':
    # 物品数目
    i = 5
    # 背包容量
    j = 10
    # 物品信息
    w = [2, 2, 6, 5, 4]
    v = [6, 3, 5, 4, 6]
    # 结果存放表
    rst = [[0 for m in range(j+1)] for n in range(i+1)]
    # 计算结果，构造解集合
    bag(5, 10, w, v, out=rst)
    # 输出解集合表格
    for item in rst:
        print(item)
    # 回溯查找输入序列
    search(rst, i, j)

当然本题也可以使用非递归的方式实现，也就是我们更常用的DP Table的形式，代码如下。

def bag(N, W, w, v, dp):
    for i in range(1, N+1):
        for j in range(1, W+1):
            if w[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
            else:
                # 第i个物品放不下
                dp[i][j] = dp[i-1][j]
    return dp


def search(rst, i, j):
    x = [False for m in range(i+1)]
    for m in range(i, 0, -1):
        if rst[m][j] == rst[m-1][j]:
            # 此时代表没有选中当前
            pass
        else:
            x[m] = True
            j -= w[m-1]
    for i in range(len(x)):
        if x[i]:
            print("选择了第{}个物品".format(i))


if __name__ == '__main__':
    # 物品数目
    i = 5
    # 背包容量
    j = 10
    # 物品信息
    w = [2, 2, 6, 5, 4]
    v = [6, 3, 5, 4, 6]
    # 结果存放表
    dp = [[0 for m in range(j+1)] for n in range(i+1)]
    # 计算结果，构造解集合
    bag(5, 10, w, v, dp)
    # 输出解集合表格
    for item in dp:
        print(item)
    # 回溯查找输入序列
    search(dp, i, j)

优化思路

其实可以从代码和状态转移公式都能看出来当前层的状态只与上一层状态有关（可以参考上一节的DP Table可视化），也就是说，我们其实只需要知道最后一层的情况而不需要存储之前的结果，在dp table中我们最后输出的其实是最右下角的值。这就是01背包的状态压缩。

这个时候，我们可以得到一个新的递推式，这里的$f[j-w[i]]+v[i]$代替了原来递推式中的$dp[i-1][j-w[i]]+v[i]$这部分。

f [ j ] = m a x { f [ j ] , f [ j − w [ i ] ] + v [ i ] } f[j] = max\{ f[j], f[j-w[i]] + v[i] \} f[j]=max{f[j],f[j−w[i]]+v[i]}

但是注意，我们这里只有一维数组，这就要保证当我想要取得$f[j-w[i]]$的时候，他没有被更新过，换言之，它必须是上一层的数据，这就要求我们内部的那个循环必须逆序进行。 这就是空间优化版本最难以理解的地方。

具体代码如下，此时就不能采用上面的思路输出选择的物品了。此时空间复杂度由$O(NW)$优化为$O(W)$。

def bag(N, W, w, v, dp):
    for i in range(N):
        for j in range(W, w[i]-1, -1):
            dp[j] = max(dp[j], dp[j-w[i]] + v[i])
    return dp


if __name__ == '__main__':
    # 物品数目
    i = 5
    # 背包容量
    j = 10
    # 物品信息
    w = [2, 2, 6, 5, 4]
    v = [6, 3, 5, 4, 6]
    # 结果存放表
    dp = [0 for m in range(j+1)]
    # 计算结果，构造解集合
    dp = bag(i, j, w, v, dp)
    print(dp[-1])

补充说明

具体代码可以查看，欢迎Star或者Fork。参考书《你也能看得懂的Python算法书》，书中略微有一点不合理之处，做了修改。到这里，其实你已经体会到了动态规划的简约之美。