计算过程如下
朴素版代码
import java.util.Scanner;
import java.io.*;
public class Main {
static int N = 1010;
static int[] v = new int[N];
static int[] w = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
// i = 0 时表示取前 0 个物品,即不取物品,所以总价值都为 0
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
// 不包含 i 的方案
f[i][j] = f[i - 1][j];
// 包含 i 的方案,只有 vi ≤ j 时才会选择
if (v[i] <= j) {
// 取两个方案中的最大值
f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
System.out.println(f[n][m]);
sc.close();
}
}
优化
仔细分析状态变换过程可以发现,计算 f[i, j] 时只会用到 f[i - 1, j],不需要存储 f[0 ~ i-2, j] 的值。
并且 f(i, j) = Math.max(f(i - 1, j), f(i - 1, j - v[i] + w[i])
中,第二维 j 的值只与 j 与 j - v[i] 有关,而 j = j
j - v[i] < j
,都严格 ≤ j,因此可以将第一维 i 删去,用一维滚动数组来存储中间值。
等价转换
将运算过程删去第 i 维后得到以下代码
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
f[j] = f[j];
if (j >= v[i]) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
}
System.out.println(f[m]);
我们可以发现 f[j] = f[j]
是恒等式,直接删除。
j >= v[i]
的判断可以放进 j 的循环中,所以再改进如下
for (int i = 1; i <= n; i ++) {
for (int j = v[i]; j <= m; j ++) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
问题
此时 f 数组由于节省空间更改为滚动数组,所以运算 i = 1 时需要用到 i = 0 时 f 数组的结果,运算 i = 2 时需要用到 i = 1 时 f 数组的结果。
这就要求在运算 Math.max(f[j], f[j - v[i]] + w[i])
时,读取到的 f 数组里的数据必须全部是上一个 i 运算的结果。
但是由于 j 是递增的,而 j - v[i]
又严格小于 j,因此如果 f[j]
被修改,下一次读取的 f[j - v[i]]
的数据就是最新修改后的值。比如:
当 i = 1 时,我们使用的应是 i = 0 时 f 数组的数据,j 开始循环
j = 1:f[1] = Math.max(f[1], f[0] + w[1]) = Math.max(0, 0 + 2) = 2
j = 2:f[2] = Math.max(f[2], f[1] + w[1]) = Math.max(0, 2 + 2) = 4
…
此时由于 f[1] 先被修改,所以导致 j = 2 时使用的 f[1] 就是修改后的值,但我们本来只想读取 i = 0 时 f[1] 的值,出现矛盾。
如何解决
Math.max(f[j], f[j - v[i]] + w[i])
是我们运算的根基,不要轻易修改。只需要保证 f[j - v[i]]
在使用时一定是原值即可。
所以将 j 递减循环,即可保证每一次读取的 f[j - v[i]]
都是更新前的值,完美解决该问题。比如:
当 i = 1 时,我们使用的应是 i = 0 时 f 数组的数据,j 开始循环
j = 5:f[5] = Math.max(f[5], f[4] + w[1]) = Math.max(0, 0 + 2) = 2
j = 4:f[4] = Math.max(f[4], f[3] + w[1]) = Math.max(0, 0 + 2) = 2
…
可以发现求 f[5] 时读取的 f[5] 和 f[4] 都是上一轮计算的结果,即使本次循环更新后,求 f[4] 时也不会用到,问题解决。 代码修改如下:
for (int i = 1; i <= n; i ++) {
for (int j = m; j >= v[i]; j --) {
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
优化版完整代码
import java.util.Scanner;
import java.io.*;
public class Main {
static int N = 1010;
static int[] v = new int[N];
static int[] w = new int[N];
static int[] f = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i ++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
// i = 0 时表示取前 0 个物品,即不取物品,所以总价值都为 0
for (int i = 1; i <= n; i ++) {
for (int j = m; j >= v[i]; j --) {
// 取两个方案中的最大值
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
sc.close();
}
}