动态规划 之多重背包 问题
1. 问题描述及分析
动态规划是一种解决复杂问题的方法，
它将一个大问题分解为若干个子问题，通过求解子问题，从而得到原问题的最优解。动态规划的核心思想是避免重复计算，利用已有的结果进行状态转移。
背包问题是一类经典的动态规划问题，
它描述了如何在给定的背包容量和若干个物品的重量和价值的情况下，选择物品放入背包，使得物品的总价值最大。背包问题有多种变形，其中一种是多重背包问题。
多重背包问题与01背包和完全背包的区别在于，
- 01背包问题是指每种物品只能选择0件或1件；
- 完全背包问题是指每种物品可以选择无限多件。
- 多重背包问题是在01背包问题和完全背包问题的基础上增加了每种物品的数量限制。
它可以描述为
一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
2. 动态规划表
假设输入是：
N = 5, C = 10, v = [2,3,4,5,6], w = [3,4,5,6,7], s = [1,2,1,2,1]
那么输出是：15，解释是：选一件物品 1，两件物品 2，一件物品 4，可使价值最大。
对应的动态规划表如下：
| i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 6 | 6 | 6 | 7 | 7 | 8 | 8 |
| 3 | 0 | 0 | 3 | 4 | 6 | 7 | 9 | 10 | 11 | 12 | 12 |
| 4 | 0 | 0 | 3 | 4 | 6 | 7 | 9 | 10 | 13 | 15 | 15 |
| 5 | 0 | 0 | 3 | 4 | 6 | 7 | 9 | 10 | 13 | 15 | 15 |
其中加粗的数字表示状态转移方程中的 max 值。
3. 解决思路
解决多重背包问题的方法有很多，其中一些常见的方法有：
-
- 将多重背包转化为01背包，即将每种物品拆分为n[i]个01物品，然后求解01背包问题。这种方法简单易懂，但是复杂度较高，为O(NW)。
- 使用二进制优化法，即将每种物品拆分为若干个01物品，但是每个01物品的重量和价值都是原来的2^k倍（k为非负整数），使得拆分后的总件数为O(log n[i])。这种方法可以降低复杂度到O(NW log N)。
- 使用单调队列优化法，即利用单调性和滑动窗口的思想，维护一个单调递减的队列，使得每次更新状态时只需要O(1)时间。这种方法可以将复杂度降低到O(NW)。
- 贪心算法：这种算法是基于每次选择当前最优的物品来放入背包，不考虑后续的影响。它的优点是简单快速，缺点是可能无法得到全局最优解。
4. 具体实现方案
下面我们用JAVA语言来实现这些方法，并给出相应的代码示例和注释。
4.1 方法一：转化为01背包
这种方法的思路是
将每种物品拆分为n[i]个01物品，然后按照01背包问题的状态定义和转移方程来求解。
我们定义状态dp[i][j]表示将前i种物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W。
我们将dp[0][0…W]初始化为0，表示将前0种物品（即没有物品）装入书包的最大价值为0。
当 i > 0 时 dp[i][j] 有两种情况：
-
- 不装入第i种物品，即 dp[i−1][j] ，同01背包；
- 装入第i种物品（前提是能装下），即 dp[i−1][j−w[i]] + v[i] ，同01背包；
所以状态转移方程为 dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]) // j >= w[i]
由于每种物品有n[i]个可选，所以我们需要对每个拆分后的01物品进行遍历，并更新对应的状态。
代码如下：
import java.util.Scanner;
public class MultiKnapsack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品种数
int V = sc.nextInt(); // 背包容量
int[] v = new int[N + 1]; // 体积数组
int[] w = new int[N + 1]; // 价值数组
int[] s = new int[N + 1]; // 数量数组
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
sc.close();
int[][] dp = new int[N + 1][V + 1]; // 状态数组
for (int i = 0; i <= V; i++) {
dp[0][i] = 0; // 初始化状态
}
for (int i = 1; i <= N; i++) { // 遍历物品
for (int j = 0; j <= V; j++) { // 遍历背包容量
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) { // 遍历物品数量
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]); // 状态转移
}
}
}
System.out.println(dp[N][V]); // 输出最大价值
}
}
实例实现：
public class MultiKnapsack2 {
public static void main(String[] args) {
int N = 3;
int V = 20;
int[] v = new int[]{2, 3, 4}; // volume
int[] w = new int[]{3, 5, 3}; // worth
int[] s = new int[]{3, 3, 6}; // size
System.out.println(dp(v, w, s, V, N));
}
public static int dp(int[] v, int[] w, int[] s, int V, int N) {
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
for (int k = 0; k <= s[i - 1] && v[i - 1] * k <= j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * v[i - 1]] + k * w[i - 1]);
}
}
}
return dp[N][V];
}
}
4.2 方法二：二进制优化
这种方法的思路是
将每种物品拆分为若干个01物品，但是每个01物品的重量和价值都是原来的2^k倍（k为非负整数），使得拆分后的总件数为O(log n[i])。
这样做的好处是可以减少拆分后的物品数量，从而减少状态转移的次数。具体的拆分方法是：
-
- 对于每种物品，我们先将其数量n[i]用二进制表示，例如n[i]=13，可以表示为1101；
- 然后我们将其拆分为若干个01物品，每个物品的数量为二进制位上的2^k，例如13可以拆分为8,4,1；
- 每个拆分后的物品的重量和价值都是原来的2^k倍，例如原来的重量和价值为v[i]和w[i]，那么拆分后的重量和价值分别为8v[i],8w[i],4v[i],4w[i],v[i],w[i]；
- 如果n[i]刚好是2^k，那么只需要拆分一个物品即可，例如n[i]=16，那么只需要一个16v[i],16w[i]的物品；
- 如果n[i]还有剩余，那么就将剩余的部分单独拆分为一个物品，例如n[i]=9，那么可以拆分为8,1,但是还剩下7个，那么就再拆分一个7v[i],7w[i]的物品。
拆分后的物品都是01物品，所以我们可以按照01背包问题的状态定义和转移方程来求解。
我们定义状态dp[j]表示将前i种物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W。
我们将dp[0…W]初始化为0，表示将前0种物品（即没有物品）装入书包的最大价值为0。
当 i > 0 时 dp[j] 有两种情况：
-
- 不装入第i种物品，即 dp[j] ，同01背包；
- 装入第i种物品（前提是能装下），即 dp[j−v[i]] + w[i] ，同01背包；
所以状态转移方程为 dp[j] = max(dp[j], dp[j−v[i]]+w[i]) // j >= v[i]
由于每种物品有多个可选，所以我们需要对每个拆分后的01物品进行遍历，并更新对应的状态。
代码如下：
import java.util.Scanner;
public class MultiKnapsack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品种数
int V = sc.nextInt(); // 背包容量
int[] v = new int[N + 1]; // 体积数组
int[] w = new int[N + 1]; // 价值数组
int[] s = new int[N + 1]; // 数量数组
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
sc.close();
int[] dp = new int[V + 1]; // 状态数组
for (int i = 0; i <= V; i++) {
dp[i] = 0; // 初始化状态
}
for (int i = 1; i <= N; i++) { // 遍历物品
int k = 1; // 拆分因子
while (k <= s[i]) { // 拆分数量不超过原数量
for (int j = V; j >= k * v[i]; j--) { // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]); // 状态转移
}
s[i] -= k; // 减去已拆分的数量
k <<= 1; // 拆分因子翻倍
}
if (s[i] > 0) { // 如果还有剩余数量
for (int j = V; j >= s[i] * v[i]; j--) { // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - s[i] * v[i]] + s[i] * w[i]); // 状态转移
}
}
}
System.out.println(dp[V]); // 输出最大价值
}
}
实例 实现如下：
public class MultiKnapsack {
public static void main(String[] args) {
int N = 3;
int V = 20;
int[] v = new int[]{2, 3, 4}; // volume
int[] w = new int[]{3, 5, 3}; // worth
int[] s = new int[]{3, 3, 6}; // size
System.out.println(dp(v, w, s, V, N));
}
public static int dp(int[] v, int[] w, int[] s, int V, int N) {
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
int k = 1;
while (k <= s[i - 1]) {
for (int j = V; j >= k * v[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - k * v[i - 1]] + k * w[i - 1]);
}
s[i - 1] -= k;
k <<= 1;
}
if (s[i - 1] > 0) {
for (int j = V; j >= s[i - 1] * v[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - s[i - 1] * v[i - 1]] + s[i - 1] * w[i - 1]);
}
}
}
return dp[V];
}
}
4.3 方法三：单调队列优化
这种方法的思路是
利用单调性和滑动窗口的思想，维护一个单调递减的队列，使得每次更新状态时只需要O(1)时间。
这样做的好处是可以避免枚举物品数量，从而减少状态转移的次数。具体的优化方法是：
-
- 对于每种物品，我们将其按照重量和价值的比例进行排序，即v[i]/w[i]从大到小排序；
- 然后我们将每种物品分成若干个组，每个组的重量和价值都是原来的2^k倍（k为非负整数），使得每个组的数量为1；
- 每个组内的物品都有相同的重量和价值比例，所以我们可以用一个单调递减的队列来存储每个组的最大价值；
- 当我们更新状态时，我们只需要从队首取出最大价值，然后将其加上当前物品的价值，再将其放入队尾；
- 如果队尾的价值小于队首的价值，那么就将其弹出，因为它不可能再被用到；
我们定义状态dp[j]表示将前i种物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W。
我们将dp[0…W]初始化为0，表示将前0种物品（即没有物品）装入书包的最大价值为0。
当 i > 0 时 dp[j] 有两种情况：
-
- 不装入第i种物品，即 dp[j] ，同01背包；
- 装入第i种物品（前提是能装下），即 dp[j−v[i]] + w[i] ，同01背包；
所以状态转移方程为 dp[j] = max(dp[j], dp[j−v[i]]+w[i]) // j >= v[i]
由于每种物品有多个可选，所以我们需要对每个拆分后的01物品进行遍历，并更新对应的状态。
代码如下：
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class MultiKnapsack {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品种数
int V = sc.nextInt(); // 背包容量
int[][] items = new int[N][3]; // 物品数组
for (int i = 0; i < N; i++) {
items[i][0] = sc.nextInt(); // 体积
items[i][1] = sc.nextInt(); // 价值
items[i][2] = sc.nextInt(); // 数量
}
sc.close();
int[] dp = new int[V + 1]; // 状态数组
Arrays.fill(dp, -1); // 初始化状态为-1
dp[0] = 0; // 将前0种物品装入书包的最大价值为0
Arrays.sort(items, new Comparator<int[]>() { // 按照重量和价值比例排序
@Override
public int compare(int[] o1, int[] o2) {
return Double.compare(o2[1] * 1.0 / o2[0], o1[1] * 1.0 / o1[0]);
}
});
for (int i = 0; i < N; i++) { // 遍历物品
int v = items[i][0]; // 当前物品体积
int w = items[i][1]; // 当前物品价值
int s = items[i][2]; // 当前物品数量
for (int r = 0; r < v; r++) { // 遍历余数
ArrayDeque<int[]> queue = new ArrayDeque<>(); // 单调队列
for (int j = r; j <= V; j += v) { // 遍历背包容量
if (dp[j] != -1) { // 如果当前状态有效
int val = dp[j] - j / v * w; // 计算当前状态的价值
while (!queue.isEmpty() && queue.peekLast()[0] <= val) { // 如果队尾的价值小于等于当前价值
queue.pollLast(); // 弹出队尾
}
queue.offerLast(new int[]{val, j}); // 将当前价值和容量加入队尾
}
if (!queue.isEmpty()) { // 如果队列不为空
dp[j] = queue.peekFirst()[0] + j / v * w; // 更新当前状态为队首的价值加上当前物品的价值
}
if (!queue.isEmpty() && queue.peekFirst()[1] == j - s * v) { // 如果队首的容量等于当前容量减去最大数量乘以体积
queue.pollFirst(); // 弹出队首，因为它不可能再被用到
}
}
}
}
int res = 0; // 最大价值
for (int i = 0; i <= V; i++) { // 遍历所有状态
res = Math.max(res, dp[i]); // 更新最大价值
}
System.out.println(res); // 输出最大价值
}
}
4.4 方法四：贪心算法
-
- 贪心算法：
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Greedy {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 物品种数
int c = sc.nextInt(); // 背包容量
int[] v = new int[n]; // 物品体积
int[] w = new int[n]; // 物品价值
int[] s = new int[n]; // 物品数量
for (int i = 0; i < n; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
sc.close();
// 调用贪心算法求解
double max_value = greedy(n, c, v, w, s);
System.out.println(max_value);
}
// 定义贪心算法方法
public static double greedy(int n, int c, int[] v, int[] w, int[] s) {
double[] r = new double[n]; // 物品性价比
for (int i = 0; i < n; i++) {
r[i] = (double) w[i] / v[i];
}
// 按性价比降序排序
Integer[] index = new Integer[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
Arrays.sort(index, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Double.compare(r[o2], r[o1]);
}
});
// 贪心选择
double max_value = 0;
for (int i : index) {
if (c >= v[i]) {
int num = Math.min(c / v[i], s[i]); // 选择最多能放的数量
max_value += num * w[i];
c -= num * v[i];
}
if (c == 0) break;
}
return max_value;
}
}5. 一些多重背包问题的练习题
来看看三道多重背包问题的练习题吧。你可以尝试用不同的方法来解决它们，并比较时间和空间复杂度。
这三道练习题都是多重背包问题的变形，但是有以下的不同：
-
- 练习题一是最基本的多重背包问题，每种物品的体积和价值都是固定的，只需要考虑数量的限制。
- 练习题二是在多重背包问题的基础上，增加了求方案数的要求，即在获得最大价值的情况下，有多少种不同的选择方式。这需要用一个辅助数组来记录方案数，并且在状态转移时进行相应的更新和取模。
- 练习题三是在多重背包问题的基础上，增加了每种物品有多个子类别的要求，即每种物品的体积和价值都是由若干个子类别组成的。这需要先对每种物品进行预处理，将其总体积，总价值和总数量计算出来，然后再按照普通的多重背包问题进行求解。
5.1 练习题一：
题目
有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
-
-
输入格式：第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
-
输出格式：输出一个整数，表示最大价值。
-
数据范围：0 < N,V ≤ 1000, 0 < vi,wi,si ≤ 1000
-
输入样例：
4 10 2 3 4 3 5 3 4 6 2 5 8 2
-
输出样例：
36
解答
练习题一的JAVA实现：
import java.util.Scanner;
public class MultiKnapsack {
// 定义一个独立于main的方法，用于求解多重背包问题
// 参数为物品种数N，背包容量V，体积数组v，价值数组w，数量数组s
// 返回值为最大价值
public static int solve(int N, int V, int[] v, int[] w, int[] s) {
// 定义一个一维数组dp，表示在不同的背包容量下，能获得的最大价值
// dp[j]表示在背包容量为j的情况下，能获得的最大价值
int[] dp = new int[V + 1];
// 遍历物品
for (int i = 1; i <= N; i++) {
// 遍历背包容量，从后往前遍历，避免覆盖之前的状态
for (int j = V; j >= v[i]; j--) {
// 遍历物品数量，从1到s[i]，并且满足j-k*v[i]>=0
for (int k = 1; k <= s[i] && j >= k * v[i]; k++) {
// 状态转移方程：dp[j] = max(dp[j], dp[j-k*v[i]] + k*w[i])
// 表示在背包容量为j时，可以选择放入k个第i种物品或者不放入第i种物品，取两者中的较大值作为最大价值
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
// 返回dp[V]，即在背包容量为V时，能获得的最大价值
return dp[V];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品种数
int V = sc.nextInt(); // 背包容量
int[] v = new int[N + 1]; // 体积数组
int[] w = new int[N + 1]; // 价值数组
int[] s = new int[N + 1]; // 数量数组
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
sc.close();
// 调用solve方法，传入参数，并打印返回值
System.out.println(solve(N, V, v, w, s));
}
}5.2 练习题二：
题目
有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出方案数。
-
-
输入格式：第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
-
输出格式：输出一个整数，表示方案数。由于答案可能很大，请输出答案模10^9+7的结果。
-
数据范围：0 < N,V ≤ 1000, 0 < vi,wi,si ≤ 1000
-
输入样例：
4 10 2 3 4 3 5 3 4 6 2 5 8 2 -
输出样例：
7
-
解答
练习题二的JAVA实现：
import java.util.Scanner;
public class MultiKnapsack {
public static final int MOD = (int)1e9 + 7; // 模数
// 定义一个独立于main的方法，用于求解多重背包问题
// 参数为物品种数N，背包容量V，体积数组v，价值数组w，数量数组s
// 返回值为方案数模10^9+7的结果
public static int solve(int N, int V, int[] v, int[] w, int[] s) {
// 定义两个一维数组dp和g，分别表示在不同的背包容量下，能获得的最大价值和方案数
// dp[j]表示在背包容量为j的情况下，能获得的最大价值
// g[j]表示在背包容量为j且价值为dp[j]的情况下，有多少种方案
int[] dp = new int[V + 1];
int[] g = new int[V + 1];
// 初始化状态，当背包容量为0时，只有一种方案，即什么都不放
dp[0] = g[0] = 1;
// 遍历物品
for (int i = 1; i <= N; i++) {
// 遍历背包容量，从后往前遍历，避免覆盖之前的状态
for (int j = V; j >= v[i]; j--) {
// 遍历物品数量，从1到s[i]，并且满足j-k*v[i]>=0
for (int k = 1; k <= s[i] && j >= k * v[i]; k++) {
// 如果前一个状态有效，即dp[j-k*v[i]]>0
if (dp[j - k * v[i]] > 0) {
// 如果当前状态可以更新为更大的价值，即dp[j-k*v[i]] + k*w[i] > dp[j]
if (dp[j - k * v[i]] + k * w[i] > dp[j]) {
// 更新最大价值
dp[j] = dp[j - k * v[i]] + k * w[i];
// 更新方案数为前一个状态的方案数
g[j] = g[j - k * v[i]];
} else if (dp[j - k * v[i]] + k * w[i] == dp[j]) {
// 如果当前状态可以更新为相同的价值，即dp[j-k*v[i]] + k*w[i] == dp[j]
// 更新方案数为前一个状态的方案数加上当前状态的方案数
g[j] += g[j - k * v[i]];
// 取模防止溢出
g[j] %= MOD;
}
}
}
}
}
// 返回g[V]，即在背包容量为V且价值为dp[V]时，有多少种方案
return g[V];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品种数
int V = sc.nextInt(); // 背包容量
int[] v = new int[N + 1]; // 体积数组
int[] w = new int[N + 1]; // 价值数组
int[] s = new int[N + 1]; // 数量数组
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
sc.close();
// 调用solve方法，传入参数，并打印返回值
System.out.println(solve(N, V, v, w, s));
}
}5.3 练习题三：
题目
有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 si1 + si2 + … + sik = si件，其中每个子类别的物品有 si1, si2, …, sik件（k为正整数），每件体积是 vi1, vi2, …, vik ，价值是 wi1, wi2, …, wik 。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
-
-
输入格式：第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行若干个整数。第 i 行的第一个整数为 k ，表示第 i 种物品的子类别个数；接下来有 k 对整数 (vi1, wi1), (vi2, wi2), …, (vik, wik) ，用空格隔开，分别表示第 i 种物品的各个子类别的体积和价值。
-
输出格式：输出一个整数，表示最大价值。
-
数据范围：0 < N,V ≤1000, k >0 , k ≤1000 , ∑k ≤1000 , 0 < vi,wi ≤1000
-
输入样例：
3 10 2 1 2 2 4 3 3 5 4 6 5 8 2 6 9 7 10
-
输出样例：
25解答练习题三的JAVA实现：
import java.util.Scanner;
public class MultiKnapsack {
// 定义一个独立于main的方法，用于求解多重背包问题
// 参数为物品种数N，背包容量V，体积数组v，价值数组w，数量数组s
// 返回值为最大价值
public static int solve(int N, int V, int[] v, int[] w, int[] s) {
// 定义一个一维数组dp，表示在不同的背包容量下，能获得的最大价值
// dp[j]表示在背包容量为j的情况下，能获得的最大价值
int[] dp = new int[V + 1];
// 遍历物品
for (int i = 1; i <= N; i++) {
// 遍历背包容量，从后往前遍历，避免覆盖之前的状态
for (int j = V; j >= v[i]; j--) {
// 遍历物品数量，从1到s[i]，并且满足j-k*v[i]>=0
for (int k = 1; k <= s[i] && j >= k * v[i]; k++) {
// 状态转移方程：dp[j] = max(dp[j], dp[j-k*v[i]] + k*w[i])
// 表示在背包容量为j时，可以选择放入k个第i种物品或者不放入第i种物品，取两者中的较大值作为最大价值
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
// 返回dp[V]，即在背包容量为V时，能获得的最大价值
return dp[V];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品种数
int V = sc.nextInt(); // 背包容量
int[] v = new int[N + 1]; // 体积数组
int[] w = new int[N + 1]; // 价值数组
int[] s = new int[N + 1]; // 数量数组
for (int i = 1; i <= N; i++) {
int k = sc.nextInt(); // 子类别个数
v[i] = sc.nextInt(); // 第一个子类别的体积
w[i] = sc.nextInt(); // 第一个子类别的价值
s[i] = 1; // 第一个子类别的数量为1
for (int j = 2; j <= k; j++) { // 遍历剩余的子类别
int vi = sc.nextInt(); // 当前子类别的体积
int wi = sc.nextInt(); // 当前子类别的价值
s[i] += vi / v[i]; // 更新第i种物品的总数量，按照第一个子类别的体积为单位
v[i] += vi; // 更新第i种物品的总体积，累加所有子类别的体积
w[i] += wi; // 更新第i种物品的总价值，累加所有子类别的价值
}
}
sc.close();
// 调用solve方法，传入参数，并打印返回值
System.out.println(solve(N, V, v, w, s));
}
}
6. 总结
多重背包问题是一种动态规划问题，它可以用不同的方法来求解，其中最优化的方法是利用二进制的思想将每种物品拆分成若干个01背包中的物品，然后转化为01背包问题来求解。这样可以将时间复杂度降低到O(N*C)。动态规划的核心思想是将问题分解为子问题，并利用子问题的最优解来构造原问题的最优解。动态规划的难点在于找到合适的状态定义和状态转移方程，以及进行空间优化。