AcWing 3. java
原题链接
简单
作者:
季之秋
,
2021-02-08 17:54:04
,
所有人可见
,
阅读 229
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int N=1010;
int v[]=new int[N];
int w[]=new int[N];
int f[]=new int[N];
for(int i=1;i<=n;i++) {
v[i]=sc.nextInt();
w[i]=sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
//f[i][j]=f[i-1][j]; 单独操作就是二维里都是一样的一维数组,那一个一位数组可以代表了
f[j]=Math.max(f[j],f[j-v[i]]+w[i]);
//if(j>=v[i]) f[i][j]=Math.max(f[i-1][j],f[i][j-v[i]]+w[i]);
//因为f[i][j]先更新 所以f[i][j-v[i]]和f[i][j]都是同一层(同一循环)的数据
//所以可以拿一维的数代替,意义相同,都是同一层的数据更新max
}
}
System.out.println(f[m]);
}
}