FilesExpand file tree

 master

/

Knapsack.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (32 loc) · 783 Bytes

 master

/

Knapsack.java

Copy path

Top

File metadata and controls

• Code
• Blame

38 lines (32 loc) · 783 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

// A Dynamic Programming based solution for 0-1 Knapsack problem

public class Knapsack

{

private static int knapSack(int W, int wt[], int val[], int n)

{

int i, w;

int rv[][] = new int[n+1][W+1]; //rv means return value

// Build table rv[][] in bottom up manner

for (i = 0; i <= n; i++)

{

for (w = 0; w <= W; w++)

{

if (i==0 || w==0)

rv[i][w] = 0;

else if (wt[i-1] <= w)

rv[i][w] = Math.max(val[i-1] + rv[i-1][w-wt[i-1]], rv[i-1][w]);

else

rv[i][w] = rv[i-1][w];

}

}

return rv[n][W];

}

// Driver program to test above function

public static void main(String args[])

{

int val[] = new int[]{50, 100, 130};

int wt[] = new int[]{10, 20, 40};

int W = 50;

int n = val.length;

System.out.println(knapSack(W, wt, val, n));

}

}