（详解）背包问题中的套路

天道Vax的时间宝藏

发布于 2021-08-11 11:11:02

2330

发布于 2021-08-11 11:11:02

一、概述

背包问题是一类比较 特殊的动态规划 问题，这篇文章的侧重点会在答案的推导过程上，我们还是会使用之前提到的解动态规划问题的四个步骤来思考这类问题。

在讲述背包问题之前，首先提及一下，背包类动态规划问题和其他的动态规划问题的不同之处在于，背包类动态规划问题会选用值来作为动态规划的状态，你可以回顾下之前我们讨论过的动态规划问题，基本上都是利用数组或者是字符串的下标来表示动态规划的状态。

针对背包类问题，我们依然可以 画表格 来辅助我们思考问题，但是背包类问题有基本的雏形，题目特征特别明显，当你理解了这类问题的解法后，遇到类似问题基本上不需要额外的辅助就可以给出大致的解法，这也就是说，学习背包类问题是一个性价比很高的事情，理解了一个特定问题的解法，基本上一类问题都可以直接套这个解法。

二、问题雏形

首先我们来看看这样一个问题：

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 C[i]，价值是 W[i]。求解将哪些物品装入背包可使价值总和最大。求出最大总价值

话不多说，我们还是按之前的分析四步骤来看看这个问题：

问题拆解

我们要求解的问题是 “背包能装入物品的最大价值”，这个问题的结果受到两个因素的影响，就是背包的大小，以及物品的属性（包括大小和价值）。对于物品来说，只有两种结果，放入背包以及不放入背包，这里我们用一个例子来画画表格：

假设背包的大小是 10，有 4 个物品，体积分别是 [2,3,5,7]，价值分别是 [2,5,2,5]。

1、如果我们仅考虑将前一个物品放入背包，只要背包体积大于 2，此时都可以获得价值为 2 的最大价值：

2、如果我们仅考虑将前两个物品放入背包，如果背包体积大于或等于 5，表示两个物体都可放入，此时都可以获得价值为 2+5=7 的最大价值，如果不能全都放入，那就要选择体积不超，价值最大的那个：

3、如果我们仅考虑将前三个物品放入背包，如果背包体积大于或等于 10，表示三个物体都可放入，此时都可以获得价值为 2+5+2=9 的最大价值，如果不能全都放入，那就要选择体积不超，价值最大的那个方案：

4、如果我们考虑将所有物品放入背包，我们可以依据前三个物品放入的结果来制定方案：

这样，我们就根据物品和体积将问题拆分成子问题，也就是 “前 n 个物品在体积 V 处的最大价值” 可以由 “前 n - 1 个物品的情况” 推导得到。

状态定义

在问题拆解中，我们得知问题其实和背包的体积还有当前考虑的物品有关，因此我们可以定义 dp[i][j] 表示 “考虑将前 i 个物品放入体积为 j 的背包里所获得的最大价值”

递推方程

当我们考虑是否将第 i 个物品放入背包的时候，这里有两种情况

不放入，也就是不考虑第 i 个物品，那么问题就直接变成了上一个子问题，也就是考虑将 i - 1 个物品放入背包中，这样当前问题的解就是之前问题的解：

dp[i][j] = dp[i - 1][j]

如果背包体积大于第 i 个物品的体积，我们可以考虑将第 i 个物品放入，这个时候我们要和之前的状态做一个比较，选取最大的方案：

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - C[i]] + W[i])

实现

实现这一环节还是主要考虑状态数组如何初始化，你可以看到，我们每次都要考虑 i - 1，另外还要考虑背包体积为 0 的情况，因此初始化数组时多开一格可以省去不必要的麻烦

public int zeroOnePack(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;

    // dp[i][j]: 对于下标为 0～i 的物品，背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];

    // 背包空的情况下，价值为 0
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不选物品 i 的话，当前价值就是取到前一个物品的最大价值，也就是 dp[i - 1][j]
            dp[i][j] = dp[i - 1][j];

            // 如果选择物品 i 使得当前价值相对不选更大，那就选取 i，更新当前最大价值
            if ((j >= C[i - 1]) && (dp[i][j] < dp[i - 1][j - C[i - 1]] + W[i - 1])) {
                dp[i][j] = dp[i - 1][j - C[i - 1]] + W[i - 1];
            }
        }
    }

    // 返回，对于所有物品（0～N），背包容量为 V 时的最大价值
    return dp[n][V];
}

这里还有一个空间上面的优化，如果你回到我们之前画的表格，考虑前 i 个问题的状态只会依赖于前 i - 1 个问题的状态，也就是 dp[i][...] 只会依赖于 dp[i - 1][...]，另外一点就是当前考虑的背包体积只会用到比其小的体积。

基于这些信息，我们状态数组的维度可以少开一维，但是遍历的方向上需要从后往前遍历，从而保证子问题需要用到的数据不被覆盖，优化版本如下：

public int zeroOnePackOpt(int V, int[] C, int[] W) { 
    // 防止无效输入
    if ((V <= 0) || (C.length != W.length)) {
        return 0;
    }

    int n = C.length;

    int[] dp = new int[V + 1];

    // 背包空的情况下，价值为 0
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = V; j >= C[i]; --j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }

    return dp[V];
}

这里，因为物品只能被选中 1 次，或者被选中 0 次，因此我们称这种背包问题为 01 背包问题。

还有一类背包问题，物品可以被选多次或者 0 次，这类问题我们称为 完全背包问题，这类背包问题和 01 背包问题很类似，略微的不同在于，在完全背包问题中，状态 dp[i][j] 依赖的是 dp[i - 1][j] 以及 dp[i][k] k < j，你可以看看下面的实现代码：

public int completePack(int V, int[] C, int[] W) {
    // 防止无效输入
    if (V == 0 || C.length != W.length) {
        return 0;
    }

    int n = C.length;

    // dp[i][j]: 对于下标为 0～i 的物品，背包容量为 j 时的最大价值
    int[][] dp = new int[n + 1][V + 1];

    // 背包空的情况下，价值为 0
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= V; ++j) {
            // 不取该物品
            dp[i][j] = dp[i - 1][j];

            // 取该物品，但是是在考虑过或者取过该物品的基础之上(dp[i][...])取
            // 0-1背包则是在还没有考虑过该物品的基础之上(dp[i - 1][...])取
            if ((j >= C[i - 1]) && (dp[i][j - C[i - 1]] + W[i - 1] > dp[i][j])) {
                dp[i][j] = dp[i][j - C[i - 1]] + W[i - 1];
            }
        }
    }

    // 返回，对于所有物品（0～N），背包容量为 V 时的最大价值
    return dp[n][V];
}

类似的，我们还是可以对状态数组进行空间优化，依据我们之前讨论的状态之间的依赖关系，完全背包的空间优化我们直接把状态数组少开一维即可，遍历方式都不需要改变：

public int completePackOpt(int V, int[] C, int[] W) {
    if (V == 0 || C.length != W.length) {
        return 0;
    }

    int n = C.length;
    int[] dp = new int[V + 1];
    for (int i = 0; i < n; ++i) {
        for (int j = C[i]; j <= V; ++j) {
            dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
        }
    }

    return dp[V];
}