背包问题(backpack problem)是最经典也是最简单的一类动态规划(dynamic programming)问题，本篇文章重点讲解背包问题中的0-1背包，完全背包，以及多重背包三大问题，顺带也会说明一下动态规划的基本策略，适合完全不理解相关算法的初学者。

0-1背包(0-1 Knapsack Problem)

1.1 问题描述

一共有NN件物品，每件物品的价格为WiW_i，价值为ViV_i，在总重量不超过背包承载上限WmaxW_{max}的情况下，如何分配使得装入背包的价值最高？

1.2 问题分析

最先想到的就是暴力穷举法，把每种可能的情况都装进去然后找到最大的情况，但是这样做显然是极其低效的，总的时间复杂度是O(2n)O(2^n).

因此，这里引用了动态规划的思路。在这里我们以此为例，每一组的价格和价值如图所示，假设这里背包的最大重量为1010。

N=5 1 2 3 4 5
Weight 1 3 4 5 2
Value 5 10 18 20 7

那么接下来我们要做的事情是，创建一个二维数组dp[i][j]，这样的数组表示将前ii件商品装入重量为j的背包中可以获得的最大价值，其中$$0\leq i\leq N\qquad 0\leq j\leq W_{max}$$

现在我们来看一下，按照这样的规则得到的二维数组是什么样子：

1 2 3 4 5
1 5 5 5 5 5
2 5 5 5 5 7
3 5 10 10 10 12
4 5 15 18 18 18
5 5 15 23 23 23
6 5 15 23 25 25
7 5 15 28 28 30
8 5 15 33 33 33
9 5 15 33 38 38
10 5 15 33 43 43

最后的答案就是数组右下角的结果，那么我们又该如何通过程序得到这样的数组呢？

当我们只有第一件物品的时候（数组的第一列），无论背包容量有多大都只能装下一个物品，所得到的价值也只有第一个物品的价值，此例中即为5.

当我们拥有第二件物品的时候，就要做一个选择，要么装入该物品（前提是能装得下），要么不装入该物品。

那么有人可能就会问了，既然是可以装得下，那么为什么不装入这个物品呢？如果一个物品很沉很沉价值又非常之低，那么我们转入了这个物品的总价值反而要少于装了其他同等重量物品的价值，这个时候装入该物品就显得很多余了。

回到重点，对于这个二维数组来说，不装入第ii件物品的意思是dp[i-1][j]，装入第ii件物品的意思是dp[i-1][j-w[i]] + v[i].

请认真仔细的对照上面的数组，好好理解一下上面的表达式。那么我们得到的状态转移方程即为：$$
dp[i][j]=max(dp[i-1][j],\ dp[i-1][j-w[i]] + v[i]) $$

1.3 python代码

import numpy as np
n = 5
w_max = 10
w = [1, 3, 4, 5, 2]
v = [5, 10, 18 ,20, 7]
dp = np.zeros((n ,w_max + 1),dtype = np.int)
for i in range(0, n):
    for j in range(0,w_max + 1):
        if j - w[i] >= 0:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n - 1][w_max])#43

1.4 算法优化

我们可以看到，这样的0-1背包我们用时间复杂度为O(W⋅N)O(W·N)就可以解决，那么当WmaxW_{max}很大的时候，虽然时间复杂度是足够的，但是空间复杂度依旧为O(W⋅N)O(W·N)，这就导致了二维数组可能会超出内存限制。

实际上，我们不难发现这样一个二维数组是从上至下一层一层进行的（上面的表格是从左至右），在每次进行下一层计算的时候，只有上一层的数据是有用的，其余的数据就没有任何作用了。即，dp[i][j]的值只与dp[i-1][0]… … dp[i-1][j]是有关系的。

因此，我们可以利用这个特性，采用滚动数组的方法对空间复杂度进行优化，使其从二维变为长度为 WmaxW_{max}的一维数组。这种方法在动态规划中是一种常见的策略。

至于为什么是一维数组，而不是两行数组(dp[i][j]与dp[i-1][j])，我们只需要在循环j的时候做逆向计算，从最后一个物品往前推，这样就可以避免上一组数据被覆盖掉。（仔细想一想为什么）

优化后的部分代码如下：

dp = np.zeros(w_max + 1,dtype = np.int)
for i in range(0, n):
    for j in range(w_max, -1, -1):
        if j - w[i] >= 0:
            dp[j] = max(dp[j],dp[j-w[i]] + v[i])

完全背包 (Unbounded Knapsack Problem)

2.1 问题描述

完全背包与0-1背包唯一的区别在于完全背包中每种物品可以有无限多个。

2.2 问题分析

对于完全背包问题，我们很自然的就能想到设置一个$$性价比=\frac{V_i}{W_i}$$，这样一来只需要不停的装性价比最高的商品就能获得最优解。

然而，事实上这样的作法很多时候并不能得到最高的答案，当背包即将装满但还有一定空余时（没办法再装下一个的时候），装性价比最高的商品不见得比装性价比不那么高但是能将背包装满的商品。

事实上，上面的想法是完全可以进行下去的，只是稍稍麻烦一点。我们依旧围绕0-1背包的角度思考，只需要稍加修改即可。依旧是上一组数据，只不过每个物品可以无限拿取。

N=5 1 2 3 4 5
Weight 1 3 4 5 2
Value 5 10 18 20 7

对于完全背包问题，我们依旧是做一个选择，装与不装第ii件物品：

  • 不把物品ii装入背包：dp[i][j]=dp[i-1][j]
  • 把物品ii装入背包：dp[i][j]=dp[i][j-w[i]] + v[i]

(相比于0-1背包，唯一的区别就是dp[i][j]=dp[i-1][j-w[i]] + v[i]

这里肯定有很多小伙伴一脸懵逼，不妨停下来多思考思考。我在写这个文章的时候在这里也停顿了很久，不知道如何言简意赅的来阐述这样的思路。

0-1背包当取走第ii个物品时，需要找到第i−1i-1个物品的最优解中，当取走第ii个物品时，它也可以再次取走自己，所以只需要找到第ii个物品的最优解即可。

因此，完全背包的状态转移方程为：$$
dp[i][j]=max(dp[i-1][j],\ dp[i][j-w[i]] + v[i])

2.3 算法优化

对于完全背包依旧可以优化空间复杂度，如同0-1背包一样将其压缩到一维数组。唯一的不同点在于完全背包的滚动数组在循环j的时候需要正向计算。从第一个物品往后推，这样就可以避免上一组数据被覆盖掉。（仔细想一想为什么）

优化后的部分代码如下：

dp = np.zeros((w_max + 1,dtype = np.int)
for i in range(0, n)
    for j in range(0,w_max + 1):
        if j - w[i] >= 0:
            dp[j] = max(dp[j],dp[j-w[i]] + v[i])

一件很有趣的事情是，我们回过头来看1.4节的0-1背包优化算法，有没有发现他们长得十分相似呢？

此外，对于物品是无限的情况来说，如果有一个物品重量超过另一个物品然而价值又低于另一个物品，那么这样的物品就可以扔掉了。

我们只需要花费O(N2)O(N^2)的时间复杂度进行一次搜索，或许可以排除掉大量没有价值的商品，这样可以极大的节约动态规划的时间开销和空间开销。

2.4 另一种思路

我们回过头来看2.1节提到的思路，不妨在此基础上想一下，我们完全可以将完全背包转换成0-1背包。

虽然每件商品的数量是无限的，但是总量WmaxW_{max}是有限的。因此我们可以计算出每件商品最多可以装入$$\frac{W_{max}}{W_i}$$个，这样一来，我们就拥有了有限多个商品。

当然，这种思路根本谈不上优化，因为其完全没有降低时间复杂度和空间复杂度，只是提供了另一种思路罢了。

dp = np.zeros((n ,w_max + 1),dtype = np.int)
for i in range(0, n):
    for j in range(0, w_max + 1):
        for k in range(0, w_max//w[i] + 1):
            if j - k * w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i])

更高效的做法是使用二进制，即将每种物品的取的个数都用$$V_i=\sum2^i\quad 0\leq i\leq\log_2V_i$$来表示（这是一个常识，任何数字都可以分解成以22为指数的数组），如1313，我们可以表示为13=20+22+2313= 2^0 + 2^2 +2^3.

我们的目的就是要找出第i件物品要取几个好，那么与其用传统的方法每次取一个，然后询问取好呢还是不取好呢，不如用二进制的方法来代替。

举例说明，第一件物品最多可以取1313个，假设取77个是最优解，那么我们第一次询问取202^0个该物品好不好，然后询问21,22,23……2^1,2^2,2^3… …，最终得到了 20+22+21=72^0 +2^2+2^1=7这样的一个结果，我们只需要询问44次而非1313次，这是一个从nn降到log⁡n\log n级别的优化。

现在，小伙伴们可能已经彻底蒙圈了，或许能稍稍理解这样的思想，但是却怎么也写不出来，没关系，只要稍微理解以上的思路就好，我们先来看下一节。

多重背包(bounded knapsack problem)

3.1 问题描述

多重背包与前面的完全背包的不同点在于每种物品是有限多个。

3.2 问题分析

我们在2.4节中提到，完全背包每种物品其实也是有上限的，即加和不应当超过背包的最大承载重量。那么，既然完全背包可以转化成0-1背包问题进行求解，多重背包自然也可以。

我们依旧是分为两个部分，装与不装。

  • 不把物品ii装入背包：dp[i][j]=dp[i-1][j]
  • 把物品ii装入背包：因为每种物品有数量限制，因此我们需要在限制数量中找到最大的价值，此时dp[i][j]=dp[i-1][j-k*w[i]] + k*v[i-1]

因此，状态转移方程为：$$dp[i][j]=max(dp[i-1][j],\ dp[i][j-kw[i]] + kv[i])$$

3.3 python代码

import numpy as np
n = 5
w_max = 10
w = [1, 3, 4, 5, 2]    #weight
v = [5, 10, 18 ,20, 7] #value
maxx = [3, 5, 1, 8, 2] #maximum number
dp = np.zeros((n ,w_max + 1),dtype = np.int)
for i in range(0, n):
    for j in range(0, w_max + 1):
        for k in range(0, min(w_max//w[i], maxx[i]) + 1):
            if j - k * w[i] >= 0:
                dp[i][j] = max(dp[i - 1][j],
                dp[i - 1][j - k * w[i]] + k * v[i])
print(dp)
print(dp[n - 1][w_max]) #42

3.4 算法优化

无论是完全背包还是多重背包，都存在着一种优化方式，就是2进制优化。