0/1 knapsack problem using dynamic programming

Tags: , , , ,

0/1 Knapsack problem

0/1 Knapsack is typical problem which is used to demonstrate application of greedy algorithm as well as dynamic programming. There are cases when applying greedy algorithm does not give optimal solution. There are many flavors in which Knapsack problem can be asked.  

1. A thief enters a museum and want to steal artifacts from there. Every artifact has a weight and value associated with it. Thief carries a knapsack (bag) which can take only a specific weight. Problem is to find the combination of artifacts thief steals so that he gets maximum value and weight of all taken artifacts is less capacity of  knapsack he has. Thief cannot take any artifact partially. Either he takes it or leaves it. Hence the problem is 0/1 knapsack.

2. We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be stored re-computation cost is Vi. Problem is to store as many files on storage that combined size of all files is less than W and their re-computation value is maximum. We can either store or leave a file, we cannot store partial file. Hence this is a case of 0/1 knapsack problem.

0/1 knapsack problem : Line of thoughts

Brute force method would try all subsets of set of items, whose weight adds up to maximum capacity of knapsack and see which one gives maximum value. Complexity of brute force algorithm would be of exponential order as there will be 2n possible subsets for n items.

Can we do better?  If we consider each item, there are two possibilities associated with it.
First, current item is included in optimal subset. Then we need to find out all the items in remaining N-1 items which can optimize the subproblem for weight W-wk. Value of this item is added to candidate maximum value.

Second, current item is not included in optimal subset. In that case, we need to find out items in remaining N-1 items which can optimize the the original problem. Value of current item is not added into candidate maximum value.

Inclusion depends on two conditions :

  1. Weight of the item is less than the total capacity of knapsack.
  2. Inclusion of item increases current max value with K-1 items with W-Wk weight.  

Since every steps reduces the problem to a smaller problem in terms of items of weight, recursive solution would be our first refuge. To implement this problem, what are the base cases? First, we cannot add any items to knapsack capacity is zero i.e. W == 0. Second, no item can be taken if there are no items remaining, i.e. n == 0.

Recursive implementation of 0/1 knapsack problem

package com.company;
/**
	* Created by sangar on 19.8.18.
*/
public class KnapsackProblem {
	static int knapSack(int W, int[] weights, int[] val, int n) {
		/*
			If there is no item or weight that can be carried is
			zero, return zero
		*/
		if (n < 0 || W == 0)
			return 0;

		/* 
			If weight of the nth item is more than Knapsack 
			capacity W,then this item cannot be included
			in the optimal solution
		*/
		if (weights[n] > W)
			return knapSack(W, weights, val, n - 1);

		/* Consider two cases, including item and excluding item.*/
		else return Integer.max(
			(val[n]
				+ knapSack(W - weights[n], weights, val, n - 1)),
			(knapSack(W, weights, val, n - 1))
		);
	}

	public static void main(String args[]) {
		int[] val = {60, 100, 120};
		int[] wt = {10, 20, 30};
		int W = 50;
	
		int n = val.length;
		System.out.println(knapSack(W, wt, val, n - 1));
	}
}

If we look at the execution trace of the function, it looks like this.

0/1 knapsack problem

There are seven problems to be solved at the leaf level. For N = 3, there are 7 problems to be solved before we start optimizing for the max value. For N, in general, it will take 2N subproblems to be solved. Hence, complexity of recursive implementation is O(2N).

If we take another example, it will become evident that there are some subproblems which are solved again and again. Overlapping subproblems is one of the criteria, we should be thinking about dynamic programming. Also, notice that optimal solution to a smaller problem leads to optimal solution to bigger problem, which is second condition for DP.  This problem satisfy both these conditions, hence let’s design DP solution for it.

0/1 knapsack problem : Dynamic programming approach

We define two dimensional array V[N,W] where N is number of items and W is capacity. For 1<= i <= n and  0<=w<=W, V[i,w] represents the optimal solution for items I1, I2, ..In with maximum weight of w.  If we can compute all the entries of this array, then the array entry V[N,W] is the solution to our problem

For i =0 and w=0, all values will be zero. So, first column and first row will be filled with all zero values.
Recursively, we can fill the table bottom up as follows.

V[i, w ] = max (V[i-1, w], V[i-1, w-w[i]) + V[i] )
V[0, w ] = 0; there are no items
V[i, 0 ] = 0; no items can be picked.
package com.company;

/**
	* Created by sangar on 19.8.18.
*/
public class KnapsackProblem {
	public static int knapsackDP(int W, int[] weights, int[] val, int n) {
		int[][] V = new int[n+1][W + 1];
		for(int i = 1 ; i &lt; V[0].length; i++){
			/*
				If weight of item is less than current value
				we can achieve minimum value V[i] with 1..i items
			*/
			if(weights[0] &lte; i){
				V[0][i] = val[0];
			}else{
				V[0][i] = 0;
			}
		}

		//Loop for all items
		for (int i = 1; i &lt; V.length; i++) {
			for (int j = 1; j &lt; V[i].length; j++) {
				/*if a weight is more than the allowed weight, 
				that weight cannot be picked. */
				if(weights[i] &gt; j){
					V[i][j] = V[i-1][j];
				}else{
					V[i][j] = Math.max(V[i-1][j], 
							val[i] + V[i-1][j-weights[i]]);
				}
			}
		}
		return V[V.length-1][W];
	}

	public static void main(String args[]) {
		int[] val = {60, 100, 120};
		int[] wt = {10, 20, 30};
		int W = 50;

		int n = val.length;
		System.out.println(knapsackDP(W, wt, val, n - 1));
	}
}

One similar problem which can be solved with same approach is minimum number of coins to be used to get change of a particular amount. I am skipping the whole analysis and directly pasting the code here.  

Complexity of the dynamic programming implementation of knapsack problem is O(N *W). Space complexity is again O(N*W). It is thumb rule that we trade space for time in dynamic programming.

Please share if there is something is wrong or missing. If you want to contribute to website, please reach out to us at communications@algorithmsandme.com