-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBagProblem.java
More file actions
130 lines (75 loc) · 1.81 KB
/
BagProblem.java
File metadata and controls
130 lines (75 loc) · 1.81 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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class BagProblem{
public static int bag1(int[] w,int[] v,int rest){
return process1(w,v,0,rest);
}
public static int process1(int[] w,int[] v,int index,int rest){
if(rest < 0){
return -1;
}
if(index == v.length){
return 0;
}
int p1 = process1(w,v,index+1,rest);
int p2 = 0;
int next = process1(w,v,index+1,rest-w[index]);
if(next!=-1){
p2 = v[index]+next;
}
return Math.max(p1,p2);
}
public static int bag2(int[] w,int[] v,int rest){
int[][] dp=new int[v.length+1][rest+1];
for (int i=0; i<dp.length; i++) {
for (int j=0; j<dp[0].length; j++) {
dp[i][j]=-1;
}
}
return process2(w,v,0,rest,dp);
}
public static int process2(int[] w,int[] v,int index,int rest,int[][] dp){
if(rest < 0){
return -1;
}
if(dp[index][rest]!=-1){
return dp[index][rest];
}
if(index == v.length){
return 0;
}
int ans=0;
int p1 = process2(w,v,index+1,rest,dp);
int p2 = 0;
int next = process2(w,v,index+1,rest-w[index],dp);
if(next!=-1){
p2 = v[index]+next;
}
ans= Math.max(p1,p2);
dp[index][rest]=ans;
return ans;
}
public static int bag3(int[] w,int[] v,int bag){
int[][] dp=new int[v.length+1][bag+1];
int N = v.length;
int M = bag;
for (int index=N-1; index>=0;index-- ) {
for (int rest=M; rest>=0;rest-- ) {
int p1 = dp[index+1][rest];
int p2 = 0;
int next = rest-w[index]>=0?dp[index+1][rest-w[index]]:-1;
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[] w=new int[]{1,2,3,4,5};
int[] v=new int[]{9,2,14,12,10};
int bag=12;
System.out.println("v = "+bag1(w,v,bag));
System.out.println("v2 = "+bag2(w,v,bag));
System.out.println("v3 = "+bag3(w,v,bag));
}
}