AcWing 2. 01背包问题
原题链接
简单
作者:
空指针异常
,
2021-02-03 15:46:25
,
所有人可见
,
阅读 197
二维空间
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int N = 1010, M = 1010;
long f[][] = new long[N][M];
int V = 1010, W = 1010;
int v[] = new int[V];
int w[] = new int[W];
Scanner scanner = new Scanner(System.in);
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
for (int j = 0; j <= m; j++) {
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
System.out.println(f[n][m]);
}
}
一维空间
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int N = 1010, M = 1010;
long f[] = new long[M];
int V = 1010, W = 1010;
int v, w;
Scanner scanner = new Scanner(System.in);
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
f[0] = 0;
for (int i = 1; i <= n; i++) {
v = scanner.nextInt();
w = scanner.nextInt();
for (int j = m; j >= v; j--) {
f[j] = Math.max(f[j], f[j - v] + w);
}
}
System.out.println(f[m]);
}
}