AcWing 7. 混合背包问题(Java模板写法,转化为多重背包)
原题链接
中等
作者:
执梗
,
2022-05-14 17:27:46
,
所有人可见
,
阅读 165
import java.util.Scanner;
public class Main {
static int INF = 0x3f3f3f3f;
static int N = 1010;
//背包的体积
static int[] v = new int[N];
//背包的价值
static int[] w = new int[N];
//背包的数量
static int[] a = new int[N];
static int n, m;
//只考虑前i个物品,且背包容积不超过j的最大价值
static int[][] f = new int[N][N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
int c = sc.nextInt();
if (c == -1) {
a[i] = 1;
} else if (c == 0) {
a[i] = INF;
} else {
a[i] = c;
}
}
//转化为二维费用背包问题
for (int i = 1; i <= n; i++) {
//背包容积
for (int j = 0; j <= m; j++) {
//枚举第i个物品选几个
for (int k = 0; k*v[i]<=j&&k<=a[i]; k++) {
f[i][j]=Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
System.out.println(f[n][m]);
}
}