使用动态规划解决 0-1 背包问题

一、问题描述

有 n 个物品，它们有各自的重量和价值，现有给定容量的背包，

如何让背包里装入的物品具有最大的价值总和？（注意：每种物品只能放入到背包中一次）

上图给出了 a、b、c、d 4 种物品以及每种物品对应的体积和价值。

我们将要求体积为 8 的背包最多可以存放多大的价值。

二、预备知识

1、将使用 w(i) 表示物品 i 的重量，如

w(a) 表示物品 a 的重量
w(b) 表示物品 b 的重量
w(c) 表示物品 c 的重量
w(d) 表示物品 d 的重量

2、将使用 v(i) 表示物品 i 的价值，如

v(a) 表示物品 a 的价值
v(b) 表示物品 b 的价值
v(c) 表示物品 c 的价值
v(d) 表示物品 d 的价值

3、dp[i][j] 的含义

上图为初始化时，动态规划所用到的 dp 数组

上图为动态规划执行完毕之后得到的二维数组 dp，怎么构建该数组会在下面介绍，

这里先不用先关注计算的过程

我们使用二维数组 dp 表示动态规划需要构造的数组，其中 dp[i][j] 表示，

当背包的容量为 j 时，且只有前 i 件物品时，

背包里装入物品的最大的价值总和为 dp[i][j]

4、对于 dp[i][j] 的进一步解释

对于本题来说，我们假设

a 为第一件商品        b 为第二件商品        c 为第三件商品        d 为第四件商品

图中标黄的值可以用 dp[3][7] = 9 表示

她所代表的含义是当背包的容量为 7 时，且只有前 3 件物品时，

背包里装入物品的最大价值总和为 9，

dp[3][7] = 9 需要注意到的重点

1、只有前 3 件商品，即 a b c 这三件商品，即使物品的总数量为 4，但是就 dp[3][7]

来说只能取前三件，要是需要取全部的 4 件商品，需要求 dp[4][7]

2、背包的容量是 7，即使背包总容量是 8，但是就 dp[3][7] 来说，目前背包的容量为 7

3、p[3][7] 表示 当只有前 3 件商品时，并且背包的容量为 7 时，

背包里面能装的最大价值为 9，这里的 9 表示的是最大价值，是一个最优的结果，

无论前三种商品怎么组合，在现有的容量下，能够得到的最大价值是 9

5、动态规划矩阵（即 dp 矩阵）计算的方向

我们在计算 dp 矩阵的时候，计算的方向是从上到下，从左到右依次计算的

这又有什么意义呢？

假设我们需要计算图中标黄的值（该值可以用 dp[2][4] 表示），

按照从上到下，从左到右的计算方向，计算的顺序是

dp[0][0] -> dp[1][0] -> dp[2][0] -> dp[3][0] -> dp[4][0] -> 
dp[0][1] -> dp[1][1] -> dp[2][1] -> dp[3][1] -> dp[4][1] ->
dp[0][2] -> dp[1][2] -> dp[2][2] -> dp[3][2] -> dp[4][2] -> 
dp[0][3] -> dp[1][3] -> dp[2][3] -> dp[3][3] -> dp[4][3] ->
dp[0][4] -> dp[1][4] -> dp[2][4]

也就是说在计算 标黄值位置的时候，标绿值的位置已经全部都计算完毕了

6、数据动态变化的过程

还是拿着上图标黄的值来搞事情

计算 dp[2][4] = 4 的原因

根据计算方向，求完了 dp[1][4] = 3 才能求 dp[2][4] = 4,

dp[1][4] = 3 说明了当背包的容量为 4 时，

如果我有前 1 件商品（即 只有 a 商品），背包中能存放的最大价值为 3，

但是在计算 dp[2][4] 时，由计算 a 这一件商品变成了计算 a b 两件商品

这是我们需要在 a b 中选择物品添加到背包中，

背包还是那个背包（容量没有发生变化），这时背包能存放的总价值变成了 4。

这就是由 dp[1][4] -> dp[2][4] 的过程

三、对于公式的理解

几乎在所有的博客之中都会出现下列公式，那么就让我来给你解释一下它的意义；

dp[i][j] = max { dp[i - 1][j], dp[i - 1][j - w[i]] + v[i] }

在 二、符号化中 我们已经介绍了 w[i] 和 v[i] 的含义，

其中 w[i] 表示物品 i 的重量，v[i] 表示物品 i 的价值

物品的体积和价值图

上图中

dp[2][4] = max { dp[2 - 1][4],dp[2 - 1][4 - w(b)] + v(b) }

= max{dp[1][4],dp[1][1] + 4} = max{3，4} = 4

影响 dp[2][4] 值大小的影响因素有两个，一个是 dp[1][4]，另一个是 dp[1][1] + 4，

下面分别介绍两部分的值是如何得到的。

1、当物品 b 出现时，背包装不下 （此处是用来求 dp[1][4] 大小）

1、dp[1][4] 是如何来的

当物品 b 出现时，背包的容量已经放不下物品 b 了，

这时背包能够存放的最大价值就是只有前 1 件货物（即只有货物 a）时所能存放最大价值，

因为没法把 b 放入到背包，所以背包存放的最大价值不会发生改变

背包的总价值就是前 1 件物品（只有货物 a）的总价值，即 dp[1][4]

2、知识延申

dp[i][j] 在这种情况下可以表示为，

当物品 i 出现时，背包的容量已经放不下物品 i 了，

这时背包能够存放的最大价值就是只有前 i - 1 件货物时所能存放最大价值，

因为没法把 i 放入到背包，所以背包存放的最大价值不会发生改变，

背包的容量为 j 时，背包的总价值就是只有前 i - 1 时的最大价值

我们知道 dp[i-1][j] 就代表了背包的容量为 j 时，背包的总价值就是只有前 i - 1 时的最大价值

所以公式中前一部分搞定了，即图中划红线的部分

2、当物品 b 出现时，背包能装下 （此处是用来求 dp[1][1] + 4 的大小）

1、dp[1][1] + 4 是如何来的

当物品 b 出现时，物品 b 能够放入到背包中，那么背包就要留出一定的空间，

那么需要留出多大的空间呢？

留出的空间的大小是刚好能够容纳 b，这样可以充分利用背包中的空间。

就本题而言，w(b) = 3,也就是说我们再没有把 b 放入背包之前需要留出 3 的空间大小

重点强调

1、因为要留出空间来存放 b，所以要在 b 未放入之前为 b 留出空间
2、留出空间的大小为 3，因为这样刚好能够放下 b
3、若要能满足以上的条件，我们从满足添加的数据里面挑选一个价值最大的数据就行了

对于本题来说，我们要保证在背包容量小于等于 1（即 4 - w(b) = 4 - 3 = 1） 的时候，

才能安全的把 b 物品放入到背板

我们用上图来分析一下那些区域可以放 c 物品，图中蓝色区域是已经有了 b 货物，所以不能选，

橙色区域表示若我们把 b 物品放入到背包中，背包的容量是放不下的，

绿色区域是安全区域，我们可以安全的把 b 货物放入到背包,

对于 dp[0][0],dp[1][0] 和 dp[0][1],dp[1][1],我们要选dp[0][1],dp[1][1],因为 背包的容量大啊，能装的东西就多啊，能得到的价值就多啊，你 dp[0][0],dp[1][0],能装的 我 dp[0][1],dp[1][1] 都能装啊，而且我还能比你更能装。

但是对于 dp[0][1],dp[1][1] 这两个值，我们要选择 dp[1][1],因为 dp[0][0] 是在前 0 种物品中选取物品，而我们要把第 2 件商品放入背包之前，是要在前 1 件物品中选择物品的

我们选择了 dp[1][1],这是背包有多余的空间放入 b 物品，这时将 b 物品放入背包，

这时背包的最大价值为 dp[1][1] + v(b) = dp[1][1] + 4 = 4

2、知识延申

dp[i][j] 在这种情况下可以表示为，

当物品 i 出现时，物品 i 能够放入到背包中，那么背包就要留出一定的空间,

留出的空间大小为 w(i)，保证背包的容量为 j - w（i） 这样刚好放下物品 i

而且还要在前 i - 1 件货物中挑选物品，

而且还要保证得到最大的价值，只能选择 dp[i - 1][j - w(i)]

选择了 dp[i - 1][j - w(i)] 之后，物品 i 就可以放入到背包中了，

这时背包的最大价值就是 dp[i - 1][j - w(i)] + v[i]

这里解释了公式的后半部分

3、补充

1、当背包中容量留不出第 i 件物品需要的空间

图中标绿的位置可以使用 dp[2][2] = 3 表示，按照上述公式，该位置为

dp[2][2] = max{ dp[1][2], dp[1][2 - w(b)] + v(a) }

由于在后半部分 2 - w(b) 2 - 3 < -1 < 0,这说明无论背包怎么留空间都不足以给物品 b 留出足够的空间，

所以这时候 dp[2][2] 只来自于第一部分，即 dp[2][2] = dp[1][2]

在完善以下上述公式可以得到如下公式：

dp[i][j] = max { dp[i - 1][j], dp[i - 1][j - w(i)] + v(i) }  j - w(i) >=0
dp[i][j] = dp[i - 1][j]                                         j - w(i) < 0

四、对于本题来说完整的执行过程

下述的所有过程会在代码中体现出来

1、初始化

将上图中标记为绿色和黄色的部分初始化为 0

这样做的好处

1、便于计算，不如说我们在计算橙色位置 dp[1][1] 的时候，

这时候背包的总容量时小于 a 的体积的，所以无法留出阻攻的空间来存放物品 a，

所以根据公式该处的位置直接是 dp[1][1] = dp[0][1] = 0

这样可以省略一些判断

2、也符合逻辑，绿色部分表示，一件物品都没有，所以背包能存放的最大价值为 0，

因为没有东西可以往背包中放；黄色部分表示，背包的容量为 0，

这时候无论什么物品都没法放入到背包中，所以背包能存放的最大价值为 0

2、第一部分计算

对于上图来说，灰色部分表示已经计算完毕的部分，绿色部分表示即将要计算的部分

他们分别用 dp[1][1],dp[2][1],dp[3][1],dp[4][1] 表示

物品的体积和价值表

对于 dp[1][1]

判断背包能不能留出足够的空间

利用公式 j - w(a) = 1 - 2 = -1 < 0（背包留不出足够的空间)

所以有

dp[1][1] = dp[1 - 1][1] = dp[0][1] = 0

对于 dp[2][1]

判断背包能不能留出足够的空间

利用公式 j - w(b) = 1 - 3 = -2 < 0（背包留不出阻攻的空间）

dp[2][1] = dp[2 - 1][1] = dp[1][1] = 0

对于 dp[3][1]

判断背包能不能留出足够的空间

利用公式 j - w(c) = 1 - 4 = -3 < 0（背包留不出阻攻的空间）

dp[3][1] = dp[3 - 1][1] = dp[2][1] = 0

对于 dp[4][1]

判断背包能不能留出足够的空间

利用公式 j - w(d) = 1 - 5 = -4 < 0（背包留不出阻攻的空间）

dp[4][1] = dp[4 - 1][1] = dp[3][1] = 0

这一列计算完毕的结果如下图，

其中灰色的部分表示已经计算完毕

3、第二部分计算

对于上图来说，灰色部分表示已经计算完毕的部分，绿色部分表示即将要计算的部分

他们分别用 dp[1][2],dp[2][2],dp[3][2],dp[4][2] 表示

物品的体积和价值表

对于 dp[1][2]

判断背包能不能留出足够的空间

利用公式 j - w(a) = 2 - 2 = 0 >= 0（背包能留出足够的空间)

所以有

dp[1][2] = max{ dp[0][2],dp[0][0] + v(a) } = max{ dp[0][2],dp[0][0] + 3 }
= max{ 0,3 } = 3

对于 dp[2][2]

判断背包能不能留出足够的空间

利用公式 j - w(b) = 2 - 3 = -1 < 0（背包不能留出足够的空间)

所以有

dp[2][2] = dp[1][2] = 3

对于 dp[3][2]

判断背包能不能留出足够的空间

利用公式 j - w(b) = 2 - 4 = -2 < 0（背包不能留出足够的空间)

所以有
dp[3][2] = dp[2][2] = 3

对于 dp[4][2]

判断背包能不能留出足够的空间

利用公式 j - w(b) = 2 - 5 = -3 < 0（背包不能留出足够的空间)

所以有
dp[4][2] = dp[3][2] = 3

这一列计算完毕的结果如下图，

4、第三部分计算

对于上图来说，灰色部分表示已经计算完毕的部分，绿色部分表示即将要计算的部分

他们分别用 dp[1][3],dp[2][3],dp[3][3],dp[4][3] 表示

物品的体积和价值表

对于 dp[1][3]

判断背包能不能留出足够的空间

利用公式 j - w(a) = 3 - 2 = 1 >= 0（背包能留出足够的空间)

所以有
dp[1][3] = max{ dp[0][3],dp[0][1] + v(a) } = max{ dp[0][3],dp[0][1] + 3 }
= max{ 0,3 } = 3

对于 dp[2][3]

判断背包能不能留出足够的空间

利用公式 j - w(a) = 3 - 3 = 0 >= 0（背包能留出足够的空间)

所以有
dp[2][3] = max{ dp[1][3],dp[1][0] + v(a) } = max{ dp[1][3],dp[1][0] + 4 }
= max{ 0,4 } = 4

对于 dp[3][3]

判断背包能不能留出足够的空间

利用公式 j - w(a) = 3 - 4 = -1 < 0（背包能留出足够的空间)

所以有
dp[3][3] = dp[2][3] = 4

对于 dp[4][3]

判断背包能不能留出足够的空间

利用公式 j - w(a) = 3 - 5 = -2 < 0（背包能留出足够的空间)

所以有
dp[4][3] = dp[3][3] = 4

这一列计算完毕的结果如下图，