深刻分析多重背包问题（上篇）
前言
在后面的两篇文章当中，咱们曾经认真的探讨了01背包问题和齐全背包问题，在本篇文章当中将给大家介绍另外一种背包问题——多重背包问题，多重背包问题的物品数量介于01背包问题和齐全背包问题之间，他的物品的数量是无限个！
多重背包问题介绍
有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
留神：下面应用到的字符含意在本篇文章当中都一样。
多重背包问题跟01背包和齐全背包的区别都是在物品的可用次数上，01背包只能应用一次，多重背包可用应用无数次，而多重背包可用应用屡次。
背包问题温习——01背包的动静转移方程
01背包的动静转移方程
01背包问题当中，咱们是应用一个二维数组dp[i][j]进行计算，dp[i][j]示意在只应用前i个物品且背包容量为j的状况下，咱们可能取得的最大的收益。在这个状况下，咱们依据以后背包容量j判断是否能装入第i个物品能够失去上面两个方程：
$$dp[i][j] = \begin{cases}max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]), j \ge v[i]\\dp[i - 1][j] , j \lt v[i]\end{cases}$$
下面01背包的公式的第二条比较简单，如果背包容量不足以包容第i件物品，那么只能从前i - 1物品当中抉择了。咱们来仔细分析一下第一条公式。
如果以后背包容量能够包容第i个物品，那么咱们就能够抉择第i件物品或者不抉择，咱们应该抉择两种抉择当中收益更大的那个。
- 如果咱们不抉择第
i个物品，那么咱们就可能应用容量为j的背包去抉择前i - 1个物品，这种状况下咱们的最大收益为dp[i - 1][j]。 - 如果抉择第
i个物品，那么咱们背包容量还剩下j - v[i]，还能够抉择剩下的i - 1个物品，而且咱们的收益须要加上w[i]，因而咱们的收益为max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])。
将多重背包转化成01背包
在多重背包的问题当中，咱们对于一种物品咱们能够应用屡次，比说$A$物品咱们能够用三次。事实上咱们能够将多重背包转化成01背包，比方咱们能够将三个$A$物品变成三个不同的物品，所谓不同就是他们的名字不一样，然而他们的价值和体积都是一样的，假如$A$的体积为$V_a$，价值为$W_a$，可能应用的次数为3次，那么咱们能够将其转化成$A_1$，$A_2$，$A_3$，这三个物品的体积和价值均为$V_a$和$W_a$，这样的话$A$能够应用3次就转化成了$A_1$、$A_2$和$A_3$均只能应用一次。通过这种转换咱们就将多重背包转化成了01背包。
多重背包Java代码：
import java.util.ArrayList;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); ArrayList<Integer> v = new ArrayList<>(); ArrayList<Integer> w = new ArrayList<>(); for (int i = 0; i < N; i++) { int vi = scanner.nextInt(); int wi = scanner.nextInt(); int t = scanner.nextInt(); for (int j = 0; j < t; j++) { v.add(vi); w.add(wi); } } int[][] dp = new int[v.size() + 1][V+ 1]; // 对第0行进行初始化操作 for (int i = v.get(0); i <= V; ++i) { dp[0][i] = w.get(0); } for (int i = 1; i < v.size(); ++i) { for (int j = 0; j <= V; ++j) { if (j >= v.get(i)) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v.get(i)] + w.get(i)); } else { dp[i][j] = dp[i - 1][j]; } } } System.out.println(dp[v.size() - 1][V]); }}和01背包一样，咱们对多重背包也能够应用单行数组进行优化：
import java.util.ArrayList;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); ArrayList<Integer> v = new ArrayList<>(); ArrayList<Integer> w = new ArrayList<>(); for (int i = 0; i < N; i++) { int vi = scanner.nextInt(); int wi = scanner.nextInt(); int t = scanner.nextInt(); for (int j = 0; j < t; j++) { v.add(vi); w.add(wi); } } int[] f = new int[V + 1]; for (int i = 0; i < v.size(); i++) { for (int j = V; j >= v.get(i); j--) { f[j] = Math.max(f[j], f[j - v.get(i)] + w.get(i)); } } System.out.println(f[V]); }}多重背包动静转移方程
在背包容量足够的状况下，01背包的动静转移方程为：
$$dp[i][j] =max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]), j \ge v[i]$$
上述的动静转移方程是基于每个物品选和不选，那么对于多重背包来说，如果物品能够抉择$S$次，咱们能够抉择0次，能够抉择1次，......，能够抉择$S$次，咱们就须要从这些状况当中抉择收益最大的那次（前提是背包可能包容下相应次数的物品），因而多重背包的动静转移方程如下（ $T = min(S, \frac{V}{v_i})$，其中$S$示意物品可能抉择的次数，$v_i$示意物品的体积，$V$示意以后背包的容量）：
$$dp[i][j] = max\\\{ \\dp[i - 1][j], \\dp[i - 1][j - v[i]] + w[i],\\dp[i - 1][j - v[i] * 2] + w[i] * 2, \\..., \\dp[i - 1][j - v[i] * T] + w[i] * T\\\}$$
基于下面的动静转移方程咱们能够失去上面的代码：
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); int[] w = new int[N]; int[] v = new int[N]; int[] t = new int[N]; int[] f = new int[V + 1]; for (int i = 0; i < N; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); t[i] = scanner.nextInt(); } for (int i = 0; i < N; i++) { for (int j = V; j >= v[i]; --j) { // 这个循环就示意多重背包的动静转移公式了 // 在这段代码当中尽管 Math.max的参数只有量 // 然而有一段循环，将这个循环展开，他示意的 // 就是多重背包的动静转移方程 for (int k = 1; k <= t[i] && j >= v[i] * k; k++) { f[j] = Math.max(f[j], f[j - v[i] * k] + w[i] * k); } } } System.out.println(f[V]); }}总结
在本篇文章当中次要跟大家介绍了多重背包的两种解决办法，一种是将多重背包转化成01背包，另外一种办法是依据多重背包的动静转移方程去解决问题，能够看出后者的空间复杂度更低，更节约内存空间。下期咱们用另外一种办法去优化多重背包。
以上就是本篇文章的所有内容了，心愿大家有所播种，我是LeHung，咱们下期再见！！！
更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu...
关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。