AcWing 2. 01背包问题JAVA版题解
原题链接
简单
作者:
巴韭特
,
2021-05-19 19:27:46
,
所有人可见
,
阅读 2
Java版原始题解
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int V = scan.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = scan.nextInt();
w[i] = scan.nextInt();
}
int[][]dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i-1][j];
if ( j >= v[i]) {
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]] + w[i]);
}
}
}
System.out.println(dp[N][V]);
}
}
优化成1维的版本
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
int V = scan.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++) {
v[i] = scan.nextInt();
w[i] = scan.nextInt();
}
int[]dp = new int[V + 1];
for (int i = 0; i < N; i++) {
//逆序遍历
for (int j = V; j >= v[i]; j--) {
dp[j] = Math.max(dp[j],dp[j-v[i]] + w[i]);
}
}
System.out.println(dp[V]);
}
}