forked from algorithmzuo/algorithmbasic2020
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode01_Knapsack.java
More file actions
63 lines (57 loc) · 1.6 KB
/
Code01_Knapsack.java
File metadata and controls
63 lines (57 loc) · 1.6 KB
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
package class19;
public class Code01_Knapsack {
// 所有的货，重量和价值，都在w和v数组里
// 为了方便，其中没有负数
// bag背包容量，不能超过这个载重
// 返回：不超重的情况下，能够得到的最大价值
public static int maxValue(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
// 尝试函数！
return process(w, v, 0, bag);
}
// index 0~N
// rest 负~bag
public static int process(int[] w, int[] v, int index, int rest) {
if (rest < 0) {
return -1;
}
if (index == w.length) {
return 0;
}
int p1 = process(w, v, index + 1, rest);
int p2 = 0;
int next = process(w, v, index + 1, rest - w[index]);
if (next != -1) {
p2 = v[index] + next;
}
return Math.max(p1, p2);
}
public static int dp(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= bag; rest++) {
int p1 = dp[index + 1][rest];
int p2 = 0;
int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
if (next != -1) {
p2 = v[index] + next;
}
dp[index][rest] = Math.max(p1, p2);
}
}
return dp[0][bag];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
int[] values = { 5, 6, 3, 19, 12, 4, 2 };
int bag = 15;
System.out.println(maxValue(weights, values, bag));
System.out.println(dp(weights, values, bag));
}
}