Hi, this blog is to help you to know about 0/1 knapsack problem and how to solve it using Java.

Problem Definition

Suppose there is a thief who came to steal thing from someone's home. He has a knapsack(shoulder bag) with him with a limit of weight it can carry. So thief wants to maximize his profit by only keeping the things which have more values and also wants to utilize his knapsack efficiently. He is not allowed to break any item i.e. he has to pick any item or he should not pick that item.


For example
Lets say there are three things can be taken by the thief and their weight are 10, 20 and 30 respectively. The value of these elements are 60, 100 and 120 respectively.

The weight capacity of bag is 50. Now the options with thief are to pick 

10 weight item resulting a total weight of 10 and profit of 60 

20 weight item resulting a total weight of 20 and profit of 100 

30 weight item resulting a total weight of 30 and profit of 120 

10, 20 weight items resulting a total weight of 30 and profit of 60 + 100 = 160

10, 30 weight items resulting a total weight of 40 and profit of 60 + 120 =  180

20, 30 weight items resulting a total weight of 50 and profit of 100 + 120 = 220

so the item with weight 20 and 30 should be picked to maximize his profit.

Suppose now the weight capacity of the knapsack is reduced to 30, then he should choose 10, 20 weight items instead of 30 as profit is 160 in this case. 

Here is a dynamic programming approach to solve the above problem

package com.tech.blog;

import java.util.Scanner;

public class ZeroOneKnapsack {

	public void solve(int[] wt, int[] val, int W, int N) {
		int NEGATIVE_INFINITY = Integer.MIN_VALUE;
		int[][] m = new int[N + 1][W + 1];
		int[][] sol = new int[N + 1][W + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j <= W; j++) {
				int m1 = m[i - 1][j];
				int m2 = NEGATIVE_INFINITY;
				if (j >= wt[i])
					m2 = m[i - 1][j - wt[i]] + val[i];
				m[i][j] = Math.max(m1, m2);
				sol[i][j] = m2 > m1 ? 1 : 0;
			}
		}
		int[] selected = new int[N + 1];
		for (int n = N, w = W; n > 0; n--) {
			if (sol[n][w] != 0) {
				selected[n] = 1;
				w = w - wt[n];
			} else
				selected[n] = 0;
		}
		System.out.print("\nItems with weight ");
		for (int i = 1; i < N + 1; i++)
			if (selected[i] == 1)
				System.out.print(wt[i] + " ");
		System.out.println("are selected by knapsack algorithm.");
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ZeroOneKnapsack zeroOneKP = new ZeroOneKnapsack();

		System.out.println("Enter number of elements ");
		int n = sc.nextInt();

		int[] wt = new int[n + 1];
		int[] val = new int[n + 1];

		System.out.println("Enter weight for " + n + " elements");
		for (int i = 1; i <= n; i++)
			wt[i] = sc.nextInt();
		System.out.println("Enter value for " + n + " elements");
		for (int i = 1; i <= n; i++)
			val[i] = sc.nextInt();

		System.out.println("Enter knapsack weight ");
		int W = sc.nextInt();

		zeroOneKP.solve(wt, val, W, n);
		sc.close();
	}

}

Output for the above problem is

Enter number of elements 
3
Enter weight for 3 elements
10 20 30
Enter value for 3 elements
60 100 120
Enter knapsack weight 
50

Items with weight 20 30 are selected by knapsack algorithm.

Enter number of elements 
3
Enter weight for 3 elements
10 20 30
Enter value for 3 elements
60 100 120
Enter knapsack weight 
30

Items with weight 10 20 are selected by knapsack algorithm.