Coding Pattern : 0/1 Knapsack Dynamic Programming
If there exists a problem which can be broken down into smaller sub problems and then those subproblems can be solved optimally and recursively, then such problems are said to be eligible to be solved by Dynamic Programming.
In this article we will be focusing on a sub type of Dynamic Programming called 0/1 Knapsack Dynamic Programming (also known as Bounded Knapsack Dynamic Programming).
Knapsack problem according to Wikipedia is defined as :-
“Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.”
In simpler words, imagine we are in the Mr. Beast universe. As he says in so many of his videos, we can go to a store (given a fixed capacity bag, in our case a Knapsack) and we can pick whatever we want. As per our normal human tendency we would always want to pick up the costliest items. We would pick up all that which would maximize the total cost of the items all the while keeping in mind that those items should fit into the Knapsack. That is the summary of the problem..
Knapsack can be bounded and unbounded. In bounded we are only allowed to choose an item only once, it cannot be repeated. Whereas in unbounded we are select an item any number of items. Bounded Knapsack is also called 0/1 Knapsack since at any point of time we are either selecting one or zero instances of that item.
Problem :
Example :
Lets say we have a Knapsack of capacity 7. We have items with weights and values as
weights = [1, 2, 3, 5, 7]
values = [10, 5, 4, 8, 5]
If we want to maximize the value of the knapsack we would need to employ 0/1 Knapsack Dynamic Programming.
All Possibilities with combined weight less or equal to 7:-
- We can choose items with weight 1,2,3 and total value 19.
- We can choose items with weight 1,3 and total value 14.
- We can choose items with weights 2,3 and total value 9.
- We can choose items with weights 1,5 and total value 18.
- We can choose items with weights 2,5 and total value 13.
- We can choose item with weight 7 and total value 5.
So as evident from the above we will be choosing the combination of 1,2,3 weights to maximize the total value as 19.
It is always a good idea to begin any dynamic programming problem with an intuitive recursive solution and later on optimize it. This encourages intuitive thinking rather than plane memorizing the Dynamic Programing solution.
Solution :
Thus we will begin the solution part by first coming up with a Recursive algorithm. Then later on, we will be optimizing the same with the help of Top Down Dynamic Programming.
We start our recursive algorithm by maintaining two state variables, firstly the variable i which represents the index of the weights/values collection, used to track at what position we are in our collection and secondly the variable capacity which represents the knapsack capacity as specified in the problem.
Dynamic Programming in general is all about choices.
We start the solution by setting our capacity equal to the max capacity in the beginning as our knapsack is empty and setting our index i variable to 0 since we start from the first item. At each iteration we face two choices.
Choice 1 : If the current item’s weight is less than equal to the knapsack current capacity we select the current item and move ahead (by increasing the index by 1). This we do by subtracting the knapsack capacity with the current item weight. We add the current value of the item to the response from the next recursive call (the call we create with index pointing to the next immediate item).
Choice 2 : We do not select the current index item. Since we have not selected anything in this iteration we simply create a new recursive call by passing the same capacity and increasing the index variable by one.
In the end we return the max of the two choices to arrive at the global maximum.
Our exit conditions would be:-
- The Knapsack capacity becoming zero since no more items can be added.
- The index variable i, exceeding the length of the item collection.
In case of both the above exit conditions, we simply return 0 since we are not selecting anything when either of the above is true.
Below is the simulation of the recursive solution. We start with the call R(7,0) where 7 is the max knapsack capacity and 0 is the index of the collection. At every call we make two choices, choice 1 which is the left one, where we select the current item, add its value to the return call and move along. Choice 2, the right arrow one, where we do not select the current item and just move along to the next index. The bottom to top arrows shows the return calls.
import java.util.*;
public class Knapsack{
public static int findKnapsack(int capacity, int[] weights, int[] values, int n)
{
return Recurse(capacity,weights,values,0);
}
private static int Recurse(int capacity,int[] weights,int[] values,int i)
{
if(capacity <= 0 || i >= weights.length)
{
return 0;
}
int choice1 = 0;
int choice2 = 0;
if(weights[i] <= capacity)
{
choice1 = values[i] + Recurse(capacity - weights[i],weights,values,i+1);
}
choice2 = Recurse(capacity,weights,values,i+1);
int max = Math.max(choice1,choice2);
return max;
}
}import java.util.*;
public class Knapsack{
public static int findKnapsack(int capacity, int[] weights, int[] values, int n)
{
return Recurse(capacity,weights,values,0);
}
private static int Recurse(int capacity,int[] weights,int[] values,int i)
{
if(capacity <= 0 || i >= weights.length)
{
return 0;
}
int choice1 = 0;
int choice2 = 0;
if(weights[i] <= capacity)
{
choice1 = values[i] + Recurse(capacity - weights[i],weights,values,i+1);
}
choice2 = Recurse(capacity,weights,values,i+1);
int max = Math.max(choice1,choice2);
return max;
}
}Coding Pattern Template
Most of the Dynamic Programming problems will be following some variation of the below template. I would suggest spending sometime to understand the template before moving forward.
import java.util.*;
public class Knapsack{
public static int findKnapsack(int capacity, int[] weights, int[] values, int n)
{
/*Single call to our recurse function with the given items
plus the state variables which are going to change, in this case
only the index is gonna change so that is the only addtional
state variable we will pass so as to track the end of the array*/
return Recurse(capacity,weights,values,0);
}
private static int Recurse(int capacity,int[] weights,int[] values,int i)
{
/* The first statement int the Recurse method of a DP problem
will be an exit condition. In most case it would be either
the end of the array or a failure of a problem specific constraint*/
if(capacity <= 0 || i >= weights.length)
{
return 0;
}
/*Here we will mostly initialise the choices which we are going to perform
later. This can be any number but in most case it would be 2.*/
int choice1 = 0;
int choice2 = 0;
/*Condition to check if we can make make the first choice*/
if(weights[i] <= capacity)
{
choice1 = values[i] + Recurse(capacity - weights[i],weights,values,i+1);
}
/*This step would be a bunch of recurse method calls.
*/
choice2 = Recurse(capacity,weights,values,i+1);
/*This again is a common step where we collate the result
of all the Recursive calls we have so far made and return the max/min
up until this point to the previous stack call*/
int max = Math.max(choice1,choice2);
return max;
}
}The time complexity of the above algorithm comes out to be 2^n, this is due to the reason that at every recursive step we make two choices for every i.
This recursive solution is great to start with but would give Time Limit exceeded output for larger test cases and is not an acceptable final solution for most interviews.
Next we will be using the Top Down Memorization technique to fasten it up.
If you observe in the below image, the Recursive step R(4,3) has been repeated. What if we store the result of this call the first time it executes and use the same result in the later calls instead of calculating it again by going over the sub tree. This is exactly what we are going to do in top down memoization.
We will be using the data structure called HashMap in Java, also known as Dictionary in C#. This structure will be storing the precomputed result of the smaller problem which is being reused multiple times.
In the below code we initialize a structure called ‘dp’. We will be passing it along in all the calls to the Recurse function.
For the ‘Key’ we will be using a string composed of index and capacity. This ensures that we have key for all possible i and capacity combinations. If the key already exists we return the corresponding result from the dp, if it does not exist we compute it, we then store it and in the end return it. This way the time complexity of this solution comes down to O(N²) from O(2^n).
import java.util.*;
public class Knapsack{
public static int findKnapsack(int capacity, int[] weights, int[] values, int n)
{
HashMap<String, Integer> dp = new HashMap<>();
return Recurse(capacity,weights,values,0,dp);
}
private static int Recurse(int capacity,int[] weights,int[] values,int i,HashMap<String, Integer> dp)
{
String key = capacity + "," + i;
if(capacity <= 0 || i >= weights.length)
{
dp.put(key,0);
return 0;
}
if(dp.containsKey(key))
{
return dp.get(key);
}
int choice1 = 0;
int choice2 = 0;
if(weights[i] <= capacity)
{
choice1 = values[i] + Recurse(capacity - weights[i],weights,values,i+1,dp);
}
choice2 = Recurse(capacity,weights,values,i+1,dp);
int max = Math.max(choice1,choice2);
dp.put(key,max);
return dp.get(key);
}
}Problem 2 : Subset Sum
This problem consists of a collection of number say = {1,3,4,5}. We need to find if the subset of these number sum to 7. This is a classic application of the 0/1 Knapsack Dynamic Programming pattern.
I am directly adding the Top down Dynamic Programming solution of this problem.
import java.util.*;
class SubsetSum {
public static boolean subsetSum (int [] arr, int total)
{
HashMap<String, Boolean> dp = new HashMap<>();
return Recurse(arr,total,0,dp);
}
private static boolean Recurse(int[] arr, int total, int i,HashMap<String,Boolean> dp)
{
String key = total + "," + i;
if(dp.containsKey(key))
{
return dp.get(key);
}
if(total == 0)
{
dp.put(key,true);
return true;
}
if(i >= arr.length)
{
dp.put(key,false);
return false;
}
boolean choice1 = false;
boolean choice2 = false;
if(arr[i] <= total)
{
choice1 = Recurse(arr,total-arr[i],i+1,dp);
}
choice2 = Recurse(arr,total,i+1,dp);
boolean result = choice1 == true ? choice1 : choice2;
dp.put(key,result);
return dp.get(key);
}
}This is the end of the article. Thanks for reading it. If you liked the article and found it useful, please leave a clap and follow as it really motivates me to write more of these.
Also do check out the next variation of Knapsack called the unbounded Knapsack below :
