【Java算法系列】背包问题

如果您对一维动态规划算法和二维动态规划算法不了解，阅读本文之前，可以先阅读：【Java算法系列】动态规划算法（二）。

背包问题是动态规划算法中非常经典的一类问题，也是笔试面试中常见的一类问题。

背包问题有四类：0/1背包问题、完全背包问题、多重背包问题、混合背包问题。

下面将总结0/1背包问题、完全背包问题、多重背包问题三类问题。对于混合背包问题，难度较大，一般笔试面试题也不会过多涉及。

笔者自认为本文将背包问题总结地比较全面，可难免有错漏，欢迎批评指正！

一、0/1背包问题

1.1 经典0/1背包问题

动态规划是一个将大问题划分为小问题进行解决，从而一步步获取最优解的过程。对于0/1背包问题，考虑子问题“求解将前 i 个物品放入容量为 j 的背包中的最大价值”，设 F(i, j) 为将前 i 个物品放入容量为 j 的背包中最优解的总价值。对于第 i 个物品，事实上有两种情况：

• w[i] > j，即第 i 个物品的重量大于背包容量 j，则不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值，即 F[i][j] = F[i-1][j]。

• w[i] ≤ j，即第 i 个物品的重量不大于背包容量 j，则有以下两种情况的最大值决定：

  • 不放入该物品，此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值，即 F[i][j] = F[i-1][j]。
  • 放入该物品，此时背包的剩余容量为 j-w[i]，则最优解的值等同于“第 i 个物品的价值”与“前 i-1 个物品放入容量为 j-w[i] 的背包中最优解的值”之和，即F[i][j] = v[i] + F[i - 1][j - w[i]]。

（注意理解上述过程：是先比较第i个物品的重量与背包容量，若能放，再比较放入第i个物品与不放入第i个物品哪个能得到前i个物品情况下的最优解！）

因此可以得到递推公式：

$$初始条件：F(i,0) = F(0, j) = 0 \\$$

和

$$F(i,j)=\begin{cases}F(i-1, j), & w[i] > j \\max\{ F(i-1,j),v[i] + F(i - 1)(j - w[i]) \}, & w[i] ≤ j\end{cases}$$

给出如下一个例子：

对于n=4, m=5的背包问题，应建立一个dp[n+1][m+1]的二维表。填表过程如下：

你是否对这个填表过程感到熟悉？是的，所谓背包问题，其实还是前面的二维动态规划问题！

填表过程的代码如下：

/**
 * @param w 物品的重量
 * @param v 物品的价值
 * @param n 物品的个数
 * @param m 背包的容量
 */
public static int knapsack1(int[] w, int[] v, int n, int m) {
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < m + 1; j++) {
            if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = Math.max(dp[i - 1][j],
                                    v[i - 1] + dp[i - 1][j - w[i - 1]]);
        }
    }
    return dp[n][m];
}

看到这里，你可能会感到疑惑，为什么要这样填表？这样填写出来的表不是与这n件物品的存储顺序有关吗？但是常识告诉我们，这个问题的解答不应该与物品顺序相关呀？

是的，本问题的核心思想就是“求解将前 i 个物品放入容量为 j 的背包中的最大价值”，而不同的物品顺序显然填出来的表是不相同的。但是，这个动态规划表并不是我们需要的结果，我们也并不关心”前 i 个物品放入容量为 j 的背包“的问题，我们关心的是“n 个物品放入容量为 m 的背包”的问题。虽然不同物品顺序得出的动态规划表不一样，但其最优解的值一定是一样的，而这才是我们关心的。

接下来将介绍如何回溯得到最优方案。

1.2 回溯、输出最优解

我们先用图示的方法看看如何从动态规划表进行回溯、得出最优解的方案：

上述回溯过程似乎很复杂，但是在代码中可以加入一个辅助数组path[][]来记录更新的物品。则求出最优方案的代码如下：

public static void knapsack2(int[] w, int[] v, int n, int m) {
    int[][] dp = new int[n + 1][m + 1];
    int[][] path = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else {
                if (dp[i - 1][j] < v[i - 1] + dp[i - 1][j - w[i - 1]]) {
                    dp[i][j] = v[i - 1] + dp[i - 1][j - w[i - 1]];
                    path[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
    }
    for (int i = n, j = m; i >= 0; i--) {
        if (path[i][j] == 1) {
            System.out.println("放入第" + i + "个物品");
            j = j - w[i - 1];    // 回溯过程体现在这里！
        }
    }
    System.out.println("最大价值为: " + dp[n][m]);
}

上文提到，不同的物品顺序得到的动态规划表不同，但最优解的值是相同的。但是，相同的只有最优解的值，由于最优解的方案是需要根据动态规划过程回溯得到的，因此最优解的方案却不一定一样。

例如将上例中物品1的价值修改为10，求得的最优解虽然同样是35，却存在 {物品1, 物品2, 物品4} 和 {物品3, 物品4} 两个最优方案。你可以使用下面两个例子进行测试：

// 示例1
int[] w = {2, 1, 3, 2};         // 物品的重量
int[] v = {10, 10, 20, 15};     // 物品的价值
int n = w.length;               // 物品的个数
int m = 5;                      // 背包的容量
knapsack2(w, v, n, m);

// 示例2
int[] w = {3, 1, 2, 2};         // 物品的重量
int[] v = {20, 10, 10, 15};     // 物品的价值
int n = w.length;               // 物品的个数
int m = 5;                      // 背包的容量
knapsack2(w, v, n, m);

以上两个例子仅仅交换了物品的顺序，虽然最优解的值相同，但最优方案却不同。

那么，怎么判断最优解的方案是否唯一呢？在填表过程中，如果 F[i-1][j] 与 v[i] + F[i - 1][j - w[i]] 相等，则可说明存在多个最优方案。

1.3 改进1：记忆功能

注：此方法不需掌握，可直接跳过。但是看完之后，相信你会对动态规划有更深一步的了解。

动态规划算法是自底向上的：动态规划算法从最小的子问题出发，使用较小子问题的解去填充表格，每个子问题只解一次。但是，有些较小的子问题的解常常不是必需的。

递归的算法是自顶向下的：递归算法对递推式的求解将导致需要不止一次地解公共的子问题。例如斐波那契数列问题，递归算法将多次重复计算相同值，因此效率非常低。

将自底向上的动态规划算法与自顶向下的递归算法结合起来，使它只对必要的子问题求解且只求解一次，这就是记忆功能的方法。该方法自顶向下地使用递归进行求解，但还需维护一个自底向上的动态规划表格：

public class MFKnapsackDemo {
    public static void main(String[] args) {
        int[] w = {2, 1, 3, 2};         // 物品的重量
        int[] v = {12, 10, 20, 15};     // 物品的价值
        int n = w.length;               // 物品的数量
        int m = 5;                      // 背包的容量
        MFKnapsack mfKnapsack = new MFKnapsack(m, w, v);
        System.out.println("最大价值为: " + mfKnapsack.knapsack(n, m));
    }
}

class MFKnapsack {
    static int n;          // 物品的个数
    static int m;          // 背包的容量
    static int[] w;        // 物品的重量
    static int[] v;        // 物品的价值
    static int[][] dp;     // 动态规划表

    /**
     * 将w[]、v[]、dp[][]作为全局变量
     * 对于dp[][]，将第0行、第0列初始化为0，其余全部初始化为-1
     */
    public MFKnapsack(int m, int[] w, int[] v) {
        this.m = m;
        this.w = w;
        this.v = v;
        this.n = w.length;
        dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = -1;
            }
        }
    }

    public static int knapsack(int i, int j){
        if (dp[i][j] < 0){
            if (j < w[i-1])
                dp[i][j] = knapsack(i-1, j);
            else
                dp[i][j] = Math.max(knapsack(i-1, j), v[i-1] + knapsack(i-1, j-w[i-1]));
        }
        return dp[i][j];
    }
}

递归调用过程不便画出填表的过程，对于该例，其动态规划表dp[][]为：

对比普通动态规划算法计算出的表格来看，加入记忆功能后，算法将只对必要的子问题进行求解。

但是，加入记忆功能后，它的时间效率与常规的动态规划算法是一致的，加入记忆功能对性能的改进并不会超过一个常数因子。但如果一个值的计算无法在常数时间内完成，那么记忆功能对性能的改进可能会更显著。

1.4 改进2：空间优化

回到经典的01背包问题，我们再看一看核心表达式：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j],v[i] + dp[i - 1][j - w[i]] \}, & w[i] ≤ j\end{cases}$$

可以看到，求解 dp[i][j] 时，其实只需要第 i-1 行的第 j 列或者第 j - w[i] 列的结果，其他行的结果是不需要的。所以我们真正需要的只有 i-1 这一行，在对 i 遍历时，第 i 层可以自动滚动覆盖掉第 i-1 层。

那么我们就可以进行空间优化，将其优化为一维数组：

$$dp[j]=\begin{cases}dp[j], & w[i] > j \\max\{ dp[j],v[i] + dp[j - w[i]] \}, & w[i] ≤ j\end{cases}$$

如果按照这个公式填表，会发现存在以下问题：

出现这个问题的原因是：从左向右遍历会导致，后修改的右边的值需要用到先修改的左边的值。

那么如何解决呢？很简单，将其修改为从右向左遍历即可：

根据填表过程，可以得到01背包问题的空间优化算法：

public static int knapsack3(int[] w, int[] v, int n, int m) {
    int[] dp = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            //if (w[i - 1] > j) dp[j] = dp[j];
            if (w[i - 1] <= j)
                dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]);
        }
    }
    return dp[m];
}

1.5 恰好装满问题

若使用空间优化，则应初始化 dp[0] 为 0，其余初始化为Integer.MIN_VALUE。

最后若 dp[m] 为正数则说明恰好装满，若为负数则说明无解。

对于NC11 【模板】01背包，给出我的代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[n];
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        int[] dp = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (w[i - 1] <= j)
                    dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]);
            }
        }
        System.out.println(dp[m]);

        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                if (w[i - 1] <= j)
                    dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]);
            }
        }
        if (dp[m] < 0) dp[m] = 0;
        System.out.print(dp[m]);
    }
}

二、完全背包问题

看到这里先问一下大家，为什么叫做0/1背包问题呢？因为在0/1背包问题中，对于所有的物品只有放与不放两种情况。而完全背包问题就不一样了，在完全背包问题中，每种物品都有无限件可用：

2.1 经典完全背包问题

我们先看一看经典01背包问题的方程：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j],v[i] + dp[i - 1][j - w[i]] \}, & w[i] ≤ j\end{cases}$$

对于完全背包问题，由于每种物品有任意多个，那么我们可以再加入一层循环 k，k 代表第 i 种物品有 k 件。

则 v[i] 应修改为 k*v[i]，w[i] 应修改为 k*w[i]，且应对遍历的k*v[i]+dp[i-1][j-k*w[i]]取最大值，因此可以得到完全背包问题的方程：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j], max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j\end{cases}$$

代码如下：

public static int CompleteKnapsack1(int[] w, int[] v, int n, int m) {
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else {
                int temp = 0;
                for (int k = 1; k <= j / w[i - 1]; k++) {
                    temp = Math.max(temp, k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]);
                }
                dp[i][j] = Math.max(dp[i - 1][j], temp);
            }
        }
    }
    return dp[n][m];
}

但是这种算法的时间复杂度将达到 O(n^3)，性能太差，因此需要进行时间复杂度的优化。

2.2 改进1：时间优化

观察完全背包问题的方程：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j &①\\max\{ dp[i-1][j],max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j &②\end{cases}$$

我们发现，当 k=0 时，有dp[i-1][j]与k*v[i]+dp[i-1][j-k*w[i]]相等，故以上方程可以合并为：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j &①\\max\{ k * v[i] + dp[i - 1][j - k * w[i]] \}, & 0 ≤ k ≤ \frac {j} {w[i]} &②\end{cases}$$

对于式子②，我们知道有以下两种情况，二者的最大值即为 dp[i][j]：

• 不放入第 i 种物品。则有：

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

• 放入第 i 种物品。那么应该放入几件呢？由遍历计算得出的最大值决定：

  $$dp[i][j] = max\{ k * v[i] + f[i-1][j-k*w[i]] \} \tag{1 ≤ k ≤ j/w[i]}$$

  • 用 k+1 替换 k，该式可以写为：

  $$ \begin{aligned} dp[i][j] & = max\{ (k+1) * v[i] + f[i-1][j-(k+1)*w[i]] \} \\ & = max\{ k * v[i] + f[i-1][j-(k+1)*w[i]] \} +v[i]\\ & = max\{ k * v[i] + f[i-1][j-w[i]-k*w[i]] \} +v[i]\end{aligned}\\(0 ≤ k ≤ j/w[i])$$

  • 对于上述③式，用 j-w[i] 替换 j ，该式可以写为：

  $$dp[i][j-w[i]]=max\{ k * v[i] + dp[i - 1][j-w[i] - k * w[i]] \} \\(0 ≤ k ≤ j/w[i])$$

  • 观察以上两个式子，可以得到：

    $$dp[i][j] = dp[i][j-w[i]] + v[i] \tag{w[i] ≤ j}$$

综合不放入的情况与放入的情况，两者应取最大值，因此式子②可以写为：

$$dp[i][j] = max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \} \tag{w[i] ≤ j}$$

综上，结合式子①与式子②，因此完全背包问题的方程为：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j\\max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j\end{cases}$$

因此可以写出代码：

public static int CompleteKnapsack2(int[] w, int[] v, int n, int m) {
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = Math.max(dp[i - 1][j],
                                     dp[i][j - w[i - 1]] + v[i - 1]);
        }
    }
    return dp[n][m];
}

2.3 改进2：空间优化

观察完全背包问题的方程：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j\\max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j\end{cases}$$

可以看到，求解 dp[i][j] 时，其实只需要第 i-1 行的第 j 列或者当前第 i 行已经求过的第 j-w[i] 列的结果，其他行的结果是不需要的。

那么我们就可以进行空间优化，将其优化为一维数组：

$$dp[j]=\begin{cases}dp[j], & w[i] > j \\max\{ dp[j],dp[j - w[i]] +v[i]\}, & w[i] ≤ j\end{cases}$$

与0/1背包问题的空间优化不同，由于我们需要的第 i 行的第 j-w[i] 列在当前值 j 的左侧，因此我们必须对 j 从左向右遍历才能取到该值。

因此，空间优化后的完全背包问题的代码如下：

public static int CompleteKnapsack3(int[] w, int[] v, int n, int m) {
    int[] dp = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i - 1] <= j)
                dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
        }
    }
    return dp[m];
}

2.4 时间优化的思路转换

上面的时间优化的的数学过程是不是让你感到很妙又很晕呢？那么我们换一种思路。

我们知道，动态规划是一个将大问题划分为小问题进行解决，从而一步步获取最优解的过程。

我们将 F[i][j] 表示为“将前 i 个物品放入容量为 j 的背包中的最大价值”，对于第 i 种物品，有两种情况：

• w[i] > j，即第 i 个物品的重量大于背包容量 j。则不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值，即 F[i][j] = F[i-1][j]。

• w[i] ≤ j，即第 i 个物品的重量不大于背包容量 j。则有以下两种情况的最大值决定：

  • 不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中的最大价值，即 F[i][j] = F[i-1][j]。
  • 放入该物品。先放入一个物品，此物品的价值为v[i]，此时背包的剩余容量为 j-w[i]。那么剩下的j-w[i]应该怎么再放入物品 i 呢？该问题就等同于“将前 i 个物品放入容量为 j-w[i] 的背包中的最大价值”。因此，F[i][j] = v[i] + F[i][j-w[i]]。

因此可以得到递推公式：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j\\max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j\end{cases}$$

怎么样？是不是更好理解了呢？

2.5 恰好装满问题

若使用空间优化，则应初始化 dp[0] 为 0，其余初始化为Integer.MIN_VALUE。

最后若 dp[m] 为正数则说明恰好装满，若为负数则说明无解。

对于NC12 【模板】完全背包，给出我的代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[n];
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        int[] dp = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= w[i - 1])
                    dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
            }
        }
        System.out.println(dp[m]);

        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= w[i - 1])
                    dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
            }
        }
        if (dp[m] < 0) dp[m] = 0;
        System.out.print(dp[m]);
    }
}

三、多重背包问题

3.1 经典多重背包问题

我们先观察完全背包问题的方程：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j], max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j\end{cases}$$

那么，多重背包与完全背包的区别在哪里呢？多重背包仅仅是对物品的数量多了个限制k≤c[i]：

$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j], max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j & and & k ≤ c[i]\end{cases}$$

所以，仅仅需要对 k 循环的条件作修改即可。代码如下：

public static int MultipleKnapsack1(int[] w, int[] v, int[] c, int n, int m) {
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (w[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else {
                int temp = 0;
                for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) { //对比完全背包，仅需修改此处
                    temp = Math.max(temp, k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]);
                }
                dp[i][j] = Math.max(dp[i - 1][j], temp);
            }
        }
    }
    return dp[n][m];
}

3.2 改进1：空间优化

同样的，多重背包问题可以进行空间优化，其思路与0/1背包问题一致，需要考虑到：若从左向右遍历，会导致后修改的右边的值需要用到先修改的左边的值。

因此，多重背包问题的 j 值需要从右向左遍历：

public static int MultipleKnapsack2(int[] w, int[] v, int[] c, int n, int m) {
    int[] dp2 = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            if (w[i - 1] <= j) {
                for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) {
                    dp2[j] = Math.max(dp2[j],
                            k * v[i - 1] + dp2[j - k * w[i - 1]]);
                }
            }
        }
    }
    return dp[m];
}

3.3 改进2：二进制优化、单调队列优化

多重背包问题还可以进行二进制优化、单调队列优化。但笔者才疏学浅，就不多作介绍了。

OJ地址：多重背包的二进制优化、多重背包的单调队列优化

参考资料

1. 【尚硅谷】Java数据结构与算法
2. 清华大学出版社《算法设计与分析基础（第3版）》Anany Levitin 著 潘彦 译
3. 背包问题-笔记整理