Published in · 4 min read · Jun 3, 2020
There are lots of tutorials around DP problems over the internet and some of them are misleading to whole DP concept in terms of approaching the problem. Hence, I thought of writing a detailed article on Knapsack problems and the methods to approach the variety of DP problems.
First of all, let’s understand what is dynamic programming?
The folks who know DP concept initially consider building a DP table to maintain their result and get stuck in the middle of the problems. This is completely wrong and instead they should first learn about the core concept of dynamic programming.
Brief description about recursion
It simply creates a function stack in memory and returns the result from the stack to its previous calling stack. Firstly, recursion takes a reduced input upon every function call and we define a base condition defined in recursive function to break or return from the existing or said last stack.
What if we do not pass the reduced input to recursive function? Obviously, it will run endlessly and throws Stack overflow error. Usually, the recursive function template should be as follows in most of the cases.
recursive(int[] array, int weight) {
//define baseCondition
//make next recursive call
}Here, the baseCondition is nothing but the smallest valid input after which if our code runs, it would do nothing or crash and keep increasing function stack unnecessarily.
What is memoization?
Well, if you carefully observe the above diagram, recursive function e.g. f(n-2) will get called even if the it was called from some another call stack and deteriorates the performance and time complexity of the program. Just for the sake of understanding, I’m putting it up here again with highlighted marking.
What if we could store the result somewhere in memory for that function call or in simpler terms, for a specific input args that f(n-2) takes…It’s cool, right?This way, when recursive function f(n-2) gets called and if that function has produced result before which can be retrieved from storage/memory in O(1) time rather compelling the function to execute and calculate the result repetitively.
The question is, how can we store the result of the function call with reduced number of arguments. That’s where DP table comes in picture. Firstly, identify the varied arguments to the recursive function and prepare a table to with n+1 size where n is the size of the initial input.
Secondly, initialize the table with some value e.g. -1 if we are going to store int result in table. Lastly, keep filling the table if the value is not stored before and retrieve the value later whenever required. This follows top-down approach which means the values will get filled from 1st row and column to the last. The last value should be our result. However, it does not necessarily be top-down approach but it depends on approach and may follow bottom-up approach as well if we chose to use iterative one instead of recursion.
That makes sense, right….
What is DP?
Dynamic programming is nothing but splitting out the problem into sub problems and gather the result of those sub problems in a very intuitive manner.
Generally speaking, DP = enhanced recursion + memoization
When you have to find out the optimal(min, max, largest, smallest) solution, DP is used efficiently to find the answer than any other algorithms. For example, find the maximum profit, maximum difference between 2 elements of an unsorted array and many more…
O(1) knapsack problem
What is knapsack basically? If you search this word out on internet, it is a synonym for a bag or carrier. We will use the same word and define a problem soon.
How to identify knapsack problems?
You will be given something like an input array with associated weights in an another array and you have to find out the optimal solution by processing those inputs.
Problem statement:
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).
As mentioned above, in order to find an optimal solution, we have to adopt DP approach to solve the problem, right…
What will be our approach then?
Simple, recursion + memoization = DP
Let’s write the code to find the maximum profit.
public int knapSack(int W, int wt[],int val[], int n) { // Base Case
if (n == 0 || W == 0)
return 0; if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1); // Return the maximum of two cases:
// (1) nth item included
// (2) not included
else
return max(val[n - 1] +
knapSack(W - wt[n - 1],wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
In above program, we have 2 choices for knapsack and that is whether to include the item in bag or not to gain max profit. We start from the very end and calculate the maximum of items included for the current index vs not included in current index and leave to pick it from next.
Hope the whole article helped you in understanding the DP based knapsack problem.
Will keep discussing more algorithms here…Happy coding!!
