乐趣区

关于java:Java算法系列背包问题

jiezi

背包问题是动静布局算法中十分经典的一类问题，也是口试面试中常见的一类问题。

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

上面将总结 0/ 1 背包问题、 齐全背包问题 、 多重背包问题 三类问题。对于混合背包问题，难度较大，个别口试面试题也不会过多波及。

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

一、0/ 1 背包问题

1.1 经典 0 / 1 背包问题

你有一个背包，最多能包容的分量是 m。当初有 n 个物品，第 i 个物品的分量为 w[i] , 价值为 v[i]。求这个背包至少能装多大价值的物品？

本例可参考：NC11【模板】01 背包

动静布局是一个将大问题划分为小问题进行解决，从而一步步获取最优解的过程。对于 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}
$$

给出如下一个例子：

背包的承重 m = 5。当初有 4 个物品如下，求背包至少能装多大价值的物品：

物品 分量 价值
1 2 12
2 1 10
3 3 20
4 2 15

对于 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 恰好装满问题

你有一个背包，最多能包容的分量是 m。当初有 n 个物品，第 i 个物品的分量为 w[i] , 价值为 v[i]。若背包 恰好装满，求至少能装多大价值的物品？如果无解请返回 0。

本例可参考：NC11【模板】01 背包

若应用空间优化，则应初始化 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 背包问题中，对于所有的物品只有放与不放两种状况。而 齐全背包问题 就不一样了，在齐全背包问题中，每种物品都有有限件可用：

你有一个背包，最多能包容的分量是 m。当初有 n 种物品，每种物品有任意多个，第 i 个物品的分量为 w[i] , 价值为 v[i]。求这个背包至少能装多大价值的物品？

本例可参考：NC12【模板】齐全背包

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 {for (int k = 1; k <= j / w[i - 1]; k++) {int temp = Math.max(dp[i - 1][j],
                            k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]);
                    dp[i][j] = Math.max(dp[i][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 恰好装满问题

你有一个背包，最多能包容的分量是 m。当初有 n 种物品，每种物品有任意多个，第 i 个物品的分量为 w[i] , 价值为 v[i]。若背包 恰好装满，求至少能装多大价值的物品？如果无解请返回 0。

本例可参考：NC12【模板】齐全背包

若应用空间优化，则应初始化 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]);
    }
}

三、多重背包问题

你有一个背包，最多能包容的分量是 m。当初有 n 种物品，第 i 个物品的分量为 w[i] , 价值为 v[i]，数量为 c[i]。求这个背包至少能装多大价值的物品？

本例可参考：多重背包

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 {for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) { // 比照齐全背包，仅需批改此处
                    int temp = Math.max(dp[i - 1][j], k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]);
                    dp[i][j] = Math.max(dp[i][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. 背包问题 - 笔记整顿
退出移动版