AcWing 8. java-二维费用的背包问题
原题链接
中等
import java.util.Scanner;
public class de {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
//想要进一步提高速度可以io替换scanner
int n=sc.nextInt();
int m=sc.nextInt();
int W=sc.nextInt();
int[][] f=new int[m+1][2];
for (int i = 0; i <n ; i++) {
int v=sc.nextInt();
int w=sc.nextInt();
int value=sc.nextInt();
for (int j = m; j >=0 ; j--) {
if (j>=v&&f[j][0]<f[j-v][0]+value&&f[j-v][1]+w<=W){
//以体积大小为基准,不让重量超过限制 基本上就是比一维背包 多一个判断
f[j][0]=f[j-v][0]+value;
f[j][1]=f[j-v][1]+w;
}
}
}
int t=0;
for (int i = 0; i <=m ; i++) {
t=t>f[i][0]?t:f[i][0];
}
System.out.println(t);
}
}