AcWing 4. 多重背包问题 I
原题链接
简单
作者:
空指针异常
,
2021-02-03 16:25:37
,
所有人可见
,
阅读 177
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int N = 1010, M = 1010;
int f[] = new int[M];
int V = 1010, W = 1010;
int v, w, s;
Scanner scanner = new Scanner(System.in);
int n, m;
n = scanner.nextInt();
m = scanner.nextInt();
f[0] = 0;
for (int i = 1; i <= n; i++) {
v = scanner.nextInt();
w = scanner.nextInt();
s = scanner.nextInt();
for (int j = m; j >= v; j--) {
for(int k =1;k<=s&&k*v<=j;k++)
f[j] = Math.max(f[j], f[j - k*v] + k*w);
}
}
System.out.println(f[m]);
}
}