题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
java 代码
blablabla
import java.io.;
import java.util.;
import java.math.*;
public class Main{
static int N=1010;
static int f[][]=new int[N][N];
static int v[]=new int[N];
static int mass[]=new int[N];
static int w[]=new int[N];
public static void main(String[]args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[]first_line=br.readLine().split(” “);
int n=Integer.parseInt(first_line[0]);
int m=Integer.parseInt(first_line[1]);
int o=Integer.parseInt(first_line[2]);
for(int i=1;i<=n;i++){
String[]line=br.readLine().split(” “);
v[i]=Integer.parseInt(line[0]);
mass[i]=Integer.parseInt(line[1]);
w[i]=Integer.parseInt(line[2]);
}
for(int i=1;i<=n;i++){
// 这里是从大到小来的,
// 之前错误的是没有先全部把数据读进来,导致最后一个数据没有
for(int j=m;j>=v[i];j--){
for(int k=o;k>=mass[i];k--){
f[j][k] = Math.max(f[j][k], f[j-v[i]][k-mass[i]] + w[i]);
}
}
}
System.out.print(f[m][o]);
}
}
// f(i,j,k) 从前i个物品里面选,总体积不超过v并且重重量不超过k
// f(i-1,j,k)第一类,不选第i个物品
// f(i-1,j-v,k-mass)+w 选第i个物品