一次性讲透背包问题——动态规划经典问题的深度解析

背包问题是动态规划问题的一个重要的分支，也是笔试和面试算法的常考内容。背包问题有很多分类，比如0/1背包、完全背包、多重背包、分组背包等，其中最常见的是0/1背包和完全背包问题。

0 / 1背包

0/1背包的题目是这样的：给定两个长度为n的数组weight[]和value[]，代表的含义是第iii号物品的重量是weight[i]，价值是value[i]。你有一个容量是capacity的背包，每个物品只能选一次，请你求出在不超过背包容量的前提下能拿到的物品的最大价值。比如我们给出的这个例子

示例1：

weight: [5, 6, 7]

value: [3, 4, 5]

capacity: 5

在这个例子中，背包容量只有5，只能选择0号物品，所以能拿到物品的最大价值就是0号物品的价值，也就是3。

示例2:

weight：[3, 1, 5, 3, 2]

value: [5, 3, 4, 3, 1]

capacity: 10

这个例子中我们可以拿0，1，2号物品，也可以拿0，1，3，4，这样拿到的物品价值都是12

示例3:

weight: [1, 3, 4]

value: [15, 20, 30]

capacity: 4

这个例子中，背包容量是4，可以拿0号物品和1号物品，也可以只拿2号物品，显然拿0号和1号物品的价值要更大，所以这个例子的答案是15+20=3515 + 20 = 3515+20=35

因为针对每个物品都只有两种选择：拿或者不拿，所以这种背包问题我们称之为01背包

递归解法

这个问题的暴力解法应该不难想，我们有n个物品，每一个元素都有选和不选两种情况，如果我们用一个二叉树的边去表示这个选或不选的状态，就会生成一颗高度为n+1的二叉树，题目的答案肯定能在二叉树中表示出来，因为二叉树中枚举了每个物品的所有状态。

所以，假设我定义出一个递归函数process(int index, int capacity)，递归函数的定义是从0号物品到index号物品中，使用容量为capacity的背包能拿到物品的最大价值是多少，题目要求的答案显然应该是调用process(n-1, capacity)的返回值。

递归的出口是什么呢？当index = 0时，这个递归的含义是0号物品到0号物品中，背包能拿到物品的最大价值，如果背包的容量 >= 0号物品的重量，也就是说能装得下0号物品，那能拿到的就应该是0号物品的价值，否则一个物品都装不下，能拿到的价值就应该是0，所以就有如下代码

  if (index == 0) {
    return capacity >= weight[0] ? value[0] : 0;
  }

再想一下，我们查询的范围是0号到index号物品，针对index号物品我们有两种选择：拿或者不拿，如果不拿，那么说明0 ～ index号中我们能拿到的最大价值和0 ～ index-1号物品中的最大价值是一样的，所以可以递归地调用process(index - 1, capacity)获得；如果拿了index号物品，那么留给0 ~ index-1号物品的背包容量就只剩下了capacity-weight[i]，所以此时能拿到的物品价值就应该是process(index - 1, capacity - weight[i]) + value[i]。当然，拿index号物品是有前提条件的，就是背包的容量必须 ≥\ge≥ i号物品的重量。那这样的话，我们拿到了index号元素拿和不拿时能拿走物品的最大价值，最终函数的返回值就是这两个结果中的最大值。

这种解法的代码如下

public static int maxValue(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    return process(weight, value, n-1, capacity);
}

/**
 * 递归的含义：在0 ~ index号元素中，使用剩余容量为capacity的背包能拿走的最大价值是多少
 * @param index 当前判断到第index个物品(从0开始)
 * @param capacity 背包的剩余容量
 */
public static int process(int[] weight, int[] value, int index, int capacity) {
    if (index == 0) {
        return capacity >= weight[index] ? value[index] : 0;
    }

    int curNotTake = process(weight, value, index - 1, capacity);

    int curTake = 0;
    if (capacity >= weight[index]) {
        curTake = process(weight, value, index - 1, capacity - weight[index]) + value[index];
    }

    return Math.max(curTake, curNotTake);
}

思考一下在这个递归函数的调用过程中有重叠子问题吗？假设下面的这个例子

weight: [1, 1, 1, 1]

value: [10, 20, 30, 40]

capacity: 3

递归函数中的weight和value数组都是不变的参数，我们不去管它。题目要求的肯定是process(3, 3)，process(3, 3)会递归地调用process(2, 3)和process(2, 2)，process(2, 3)会递归调用process(1, 3)和process(1, 2)，process(2, 2)也会递归调用process(1, 2)和process(1, 1)。诶看到了吗，这里重复地调用了process(1, 2)，所以0/1背包问题中存在重叠子问题。

动态规划解法

记忆化搜索

记忆化搜索的解法比较简单，在递归函数的参数中加一个缓存Map，key可以做成一个对象，对象中有index和capacity两个字段，递归之前先判断缓存中有没有，得出结果之后在缓存中也填一份。代码实现如下。

public static int maxValue(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    return process(weight, value, n-1, capacity, new HashMap<>());
}

/**
 * 递归的含义：在0 ~ index号元素中，使用剩余容量为capacity的背包能拿走的最大价值是多少
 * @param index 当前判断到第index个物品(从0开始)
 * @param capacity 背包的剩余容量
 */
public static int process(int[] weight, int[] value, int index, int capacity, Map<BagCache, Integer> cacheMap) {

    if (index == 0) {
        return capacity >= weight[index] ? value[index] : 0;
    }

    BagCache key = new BagCache(index, capacity);
    if (cacheMap.containsKey(key)) {
        return cacheMap.get(key);
    }

    int curNotTake = process(weight, value, index - 1, capacity, cacheMap);

    int curTake = 0;
    if (capacity >= weight[index]) {
        curTake = process(weight, value, index - 1, capacity - weight[index], cacheMap) + value[index];
    }

    int res = Math.max(curTake, curNotTake);

    cacheMap.put(key, res);

    return res;
}

private static class BagCache {
    int index;
    int capacity;

    public BagCache(int index, int capacity) {
        this.index = index;
        this.capacity = capacity;
    }

    @Override
    public boolean equals(Object obj) {

        if (!(obj instanceof BagCache)) {
            return false;
        }

        BagCache bagCache = (BagCache) obj;
        return this.index == bagCache.index && this.capacity == bagCache.capacity;
    }

    @Override
    public int hashCode() {
        return this.index * 10 + this.capacity;
    }
}

自底向上的动态规划

其实，根据上面递归的代码，我们就可以很轻松地改写出动态规划版本的代码。在上面递归函数的参数中weight和value是不变参数我们不去管它，index和capacity是两个不断变化的参数，index的变化范围是0n-1，capacity变量的变化范围是0capacity(题目中给出的参数capacity)，所以我们设置一个二维数组dp[][]，这个数组一共有n行，capacity+1列。这样的话，dp[i][j]代表的含义就是：0～i号物品中，使用容量为j的背包能拿到的最大价值。数组的第一列dp[i][0]代表背包的容量为0，显然拿不到任何物品，所以结果直接为0，数组的第一行dp[0][j]代表背包的容量为j，只能拿0号物品，只有当j≥weight[0]j \ge weight[0]j≥weight[0]时才能拿走0号物品，所以当j >= weight[0]时，dp[0][j] = value[0]，否则dp[0][j] = 0

此外，根据递归函数的调用关系也可以轻松得出i、j均不为0时题目的状态转移方程

所以题目的完整状态转移方程如下

根据状态转移方程可以得知，dp[i][j]是依赖第i-1行的数据推导出来的，同行之间没有依赖关系，所以可以通过从左到右从上到下的顺序推导出整个二维数组，最终dp[n-1][capacity]的数据，就是题目要的返回结果。题目的代码贴在下面，供大家进行参考。

public static int maxValueDp(int[] weight, int[] value, int capacity) {
    int n = weight.length;

    // 1. 定义dp数组的含义：dp[i][j]的含义：在0 ～ i号物品中，背包容量剩余j，能拿到到最大价值是多少
    int[][] dp = new int[n][capacity + 1];

    // 2. 数组的初始化值：dp[i][0] = 0，因为背包容量为0   dp[0][j] = j >= weight[0] ? value[0] : 0;
    for (int i=0; i<n; i++) {
        dp[i][0] = 0;
    }

    for (int j=0; j<=capacity; j++) {
        dp[0][j] = j >= weight[0] ? value[0] : 0;
    }

    // 动态转移方程：
    for (int i=1; i<n; i++) {
        for (int j=1; j<=capacity; j++) {
            int curNotTake = dp[i - 1][j];

            int curTake = 0;
            if (j >= weight[i]) {
                curTake = dp[i - 1][j - weight[i]] + value[i];
            }
            dp[i][j] = Math.max(curNotTake, curTake);
        }
    }

    return dp[n-1][capacity];
}

二维数组压缩成一维数组

在之前的文章中我们还提到了二维数组空间压缩的技巧，在这个问题中也是同样适用的。需要注意的问题是，在二维数组中，dp[i][j]的推导可能需要上一行中第0～i列数据，而不会依赖i+1 ~ capacity列的数据，所以压缩成一维数组后，每一行需要从右向左推导，才不会污染掉上一行的数据。此外j在向左推导的过程中，最多推导到第weight[i]列就可以了，因为再向左推导的话，背包的剩余容量已经装不下i号物品了，肯定和上一行的结果是相等，所以就没必要再推下去了。具体的代码我也贴在下面。

public static int maxValueDpSaveSpace(int[] weight, int[] value, int capacity) {
    int n = weight.length;

    // 1. 定义dp数组的含义：dp[i][j]的含义：在0 ～ i号物品中，背包容量剩余j，能拿到到最大价值是多少
    int[] dp = new int[capacity + 1];

    // 2. 数组的初始化值：dp[i][0] = 0，因为背包容量为0   dp[0][j] = j >= weight[0] ? value[0] : 0;

    for (int j=0; j<=capacity; j++) {
        dp[j] = j >= weight[0] ? value[0] : 0;
    }

    // 动态转移方程：
    for (int i=1; i<n; i++) {
        dp[0] = 0;
        for (int j=capacity; j>=weight[i]; j--) {
            int curNotTake = dp[j];
            int curTake = dp[j - weight[i]] + value[i];

            dp[j] = Math.max(curNotTake, curTake);
        }
    }

    return dp[capacity];
}

完全背包

完全背包是0/1背包的一个衍生问题。0/1背包中每个物品只有一件，所以针对第i号物品只有两个状态，就是拿或者不拿。在完全背包问题中，每件物品的数量是无限的，请你求出在这种情况下能拿到的物品最大价值。想一下这个问题应该怎么解决呢？

假设我们还是使用一个二维数组dp，dp[i][j]代表的含义和上面一样，还是0~i号物品在背包容量为j时能拿到的最大价值。如果你对上文中的01背包问题完全掌握了的话，那你一定能得出以下状态转移方程

(公式一)

当然，这里的k是有取值范围的，需要j−k×weight[i]≥0j-k \times weight[i] \ge 0j−k×weight[i]≥0，即 k≤j/weight[i]k \le j / weight[i]k≤j/weight[i]

对上面的这个公式做一些小小的改动，我们让 j = j - weight[i]，就可以得到

(公式二)

此时，k的取值范围是j−weight[i]−k×weight[i]≥0j - weight[i] - k \times weight[i] \ge 0j−weight[i]−k×weight[i]≥0，即 k+1≤j/weight[i]k + 1 \le j / weight[i]k+1≤j/weight[i]

再把这个式子左右各自加上一个value[i]，那么式子就变成了

(公式三)

其中k+1≤j/weight[i]k+1 \le j / weight[i]k+1≤j/weight[i]

注意观察公式一和公式三

可以看到，红线框选的这部分公式是完全一致的。虽然在公式的最后，公式一 一直到k，公式三 一直到k+1，但一中的k和三中的k + 1取值范围是完全相同的，所以我们就可以把公式一红框中的内容替换一下，就能得到完全背包问题的状态转移方程

我们尝试理解一下这个转移方程：我们要求0i号物品中，背包容量为j时的最大价值，对于i号物品有两种可能，可以不拿，这样的结果就是dp[i-1][j]，也可以至少拿一件，这样我们就把背包中一件i号物品的重量腾出来，再去计算0i号物品在背包容量为j−weight[i]j-weight[i]j−weight[i]时的最大价值，再加上一件i号物品的价值，在两种可能中取最大值，就是这个问题的解了。

思考一下转移方程的初始值，当j=0j = 0j=0时，背包没有容量，所以结果是0，当i = 0时，dp[i-1][j]是不存在的，可以直接认为是0，然后与后面的一项进行比较；当j<weight[i]时，说明背包的容量装不下第i件物品，所以可以认为dp[i][j] = dp[i-1][j]，至此，这个问题的状态转移方程我们得出如下

观察这个状态转移方程，可以发现，dp[i][j]的值是根据第i-1行，第j列的数据和第i行中0～j-1列左侧的数据推出的，所以依然可以通过从上到下，从左到右的顺序推出整个二维数组，这样我们就得到如下的代码。

public static int maxValueFullBag(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[][] dp = new int[n][capacity + 1];

    for (int i=0; i<n; i++) {
        for (int j=0; j<=capacity; j++) {
            if (j == 0) {
                dp[i][j] = 0;
                continue;
            }

            int p1 = i > 0 ? dp[i-1][j] : 0;
            int p2 = j >= weight[i] ? dp[i][j-weight[i]] + value[i] : 0;

            dp[i][j] = Math.max(p1, p2);
        }
    }

    return dp[n-1][capacity];
}

由于求出dp[i][j]时需要的是上方的元素和左侧的元素，所以这个问题还是可以使用一位数组进行空间优化，注意这里和0/1背包不同，如果你已经完全掌握二维数组到一维数组的优化的话，那么这里你一定能知道在内层for循环中需要从左向右推，具体原因就不再赘述了。代码贴在下面，供大家参考。

public static int maxValueFullBagSavePackage(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[] dp = new int[capacity + 1];

    for (int i=0; i<n; i++) {
        for (int j=0; j<=capacity; j++) {
            if (j == 0) {
                dp[j] = 0;
                continue;
            }

            int p1 = i > 0 ? dp[j] : 0;
            int p2 = j >= weight[i] ? dp[j-weight[i]] + value[i] : 0;

            dp[j] = Math.max(p1, p2);
        }
    }

    return dp[capacity];
}

总结

01背包和完全背包是所有背包问题中最重要的两个分类，也是所有背包问题的基础，在leetcode中有非常多关于这两种背包问题的题目，比如《518. 零钱兑换 II》、《377. 组合总和 Ⅳ》等，大家赶紧去试试吧。