01背包问题里的动态规划思想

写本文目的：网上讲解01背包问题的文章有很多，但看着这些文章感觉少了点什么，后来想想，好像都在讲解问题本身，然后给出答案，然后我们看这些文章的时候，好像都懂了，但是我们好像还是不知道什么是动态规划。因此本文就是要讲一讲01背包里面包含的动态规划思想。

什么是01背包问题

背包问题描述：

给定 n 件物品，物品的重量为 weights[i]，物品的价值为 values[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 W，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

01背包问题算是动态规划里面的基础问题了，网上已经有很多讲解01背包问题的文章了，而且讲得也很好。比如：

动态规划：关于01背包问题，你该了解这些！ 动态规划：关于01背包问题，你该了解这些！（滚动数组） 图解 | 你管这破玩意叫动态规划

还有就是《算法图解》里面的 9.1 背包问题，虽然标题是背包问题，但讲解的依然是01背包，算法图解里面的讲解算是很形象了。

如果完全不了解01背包问题的可以看上面几篇文章，讲得都挺好的，这里没有必要再讲一遍了。

01背包为什么叫01背包

想象一下，我们现在有一个背包，然后对于摆在我们面前的 n 件物品，我们都有两个选择，选或者不选，没有其他的选择了。

我们就可以使用 01 来表示这两种状态，0 表示不选择，1 表示选择。假设我们有 3 件物品，那么 [0, 1, 0] 就表示我们只选择了第 2 件物品。

也就是说，最终下来所有可能的不同组合情况共有 2^n 种（n 位，每位有两种可能，0 或 1）。

如果通过遍历所有可能的组合来求解 01背包 问题，那么时间复杂度将会是指数级别的。

什么是动态规划（维基百科）

这里照搬一下维基百科关于动态规划的一些描述。

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

动态规划的适用情况：

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

递归算法

在讲解01背包跟动态规划的关系之前，很有必要先看看递归算法是如何执行的，了解了递归算法的执行过程之后，后面我们就能知道动态规划的优势了。

说到递归，我们很容易想到斐波那契数列，因为斐波那契数列很容易地通过递归算法实现，如下，就几行代码：

public int f(int n) {
    if (n == 0 || n == 1)
        return n;

    return f(n - 1) + f(n - 2);
}

但是虽然它的代码很简单，但是执行的过程并没有那么简单。

我们可以将递归的执行过程想象成一个树状的结构，递归的执行过程如下图，因为 f(0) 和 f(1) 是已知的，所以叶子结点到 f(0) 或者 f(1) 的时候就结束了。

fib.png

简单来讲，就是在求解的过程中，由大到小，依次求解，求解完左边之后，再求解右边，又进行一次由大到小的求解。在到达边界的时候，依次返回。

然后我们可以很容易发现，其实在递归的过程中，f(2) 和 f(3) 都被重复计算了，而且，我们的递归层数越多，被重复计算的子问题就越多。

递归有个问题是，子问题会被多次重复求解，这样会导致有很多时间浪费在做一些重复计算上。

递归与动态规划

对于斐波那契数列，有没有方法可以做到 f(2) 和 f(3) 只求解一次呢？

有的，先求解子问题即可，从斐波那契数列的定义，我们可以知道 f(n) + f(n + 1) = f(n + 2)，那么，如果我们要求 f(5)，我们可以从 f(0) 求解到 f(5)：

f(2) = f(0) + f(1)，f(0) 和 f(1) 不需要求解，可以直接得出
f(3) = f(1) + f(2)，上一步我们已经求解了 f(2) 了，我们加上 f(1) 就得到 f(3) 了，这一步利用了上一步的计算结果
f(4) = f(2) + f(3)，上一步我们已经求解了 f(3) 了，而且我们的 f(2) 在第一步已经求解了，我们这里直接利用了前两次计算的结果
f(5) = f(3) + f(4)，同理，这里利用了前两次计算的结果

代码实现如下：

public int f(int n) {
    if (n <= 1) return n;
      
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

所以这里的关键是什么呢？

1. 先求解子问题，记录下子问题的答案。
2. 逐步求解更大的问题，这个更大的问题可以直接利用前面的计算结果。

这跟动态规划有什么关系？就从动态规划的适用情况说吧：

1. 最优子结构：我们从小到大求解 f(n) 的过程中，每一个 f(i) 可以看作最优子结构，当然这里实际上并没有优劣一说，我们每一个 f(i) 都是唯一的（对于 01背包 这种就有最优子结构的说法了）。
2. 无后效性：我们在求解 f(i) 的时候，并不关心 f(i - 1) 和 f(i - 2) 是怎么得到的，我们只需要知道前面求解的结果，并不关系其过程。
3. 子问题重叠：我们在递归求解 f(5) 的时候，发现 f(2) 和 f(3) 都被重复计算了，f(2) 和 f(3) 就是重叠子问题。

所以我们可以看到，动态规划的关键是，先求解子问题，得到子问题的解，然后逐步求解更大的问题，对于更大的问题，直接利用子问题的结果（子问题的结果都是最优结果），不需要再次计算。逐步求解，直到我们得到最终问题的答案。

01背包的决策过程

假设我们有一个容量为 4 的背包，有三件物品，物品0重量为 1、价值为 15，物品1重量为 3、价值为 20，物品2重量为 4、价值为 30。

然后使用 dp[i] 表示不同的背包容量下所能获得的最大价值。我们的背包容量为 4，所以只需要计算到 dp[4] 即可。

1. 对于第一件物品，dp[1]、dp[2]、dp[3]、dp[4] 都是 15，因为只有容量大于等于 1 的时候我们才能装得下这件物品，然后可以获得其价值。

2. 对于第二件物品，dp[1]、dp[2] 依然是 15，因为只有容量为 3 的背包才能放得下第二件物品。

1. 对于 dp[3]，容量为 3 的时候，有两种情况

• 不放入这件物品，那么所能获得的价值依然是 15。
• 放入这件物品。但是放入之后，就要占据背包全部容量了，之前的所有物品都放不下了，但是我们可以获得更大的价值 20。因此 dp[3] = 20

因此在背包容量为 3，有前两件物品选择的情况下，我们所能获得的最大价值是 20。

2. 对于 dp[4]，容量为 4 的时候，我们可以选择不放入这件物品，那么所能获得的价值依然是 15。

• 不放入这件物品，那么所能获得的价值依然是 15。
• 放入这件物品。放入之后，我们的背包还剩容量 1，在之前的物品中，容量 1 所能获得的最大价值是 15。

因此在背包容量为 4，有前两件物品选择的情况下，我们所能获得的最大价值是 20 + 15 = 35，20 是当前物品的价值，15 是剩余背包容量所能获得的最大价值。

3. 对于第三件物品的分析过程类似在对第二件物品做决策的过程，不再赘述。

我们在决策的过程中，需要根据之前物品选择之后，不同背包容量的所能获得的最大价值来进行决定是否选择当前物品。这样就能保证我们每次选择都是最优的结果。

01背包问题里面的动态规划

我们可以从动态规划适用情况来看01背包问题：

1. 最优子结构

在 0~i 件物品选择之后，不同背包容量下所能获得的最大价值就是一个最优子结构。我们并不需要知道前面的 0~i 件物品具体是怎样选择的，我们只需要知道选择的最优结果即可。

之所以需要计算不同容量，是因为如果我们当前剩余背包容量放不下当前物品的时候，就需要求解放入当前物品后，剩余的背包容量的最大价值，然后加上当前物品的价值，就是放入当前物品所能获得的最大价值。

2. 无后效性

对于 0~i 件物品具体怎么选择，我们在决定要不要放入当前物品的时候，并不关心，我们只需要知道有某一种方案可以使得获得当前最大价值就行了，同时我们后面不管怎么选择都影响不到之前选择得到的最优结果。

3. 重叠子问题

我们在选择一件物品的时候，假设要放入当前物品，那就需要知道剩余背包容量的在之前的物品选择中所能获得的最大价值。而之前的物品选择中，不同容量下所能获得的最大价值就是子问题。

01背包里面的重叠子问题

下面的讲解跟回溯相关，想详细了解回溯的朋友可以看看这一篇文章：回溯算法理论基础！

如果直接从动态规划的角度来思考01背包问题里面的重叠子问题可能会比较困难。

但是还有一种算法可以求解01背包问题的，那就是回溯（本质是递归），但是上面也说了，时间复杂度太高了，指数级别的。但是从回溯的角度来看，就很好理解01背包里面的重叠子问题。

现在，假设我们有一个容量为 W 的背包，有 3 件物品 A、B、C，需要从这 3 件物品里面选取不同的物品加入背包，使得加入背包的价值最大。我们使用一个长度为 3 的数组来记录每一种不同的组合，数组的每一个元素使用 0 代替没有选中的状态，使用 1 来代替选中的状态。

用回溯算法的处理过程如下，下图的每一个节点里面，我们都计算从 0~W 的容量下，当前的组合能获得的最大价值。

01.png

从上图看来，我们不管是否选择了 A，都要再针对 B 和 C 做出同样的组合判断，但是我们要知道，对于不同的背包容量，B 和 C 组合能得到的最大价值都是固定的，跟 A 并没有关系。

所以如果使用回溯算法，对于选不选 A，后面对于 B 和 C 的组合我们都做了重复的计算了。

上图上色的部分就是重复计算的部分，当然还有其他的重复计算，这些重复计算的地方就是01背包里面的重叠子问题了。

所以01背包里面的重叠子问题就是，i 个物品在不同背包容量下的最大价值。

动态规划是怎么处理重叠子问题的

我们再回忆一下上面提到的斐波那契数列的优化写法，我们是通过计算更小的斐波那契数列，逐步计算到我们需要的那个数 n，在这个计算过程中我们可以直接使用前面的计算结果。

因此，对于01背包问题，我们其实也可以先求解重叠的子问题，然后将这些子问题的解保存下来，在解决更大的问题的时候直接使用前面计算的结果。

具体来说，可以怎么做呢？

就是每次做判断的时候，我们都去计算将这个物品加入背包或者不加入背包的情况下，0~W 不同的背包容量下所能获得的最大价值。

然后我们在对下一个物品进行选择的时候，可以用背包容量减去当前物品重量，得到一个一个剩余的背包容量，我们看剩余背包容量在前面物品的选择中最大价值是多少，加上当前物品的价值，就是加入当前物品之后所能获得的最大价值。

我们需要注意的是，加入这件物品之后，得到的最大价值未必比不加入这件物品的价值更大，这个时候就需要对比一下两种情况，哪一种情况能获得的价值最大，就是当前选择过的物品不同组合下所能获得的最大价值了。

在01背包里面，我们可以直接利用 0~i-1 件物品的选择结果，来判断是否将第 i 件物品加入到背包。

总结

01背包里面的动态规划思想（假设我们已经选择了 0~i-1 件物品，W 是背包容量）：

1. 最优子结构：0~i-1 件物品在不同的背包容量下能获得的最大价值是一个最优子结构。
2. 无后效性：我们在决定放不放第 i 件物品的时候，前面的 0~i-1 件物品是如何组合得到那个最大价值完全没影响。
3. 重叠子问题：在 0~i-1 件物品的不同组合中，0~W 所能获得的最大价值。