AcWing 8. 二维费用的背包问题—Java实现
原题链接
中等
作者:
FUZZ
,
2019-08-25 17:21:11
,
所有人可见
,
阅读 1105
Java 代码
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 物品总数
int V = sc.nextInt(); // 背包容量
int M = sc.nextInt(); // 背包承重
int[][] dp = new int[V + 1][M + 1];
for(int i = 0; i < N; i++){
int vi = sc.nextInt(); // 体积
int mi = sc.nextInt(); // 重量
int wi = sc.nextInt(); // 价值
for(int j = V; j >= vi; j--){
for(int k = M; k >= mi; k--){
dp[j][k] = Math.max(dp[j][k], dp[j - vi][k - mi] + wi);
}
}
}
System.out.println(dp[V][M]);
}
}