二维背包
有 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
和前面的区别在于限制量有两个：体积和重量。有了前面的铺垫，这道题应该好想，就是把一维dp数组变为二维，别的地方都不变。二维费用的背包问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| import java.util.*;
public class Main {
public static int solve(int N,int V,int M,int[] v,int[] m,int[] w) {
int[][] dp = new int[V + 1][M + 1];
for (int i = 0; i <= N; i++) {
for (int j = V; j >= v[i]; j--) {
for(int k = M; k >= m[i]; k--) {
dp[j][k] = Math.max(dp[j][k],dp[j - v[i]][k - m[i]] + w[i]);
}
}
}
return dp[dp.length - 1][dp[0].length - 1];
}
public static void show(int[] arr) {
for (int i = 0; i <arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println("*");
}
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[] v = new int[N + 1];
int[] m = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
m[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(solve(N,V,M,v,m,w));
}
}
|