AcWing 426. 二维dp+滚动数组一维优化-Java
原题链接
简单
作者:
zlnnjit
,
2021-02-09 11:35:25
,
所有人可见
,
阅读 421
解法一:二维dp
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//m:总价钱 n:物品个数
int m = sc.nextInt(), n = sc.nextInt();
//定义dp[i][j]:从1~i选且总价值不超过j的所有选法集合的最大值
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
//v:当前物品的价值 p:当前物品的度
int v = sc.nextInt(), p = sc.nextInt();
int w = v * p;
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v] + w);
}
}
}
System.out.println(dp[n][m]);
}
}
一维dp转换(注意恒等变形)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//m:总价钱 n:物品个数
int m = sc.nextInt(), n = sc.nextInt();
//定义dp[i][j]:从1~i选且总价值补不超过的所有选法集合的最大值
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {
//v:当前物品的价值 p:当前物品的度
int v = sc.nextInt(), p = sc.nextInt();
int w = v * p;
for (int j = m; j >= 1; j--) {
if (j >= v) {
dp[j] = Math.max(dp[j], dp[j - v] + w);
}
}
}
System.out.println(dp[m]);
}
}