题目描述
仅供参考
样例
二维
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int [][] arr = new int[m+1][m+1];
for (int i = 1; i <= m; i++) {
String[] s1 = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(s1[0]);
arr[i][1] = Integer.parseInt(s1[1]);
}
int [][] f = new int[m+1][n+1];
for(int i = 1;i<=m;i++){
for(int j = 0;j<=n;j++){
f[i][j] = f[i-1][j];
if (j>=arr[i][0]){
f[i][j] = Math.max(f[i][j],f[i-1][j-arr[i][0]] + arr[i][0] * arr[i][1]);
}
}
}
System.out.println(f[m][n]);
}
}
一维
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int [][] arr = new int[m+1][m+1];
int [] f = new int[n+1];
for (int i = 1; i <= m; i++) {
String[] s1 = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(s1[0]);
arr[i][1] = Integer.parseInt(s1[1]);
arr[i][1]*=arr[i][0];
for(int j = n;j>=arr[i][0] ; j--){
f[j] = Math.max(f[j], f[j - arr[i][0]] + arr[i][1]);
}
}
System.out.println(f[n]);
}
}