-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathKnapsack.java
40 lines (31 loc) · 835 Bytes
/
Knapsack.java
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
import static sun.swing.MenuItemLayoutHelper.max;
public class Knapsack {
void knapsack(int W,int n,int wt[],int val[]){
int i,j;
int V[][] = new int[n+1][W+1];
for ( i=0;i<W;i++){
V[0][i]=0;
}
for (j=0;j<n;j++){
V[j][0] =0;
}
for (i=1;i<n;i++){
for (j=1;j<=W;j++){
if (wt[i]<j){
V[i][j] = max(V[i-1][W],val[i]+V[i-1][j- wt[i]]);
}
else {
V[i][j] = V[i-1][j];
}
}
}
System.out.println("Max Profit "+ V[n][W]);
}
public static void main(String[] args) {
int n = 4,W=8;
int val[]={-1,1,2,5,6};
int wt[] ={-1,2,3,4,5};
Knapsack k =new Knapsack();
k.knapsack(W,n,wt,val);
}
}