从二维优化为一维
体积从大枚举到小
import java.util.*;
public class Main {
static int N = 1000 + 10;
static int[] f = new int[N];
static int[] v = new int[N];
static int[] w = new int[N];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
// f[0][0~m] = 0; 无需初始化
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; 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]);
}
}