AcWing 8. 二维费用的背包问题-java
原题链接
中等
作者:
单箭头
,
2019-05-11 16:51:18
,
所有人可见
,
阅读 1790
java 代码
package com.company.ForTruth.ali.背包问题;
import java.util.Scanner;
/**
* Author: hszzjs
* Date: 2019/5/10 19:49
* E-mail: hushaozhe@stu.xidian.edu.cn
* 题目描述:
* 有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。
求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。输出最大价值。
输入格式
第一行两个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例:
8
*/
public class 二维费用背包 {
/**
* 这个就是增加了一维的01背包。
*/
static class Good{
int v,m,w;
public Good(int v,int m,int w){
this.v=v;
this.m=m;
this.w=w;
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt(),V=sc.nextInt(),M=sc.nextInt();
Good[] goods=new Good[N];
for(int i=0;i<N;i++){
goods[i]=new Good(sc.nextInt(),sc.nextInt(),sc.nextInt());
}
int[][][] res=new int[N+1][V+1][M+1];
for(int i=1;i<=N;i++){
for(int j=V;j>0;j--){
for(int k=M;k>0;k--){
if(goods[i-1].v>j||goods[i-1].m>k) res[i][j][k]=res[i-1][j][k];
else res[i][j][k]=Math.max(res[i-1][j][k],res[i-1][j-goods[i-1].v][k-goods[i-1].m]+goods[i-1].w);
}
}
}
System.out.println(res[N][V][M]);
}
}