0-1 Knapsack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W.

You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Example

# Input
val[] = {60, 100, 120}
wt[] = {10, 20, 30}
W = 50

# Output
220

# Explanation
Choose the 2nd and 3rd item having weight 20 and 30. The total value we can obtain is (100+120 = 220). That is the max we can obtain.

Problem Identification

Whenever you encounter any algorithmic problem, try to identify patterns in the problem statement to see if you can solve this with any known approaches.

Looking at the problem statement, we can notice two things

We have choices - Either include an item in the knapsack or don’t.
It’s an optimization problem - Find maximum total value.

This clues might hint you towards a dynamic programming solution. But don’t just make your mind yet. For a dynamic programming solution, we need the following things -

Can the problem be represented using recursion? In other words, can we breakdown the problem into smaller subproblems and represent the solution to the problem using the solutions to its subproblems. This is the first thing you should think about. Because dynamic programming is nothing but an Optimized Recursion. We just remember the solutions to the problems we have already solved so that we don’t solve them again.
Are there overlapping subproblems? If the subproblems don’t overlap then dynamic programming can’t be applied. We can determine if subproblems overlap by building a simple recursion tree.

Allright! So let’s try and see if we can come up with a recursive solution to our problem.

Recursive Solution

The first thing we can do whenever we have choices is build a simple choice diagram like this

Given item1 with weight w1, we have two options

     [item1, w1]
     /      \  
w1 > W      w1 <= W

if w1 > W; We can’t include this item in the Knapsack. We don’t have a choice
if w1 <= W; We have a choice to either include it in knapsack or leave it. Whichever choice gives us the optimal result will be chosen.

Let’s now try to devise a recursive structure for our problem. Let’s say that Knapsack(W, n) is the maximum total value that can be obtained with knapsack weight W using items from 1..n.

Recursive structure

For every item, we have two choices - either include this item in the knapsack or don’t. So the Maximum value that can be obtained from n items with total weight of W is the max of the two choices:

Maximum value obtained from n-1 items and W weight (Excluding the nth item)
Value of the nth item plus the maximum value that can be obtained from n-1 items and W-wt[n] weight (Including the nth item)

If the weight of the nth item is greater than W, then the nth item cannot be included and choice 1 is the only possibility. Let’s write this mathematically:

Knapsack(W, n) = Knapsack(W, n-1); if wt[n] > W
Knapsack(W, n) = max(Knapsack(W, n-1), Knapsack(W - wt[n], n-1) + val[n]); if wt[n] <= W

Base condition

To identify the base condition of recursion, think about the smallest valid input (Empty value array or Zero weight)

Knapsack(W, 0) = 0; for any value of W // No items so max value obtained is 0
Knapsack(0, n) = 0; for any value of n // Knapsack capacity is 0 so we can't pick any item, hence max value obtained is 0.

Allright! Let’s now write the code for our recursive solution

import java.util.Scanner;

class KnapsackRecursion {
	private static int findMaxValue(int[] values, int[] weights, int W, int n) {
		if (W == 0 || n == 0) {
			return 0;
		}

		if (weights[n - 1] > W) {
			return findMaxValue(values, weights, W, n - 1);
		}

		return Math.max(findMaxValue(values, weights, W - weights[n - 1], n - 1) + values[n - 1],
		findMaxValue(values, weights, W, n - 1));
	}

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

		int n = keyboard.nextInt();
		int[] values = new int[n];
		int[] weights = new int[n];

		for (int i = 0; i < n; i++) {
			values[i] = keyboard.nextInt();
		}

		for (int i = 0; i < n; i++) {
			weights[i] = keyboard.nextInt();
		}

		int W = keyboard.nextInt();

		keyboard.close();

		System.out.printf("Max value of Knapsack = %d%n", findMaxValue(values, weights, W, n));
	}
}

$ javac KnapsackRecursion.java
$ java KnapsackRecursion
3
60 100 120
10 20 30
50
Max value of Knapsack = 220

Time Complexity: O(2^n) , Exponential. Learn how to do time complexity analysis for recursive functions

Space Complexity: O(1), no additional space reserved. Only Stack space is used in recursion.

Method 2: Dynamic Programming Top down solution (Memoization)

If you look closely at the recursive structure of the solution, you will notice that we’re doing repetitive calculation for smaller subproblems.

val[] = {60, 100, 120}
wt[] = {10, 25, 25}
W = 50

             KP(50, 3)
          /            \
  KP(50, 2)            KP(25, 2)
  /       \            /       \
KP(50, 1) KP(25, 1)  KP(25, 1)  KP(0, 1)

Let’s see how we can memoize the solution to subproblems so that we don’t have to compute them again and again.

import java.util.Scanner;

class KnapsackTopDownMemoization {
	private static int[][] KPMem;

	private static int findMaxValueRecur(int[] values, int[] weights, int W, int n) {
		if (W == 0 || n == 0) {
			return 0;
		}

		if (KPMem[W][n] != -1) {
			return KPMem[W][n];
		}

		if (weights[n - 1] > W) {
			KPMem[W][n] = findMaxValueRecur(values, weights, W, n - 1);
		} else {
			KPMem[W][n] = Math.max(
				findMaxValueRecur(values, weights, W - weights[n - 1], n - 1) + values[n - 1],
				findMaxValueRecur(values, weights, W, n - 1));
		}

		return KPMem[W][n];
	}

	// Only Memoize variables that change in a recursive call
	private static int findMaxValueMemoized(int[] values, int[] weights, int W, int n) {
		KPMem = new int[W + 1][n + 1];
		for (int w = 0; w <= W; w++) {
			for (int i = 0; i <= n; i++) {
				KPMem[w][i] = -1;
			}
		}
		return findMaxValueRecur(values, weights, W, n);
	}

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

		int n = keyboard.nextInt();
		int[] values = new int[n];
		int[] weights = new int[n];

		for (int i = 0; i < n; i++) {
			values[i] = keyboard.nextInt();
		}

		for (int i = 0; i < n; i++) {
			weights[i] = keyboard.nextInt();
		}

		int W = keyboard.nextInt();

		keyboard.close();

		System.out.printf("Max value of Knapsack = %d%n", findMaxValueMemoized(values, weights, W, n));
	}
}

$ javac KnapsackTopDownMemoization.java
$ java KnapsackTopDownMemoization
3
60 100 120
10 20 30
50
Max value of Knapsack = 220

Time Complexity: O(W*n), For every weight, we calculate the max value obtainable using all the items. And we avoid repeated calculations.

Space Complexity: O(W*n), to store the memoized solutions.

Method 3: Dynamic Programming Bottom up solution

Now let’s convert the memoized dynamic programming solution to a bottom up solution. Bottom up solution of a dynamic programming problem is similar to top-down solution in the sense that we do remember the solutions to subproblems that are already computed. The only difference is that we try to compute the solutions to subproblems first and then construct the solution to the bigger problem using the solution to the subproblems.

import java.util.Scanner;

class KnapsackBottomUp {
	private static int findMaxValue(int[] values, int[] weights, int W) {
		int[][] KP = new int[W + 1][values.length + 1];

		for (int i = 1; i <= W; i++) {
			for (int j = 1; j <= values.length; j++) {
				if (i - weights[j - 1] >= 0) {
					KP[i][j] = Math.max(KP[i - weights[j - 1]][j - 1] + values[j - 1], KP[i][j - 1]);
				} else {
					KP[i][j] = KP[i][j - 1];
				}
			}
		}

		return KP[W][values.length];
	}

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

		int n = keyboard.nextInt();
		int[] values = new int[n];
		int[] weights = new int[n];

		for (int i = 0; i < n; i++) {
			values[i] = keyboard.nextInt();
		}

		for (int i = 0; i < n; i++) {
			weights[i] = keyboard.nextInt();
		}

		int W = keyboard.nextInt();

		keyboard.close();

		System.out.printf("Max value of Knapsack = %d%n", findMaxValue(values, weights, W));
	}
}

$ javac KnapsackBottomUp.java
$ java KnapsackBottomUp
3
60 100 120
10 20 30
50
Max value of Knapsack = 220

Time Complexity: O(W*n), For the two for loops.

Space Complexity: O(W*n), to store the bottom up solutions.

0-1 Knapsack Pattern

There are a lot of popular dynamic programming problems that are based on the Knapsack problem. All those problems will usually have the following things in common

We will be given a number of items and a target sum, or max weight, or max capacity etc
We will be given the weight of the items. But in some problem variations, the item values themselves are weights.
Choice of items. We will need to choose items so that the total value of the chosen items is maximum and the total weight of those items do not exceed the max capacity. But in some problem variations, instead of maximizing the total value, we will be given a target sum or a target value that needs to be achieved.

Dynamic Programming