题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.Scanner;
class Main{
public static void main(String[] args) {
// 转移方程为dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + v[i - 1] * p[i - 1]);
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), m = sc.nextInt();
int[] v = new int[m], p = new int[m];
for (int i = 0; i < m; i++) {
v[i] = sc.nextInt();
p[i] = sc.nextInt();
}
int[][] dp = new int[m + 1][N + 1];
for (int i = 1; i <= m; i++) {
for (int j = N; j > 0; j--) { // 这里是j--
dp[i][j] = dp[i - 1][j];
if (j >= v[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i - 1]] + v[i - 1] * p[i - 1]);
}
}
}
int res = 0;
for (int i = 1; i <= N; i++) res = Math.max(dp[m][i], res);
System.out.print(res);
}
}