Dynamic Programming-Parent Problem 1 (0/1 Knapsack): 3 approaches with practice questions.
Introduction
“Every problem of dynamic programming can be solved by plain recursion.”
Then why do we do dynamic programming?
Here’s why:
Let us write a program for Fibonacci Numbers.
The Fibonacci numbers are the numbers in the following integer sequence.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation
Fn = Fn-1 + Fn-2with seed values
F0 = 0 and F1 = 1.Let us use recursion to solve this problem:
#include<bits/stdc++.h>
using namespace std;int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}int main ()
{
int n = 5;
cout << fib(n);
getchar();
return 0;
}
Now, if we dry run this program, we will get the following recursion tree:
In the above tree, the function calls for a particular value to occur more than once. For instance, function call for n = 0, is called 3 times. And each function call will execute the function again.
Thus the time complexity of this program is 2^n or exponential.
Now, let us take a look at another program:
#include<bits/stdc++.h>
using namespace std;class A{
public:
int fib(int n)
{
// Declare an array to store
// Fibonacci numbers.
// 1 extra to handle
// case, n = 0
int f[n + 2];
int i;// 0th and 1st number of the
// series are 0 and 1
f[0] = 0;
f[1] = 1;for(i = 2; i <= n; i++)
{
//Add the previous 2 numbers
// in the series and store it
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
};// Driver code
int main ()
{
A a;
int n = 9;
cout << a.fib(n);
return 0;
}
In the above program, we used an array to store the results of all the function calls. When a subproblem comes again, we check the array and return the result directly. It saves us time running all the statements again.
It is an example of dynamic programming.
Definition
Dynamic programming is nothing but recursion with memorization. We calculate and store the results of subproblems. Thus, when a subproblem comes again, we directly use the result. It makes our code faster and reduces the time complexity (computing CPU cycles are reduced).
The three Parent Problems
These problems rule the kingdom of dynamic programming:
- 0/1 knapsack problem
- Longest Common Subsequence (LCS)
- Matrix Chain Multiplication (MCM)
In this blog, we will be covering the 0/1 Knapsack Problem.
Stay tuned, and there is a bonus waiting for you at the end of the blog ;)
Approach for any problem of DP
For every problem of dynamic programming, we first write a recursive code.
Why?
Because recursion is easy to write :)
Taking the example of Fibonacci numbers in mind, we notice that first, we wrote the recursive code. Then, we observed that some subproblems were solved again and again. Thus, in the recursive code, we maintain a container to store the results of the subproblems.
After this, if desired, we can convert our recursive code into an iterative one.
Usually, recursive code with a container to store the results of the subproblems is enough. But in some problems, the memory stack gets overflowed because of numerous function calls. Thus, we convert our code into an iterative one.
The above approach is general for all the DP questions.
0/1 Knapsack Problem
We have a set of items, each with a weight and a value. We need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Please note that the items are indivisible. We can either take an item or not (0–1 property).
For Example:
Input:
value array (val)= [4,2,10,1,2]
weight array (wt)= [12,1,4,1,2]
int W = 15
Recursive Code:
First, we will draw the choice diagram:
For a value say 12, we will check two things:
I. If the weight(w1) of an item is greater than the weight of the knapsack(W), then we can’t include it.
II. If the weight(w1) is lesser or equal to the weight of the knapsack(W), then it’s our choice to include it.
Writing the recursive code will get very easy after drawing the choice diagram.
The structure of a recursive code is as follows:
return_data_type function_name(arguments){
BASE CONDITION
CHOICE DIAGRAM
}
To check the base condition, think of the smallest valid input. We will be receiving the size of the array(n) and weight of the knapsack(W) as our varying inputs.
Thus, our smallest valid input will be when n == 0 || W == 0.
Thus the base condition will be:
if(n==0 || W==0){
return 0;
}Now, we have to code the choice diagram:
if(wt[n-1]<=W){ return max(val[n-1] + knapsack(wt,val,W-wt[n-1],n-1) ,
(knapsack(wt,val,W,n-1)));
}
Here, we are considering that the weight of the object is less than or equal to the weight of our knapsack.
Thus, it’s our choice to include it or not in the knapsack.
So, we will return the maximum value of both circumstances.
if(wt[n-1]>W){ return (knapsack(wt,val,W,n-1));
}
In our second choice, we don’t include the item in our bag since its weight is greater than the weight of our knapsack.
Now, let’s compile the entire code:
int knapsack(int wt[], int val[], int W, int n){ if(n==0 || W == 0){ return 0;
} if(wt[n-1]<=W){ return max(val[n-1] + knapsack(wt,val,W-wt[n-1],n-1) ,
(knapsack(wt,val,W,n-1)));
} else if(wt[n-1]>W){ return (knapsack(wt,val,W,n-1));
}
}
Memoization
We have learned the need for memorization in the example of the Fibonacci series. Thus, we will dive right into it.
You know that we will be using a matrix to store the results of the subproblems. But what should be the dimensions of the matrix?
The varying inputs of the recursive function decide that. In this question, we have the size of the array(n) and weight of the knapsack(W) as our varying inputs.
Thus the size of our matrix will be: (n+1)*(W+1)
The code after memorization will be as follows:
Assuming, n≤100 and W≤1000
int static t[102][1002];memset(t,-1,sizeof(t));int knapsack(int wt[], int val[], int W, int n){ if(n==0 || W == 0){ return 0;
} if(t[n][W]!=-1){ return t[n][W];
}if(wt[n-1]<=W){return t[n][W] = max(val[n-1] + knapsack(wt,val,W-wt[n-1],n-1) ,
(knapsack(wt,val,W,n-1)));
}else if(wt[n-1]>W){return t[n][W] = (knapsack(wt,val,W,n-1));
}
}
Bottom-Up Approach
As the name itself suggests, the bottom-up approach means starting from the bottom and accumulating answers to the top.
We will derive this method using the memorization approach in two steps:
- Initialization of the matrix.
- Converting the recursive calls into iterative code.
Initialization
For initialization, we will first declare our matrix. As told above, the dimensions of our matrix will be (n+1)*(W+1).
Row == 0 depicts that we have zero items for any weight. We can’t put any item in the bag, and thus our profit will always be zero. So, we will fill our first row with 0.
Column == 0 depicts that the weight of the knapsack for that particular subproblem is 0. We can’t put any item in our bag, since it has zero capacity. Thus we will put 0 in the first column of our matrix.
for(int i=0;i<n+1;i++){
for(int j=0;j<W+1;j++){
if(i==0 || j==0){
t[i][j] = 0;
}
}
}The iterative code will be as follows:
for(int i=0;i<n+1;i++){
for(int j=0;j<W+1;j++){
if(wt[i-1]<=j){
t[i][j] = max(val(i-1) + t[i-1][j-wt[i-1]], t[i-1][j]); } else{
t[i][j] = t[i-1][j];
}
}
}
I recommend you draw the matrix on your notebook and dry run the entire program. It will give you a better understanding.
Bonus
So, this was the 0/1 knapsack problem of dynamic programming. As I had mentioned, it is one of the parent problems, it has many children too.
If you want to practice more on this topic, here are some of the questions you can try:
3. Count of subsets with sum equal to X
4. Target Sum
6. Coin Change
If you want me to write on any of the above questions, do mention them in the comments.
