Dynamic Programming — 0/1 Knapsack Problem
So, I have just recently started learning DP. So here I am posting my notes here with each problem I am learning so far. Please feel free to add suggestions or comments.
0/1 Knapsack Problem — This is considered the first classical DP problem. It states something like this —
You are 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. Note that we have only one quantity of each item.
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 dont pick it (0-1 property).Example 1:Input:
N = 3
W = 4
values[] = {1,2,3}
weight[] = {4,5,1}
Output: 3Example 2:Input:
N = 3
W = 3
values[] = {1,2,3}
weight[] = {4,5,6}
Output: 0
So as we know, how to identify if a given problem is a DP problem or not.
There are two properties common in every DP problem —
- Overlapping Subproblems. — Multiple recursive calls for the same solution building with varying inputs. If there’s only one recursive call needed, NO DP.
- Optimal values(minimum, maximum, smallest, largest) — Asks for some optimal single values solution.
DP = Recursion + Memoization. Basically when recursive solution gets optimized from recalculating on the same inputs again and again, that optimized solution is called DP solution.
Every DP problem is a recursion problem first. So first let's try to figure out what’s the recursive problem here and build a recursive solution first.
W = knapsack’s weight, N= number of items.
Base Case: Handling of the smallest valid input that might come.
if W = 0 or N = 0 return 0; // If Weight is 0 or no items are there to pick. Then this is the max profit we can earn so far.Now, next as we are processing every element, There are two scenarios that might happen
1. Item’s weight (w[i]) is larger than the capacity of Knapsack (W).
2. Item’s weight (w[i]) is smaller or equal to capacity of knapsack (W).
For first case, We can’t pick that item in knapsack because its larger than the capacity of knapsack. We have to skip it and proceed to check other items.
For second case, We do get to make a choice —
— If we want to take it into knapsack.
— If we want to skip it from knapsack.
So this is where recursion comes in.
We need to collect maximum profit collecting elements who are within knapsack capacity.
So the recursive equation becomes here something like this -
int recursive_0_1_knapsack(int W, int wt[], int val[], int n) {
if (W == 0 || n==0) // Base case
return 0;
if (wt[n-1] <= W) { // 2nd case above mentioned. We consider n as a index here in recursive solution.
max_profit = max(
val[n-1] + recursive_0_1_knapsack(W - wt[n-1], wt, val, n-1),
// If we pick this current element, this item's value gets added into the profit and we get max profit from remaining elements recursive call for the remaining weight.
recursive_0_1_knapsack(W, wt, val, n-1)
// If we don't pick that element, the maximum profit We need to get from remaining elements, as we didn't consider this item, so knapsack weight still remains the same. .
);
} else {
// First case, current element's weight is larger than Knapsack's weight, so we need to skip it.
max_profit = recursive_0_1_knapsack(W, wt, val, n-1);
}
}So this is the first step of DP, building a recursive solution.
The next step is to memoize it i.e. store the recursive solution’s result in some storage so that the same recursive calls with the same parameters i.e. overlapping subproblems don’t have to calculate it from the beginning again. Once calculated, those results can be stored and utilized for further calls.
So before going for memoization, If you are wondering where're the overlapping recursive calls,
Check the number of recursive calls being made in the above recursive function, If there’s just 1 recursive call, that means it’s a plain recursion problem, if there’s more than one recursive call, then that means there exists/will be overlapping recursive calls. As you see there are 3 recursive calls in above mentioned recursive solution, two of them are with the same parameters, which indicates there’s a strong need to store those recursive results from stopping them from recalculation. That’s what memoization is.
So let’s try to memoize it here with the recursive solution first.
int [][]t = new int[W+1][N+1];
// t[W][N] will be our answer. So to accomate all the numbers/recursive results, we make matrix to accomodate all possible solutions.
for (int[] tRow : t)
Arrays.fill(tRow, -1); // populate it as default -1.
int recursive_memoized_0_1_knapsack(int W, int wt[], int val[], int n) {
if (W == 0 || n==0) // Base case
return 0;
// If solution is already computed and stored, use that one.
if (t[W][N] != -1) {
return t[W][N];
}
// if item's weight is less than W. We consider n as a index here in recursive solution.
if (wt[n-1] <= W) {
t[W][N] = Math.max(
val[n-1] + recursive_memoized_0_1_knapsack(W - wt[n-1], wt, val, n-1),
// If we pick this element, this item's value add into the profit and we get max profit from remaining elements recursive call for the remaining weight.
recursive_memoized_0_1_knapsack(W, wt, val, n-1)
// If we don't pick this element, the maximum profit We need to get from remaining elements, as we didn't consider this item, so knapsack weight still remains the same. .
);
} else {
// case when current element's weight is larger than Knapsack's weight, so we need to skip it.
t[W][N] = recursive_memoized_0_1_knapsack(W, wt, val, n-1);
}return t[W][N];
}
So this is how we are storing each subproblem’s result in matrix t and storing it to avoid recalculation/recomputation again and again.
The drawback here can be extensive recursive calls being made, which might exhaust the compiler’s function call stack. (It failed on the first test case on GeeksForGeeks, so you know it might happen more frequently than we expect.).
Now let’s move forward with the top-down approach for this. This is a standard way for memoization i.e. storing computed results of subproblems. In the Top-Down approach, We build a matrix to store already computed results up to that combination of inputs. So for building the matrix, First identify what are the varying input params among recursive calls. So if we see all the three calls in the previous memoized solution, those are —
recursive_memoized_0_1_knapsack(W - wt[n-1], wt, val, n-1)
recursive_memoized_0_1_knapsack(W, wt, val, n-1)
recursive_memoized_0_1_knapsack(W, wt, val, n-1)So as you see, the first and last params, i.e. W and N values are being changed across all 3 recursive calls, so for these varying values across the calls, we need to store the subproblems result in the matrix. So our matrix will be a 2D matrix of size (N+1) * (W+1). Why N+1 and W+1, because we will be storing every input size’s (i) maximum profit with a given weight (j) at t[i][j]. Thus we will get our answer i.e. maximum profit of N items with W weight at t[N][W]. FYI, 0 is a valid input for N and W both. So we can’t adjust the profits for t[N][W] to t[N-1][W-1].
So We first build up the matrix for base cases i.e. when N or W = 0 then we use the recursive solution to fill the matrix.
Top-Down matrix solution:
int t[][] = new int[n+1][W+1];
int top_down_0_1_knapsack(int W, int wt[], int val[], int n) {
if (W == 0 || n==0) // Base case
return 0;
// First fill default values always, because there can be default values available in top down calculation.
for (int i=0; i<=n; i++) { // represents items numbers
for (int j=0; j<=W; j++) {// represents knapsack weight.
// if no item or no knapsack exists, then result is 0;
if (i==0 || j==0)
t[i][j] = 0;
}
}
// Here we build our top down approach from recursive approach.
for (int i=1; i<=n; i++) { // represents item numbers
for (int j=1; j<=W; j++) { // represents knapsack weight.
if (wt[i-1] <= j) { // if current item's weight is less than current knapsack weight (j)
t[i][j] = Math.max(
val[i-1] + t[i-1][j - wt[i-1]],
//current item(i)'s value + maximum profit stored for remaining items (i-1) with remaining knapsack weight (j-wt[i-1]). t[i-1][j]
// Skipping the element, so profit stored for remaining items (i-1) with same current weight (j). );
} else { //current item's weight is larger than current knapsack weight(j).
t[i][j] = t[i-1][j]; //Skipping the element, so profit stored for remaining items (i-1) with same current weight (j).
}
}
}// our answer is t[n][W] max profit for n items for knapsack weight W.
return t[n][W];
}
So as you see in the matrix, we are storing profit for the combination of i and j i.e. The number of items, and weight.
And we are using those weight and value arrays inside the loops with i and j for storing the profit in the matrix i.e. filling up the matrix.
And also notice as i and j are representing N and W, so nowhere in those top-down loops, n and W are being used because those are being represented by i and j.
Hence at the end, when i = n and j = W, We get our answer — maximum profit with given weights and values of n items with knapsack’s capacity W. That’s how we get our answer — t[n][W].
And this is the solution for the 0/1 Knapsack problem. This problem works as the base for many other problems i.e. The Subset-sum, Target sum, Equal partition sum problem, and many others. All these problems are also quite popular DP problems, and these problems are different variations of the same 0/1 Knapsack problem, so if you understand 0/1 knapsack better. It builds a foundation for those problems understanding as well.
Thanks for reading it up till here. Let me know any suggestions, or note in the comments. Thanks.
