题目描述
blablabla
样例
import java.util.*;
import java.io.*;
class Main{
static final int N = 1010;
static int f[][] = new int [N][N]; //保存所有集合的最值状态
static int v[] = new int[N];
static int w[] = new int[N];
public static void main(String args[])throws IOException{
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
String arr[] = bfr.readLine().split(" ");
int n = Integer.parseInt(arr[0]);
int m = Integer.parseInt(arr[1]);
//读取操作数据;
for(int i = 1;i <=n;i++){
String arr1[] = bfr.readLine().split(" ");
v[i] = Integer.parseInt(arr1[0]);
w[i] = Integer.parseInt(arr1[1]);
}
//集合的划分;
for(int i = 1; i <= n;i++ ) //y因为下面是i-1所以要从 i= 1开始
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][j], f[i-1][j-v[i]] + w[i]);
}
System.out.println(f[n][m]);
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla