AcWing 2. 01背包问题
原题链接
简单
作者:
乾巧
,
2024-04-07 11:40:57
,
所有人可见
,
阅读 1
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=1010;
int n=sc.nextInt();
int V=sc.nextInt();
int[] v=new int[N];
int[] w=new int[N];
int[][] f=new int[N][N];//前 i个物品,背包容量 j下的最优解
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=0;j<=V;j++){
f[i][j]=f[i-1][j];//不包含i
if(j>=v[i]){
f[i][j]=Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
}
System.out.print(f[n][V]);
}
}