混合背包问题
有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
−1≤si≤1000
来源acwing
对于每一种情况，有不同的解决方式，如果再把多重背包给拆分，那么就只剩两种情况。沿用了上一题的代码。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| import java.util.*;
public class Main {
public static int solve(int N,int V,int[] v,int[] w,int[] s,ArrayList<Integer> listv,ArrayList<Integer> listw) {
int[] dp = new int[V + 1];
for (int i = 0; i < listv.size(); i++) {
if (listw.get(i) < 0) {
for (int j = 0; j <= V; j++) {
if (j >= listv.get(i))
dp[j] = Math.max(dp[j], dp[j - listv.get(i)] - listw.get(i));
}
}
else {
for (int j = V; j >= listv.get(i); j--) {
dp[j] = Math.max(dp[j],dp[j - listv.get(i)] + listw.get(i));
}
}
}
return dp[dp.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[] v = new int[N + 1];
int[] w = new int[N + 1];
int[] s = new int[N + 1];
ArrayList<Integer> listv = new ArrayList<>(1001);
ArrayList<Integer> listw = new ArrayList<>(1001);
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
if (s[i] > 0) {
for (int j = 1; j <= s[i]; j *= 2) {
s[i] -= j;
listv.add(v[i] * j);
listw.add(w[i] * j);
}
if (s[i] > 0) {
listv.add(v[i] * s[i]);
listw.add(w[i] * s[i]);
}
} else {
int p = 1;
if (s[i] == 0) p = -1;
listv.add(v[i]);
listw.add(w[i]* p);
}
}
System.out.println(solve(N,V,v,w,s,listv,listw));
}
}
|
把前面的三种背包弄明白，其实主要是01和完全背包，因为多重背包就是01，这道题很好写。