AcWing 4. 多重背包问题 I
原题链接
简单
作者:
lyxcqupt
,
2024-03-18 10:08:25
,
所有人可见
,
阅读 9
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int n,m;
static final int N = 110;
static int[] v = new int[N];
static int[] w = new int[N];
static int[] s = new int[N];
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i++){
v[i] = scan.nextInt();
w[i] = scan.nextInt();
s[i] = scan.nextInt();
}
for(int i = 1;i <= n;i++){
for(int j = 0;j <= m;j++){
for(int k = 0;k * v[i] <= j && k <= s[i];k++){
f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]*k] + w[i] * k);
}
}
}
System.out.println(f[n][m]);
scan.close();
}
}