# Java Program to Solve the 0-1 Knapsack Problem

This is java program to implement 0/1 Knapsack problem. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Here is the source code of the Java Program to Solve the 0-1 Knapsack Problem. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

1. `//This is a sample program to implement a 0/1 knapsack algorithm `
2. `import java.util.Scanner;`
3. ` `
4. `public class Zero_One_Knapsack`
5. `{`
6. `    public void solve(int[] wt, int[] val, int W, int N)`
7. `    {`
8. `        int NEGATIVE_INFINITY = Integer.MIN_VALUE;`
9. `        int[][] m = new int[N + 1][W + 1];`
10. `        int[][] sol = new int[N + 1][W + 1];`
11. `        for (int i = 1; i <= N; i++)`
12. `        {`
13. `            for (int j = 0; j <= W; j++)`
14. `            {`
15. `                int m1 = m[i - 1][j];`
16. `                int m2 = NEGATIVE_INFINITY; `
17. `                if (j >= wt[i])`
18. `                    m2 = m[i - 1][j - wt[i]] + val[i];`
19. `                m[i][j] = Math.max(m1, m2);`
20. `                sol[i][j] = m2 > m1 ? 1 : 0;`
21. `            }`
22. `        }        `
23. `        int[] selected = new int[N + 1];`
24. `        for (int n = N, w = W; n > 0; n--)`
25. `        {`
26. `            if (sol[n][w] != 0)`
27. `            {`
28. `                selected[n] = 1;`
29. `                w = w - wt[n];`
30. `            }`
31. `            else`
32. `                selected[n] = 0;`
33. `        }`
34. `        System.out.print("\nItems with weight ");`
35. `        for (int i = 1; i < N + 1; i++)`
36. `            if (selected[i] == 1)`
37. `                System.out.print(val[i] +" ");`
38. `        System.out.println("are selected by knapsack algorithm.");`
39. `    }`
40. `    public static void main (String[] args) `
41. `    {`
42. `        Scanner scan = new Scanner(System.in);`
43. `        Zero_One_Knapsack ks = new Zero_One_Knapsack();`
44. ` `
45. `        System.out.println("Enter number of elements ");`
46. `        int n = scan.nextInt();`
47. ` `
48. `        int[] wt = new int[n + 1];`
49. `        int[] val = new int[n + 1];`
50. ` `
51. `        System.out.println("Enter weight for "+ n +" elements");`
52. `        for (int i = 1; i <= n; i++)`
53. `            wt[i] = scan.nextInt();`
54. `        System.out.println("Enter value for "+ n +" elements");`
55. `        for (int i = 1; i <= n; i++)`
56. `            val[i] = scan.nextInt();`
57. ` `
58. `        System.out.println("Enter knapsack weight ");`
59. `        int W = scan.nextInt();`
60. ` `
61. `        ks.solve(wt, val, W, n);`
62. `        scan.close();`
63. `    }`
64. `}`

Output:

```\$ javac Zero_One_Knapsack.java
\$ java Zero_One_Knapsack

Enter number of elements
5
Enter weight for 5 elements
01 56 42 78 12
Enter value for 5 elements
50 30 20 10 50
Enter knapsack weight
150

Items with weight 50 30 20 50 are selected by knapsack algorithm.```

Sanfoundry Global Education & Learning Series – 1000 Java Programs.