AcWing 2. 01背包问题
原题链接
简单
作者:
季之秋
,
2021-02-08 16:48:37
,
所有人可见
,
阅读 233
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 v[]=new int[1010];
int w[]=new int[1010];
int f[]=new int[1010];
for(int i=1;i<=n;i++){
v[i]=sc.nextInt();
w[i]=sc.nextInt();
}
for(int i=1;i<=n;i++){//i取0=0,无意义,所以取i可以取到的值
for(int j=m;j>=v[i];j--){ //从大到小更新,一维滚动数组
//只有计算公式两层的联系时,上一层的数就是这一层还没更新的数
//f[i][j]=Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
f[j]=Math.max(f[j],f[j-v[i]]+w[i]);//f[j]在f[j-v[i]]前更新,所以需要从大到小更新
}
}
System.out.println(f[m]);
}
}