AcWing 3. 完全背包问题
原题链接
简单
作者:
空指针异常
,
2021-02-03 16:05:07
,
所有人可见
,
阅读 179
二维空间
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int N = 1010, M = 1010;
int f[][] = new int[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][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;
int f[] = new int[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 = v; j <= m; j++) {
f[j] = Math.max(f[j], f[j - v] + w);
}
}
System.out.println(f[m]);
}
}