In any dynamic programming coding interview you take, you'll likely encounter the knapsack problem. This question is often a source of anxiety to interviewees because of the complexity of the solution and the number of variants of the problem.
Today, we'll get you comfortable with the knapsack problem in multiple languages by exploring two popular solutions, the recursive solution and top-down dynamic programming algorithm solution. By the end of the article, you'll have the experience needed to solve the knapsack problem with confidence.
Here’s what cover today:
- What is the knapsack problem?
- Brute-force recursive solution
- Optimized dynamic programming solution
- What to learn next
Prepare for your next coding interview like a pro
Walk into any coding interview with confidence. Study the fundamental patterns behind all the top dynamic programming questions.
Grokking Dynamic Programming Patterns for Coding Interviews
What is the knapsack problem?
The knapsack problem is one of the top dynamic programming interview questions for computer science.
The problem statement is:
You're a burglar with a knapsack that can hold a total weight of capacity. You have a set of items (n items) each with fixed weight capacities and values. The weight and value are represented in an integer array. Create a function knapsack() that finds a subset or number of these items that will maximize value but whose total weight does not exceed the given number capacity.
Knapsack Question Variants
There are two major variants of this question, fractional or 0-1. The fractional variant allows you to break items to maximize the value in the pack. The 0-1 variant does not allow you to break items.
Another common variant is the constrained knapsack problem that restricts your program so you cannot select any item more than once. When an element is selected, the program must decide if it should place it in the pack or leave it.
At senior level interviews, you'll encounter variants that add volume as a constrained attribute. In this case, each item also has a fixed volume, and the knapsack has a volume limit.
What skills does it test?
This problem is so popular because it tests many desired skills at once and can be altered to throw interviewees off balance. In other words, you have to really understand the logic of the problem and code. Simple memorization won’t take you far.
The optimal solution for the knapsack problem is always a dynamic programming solution. The interviewer can use this question to test your dynamic programming skills and see if you work for an optimized solution.
Another popular solution to the knapsack problem uses recursion. Interviewers may ask you to produce both a recursive and dynamic solution if they value both skill sets. This is a popular choice because interviewers can see how well you shift from a recursive to a dynamic solution.
The knapsack problem also tests how well you approach combinatorial optimization problems. This has many practical applications in the workplace, as all combinatorial optimization problems seek maximum benefit within constraints.
For example, combinatorial optimization is used in solutions like:
- Determine the best programs to run on a limited resource cloud system
- Optimize water distribution across a fixed pipe network
- Automatically plan the best package delivery route
- Optimize the company's supply chain
You can expect this question to be asked for any role that manages or creates automated optimization software.
Brute-force recursive solution
The most obvious solution to this problem is brute force recursive. This solution is brute-force because it evaluates the total weight and value of all possible subsets, then selects the subset with the highest value that is still under the weight limit.
While this is an effective solution, it is not optimal because the time complexity is exponential. Use this solution if you’re asked for a recursive approach. It can also be a good starting point for the dynamic solution.
Time complexity: $O(2^{n})$, due to the number of calls with overlapping subcalls
Auxiliary space: $O(1)$, no additional storage is needed.
Solution
Here's a visual representation of our algorithm.
All red item subsets exceed our pack's capacity, light green subsets are within capacity but are not the highest value.
For runnable solutions in C++, Python, and Java, view this article on the Educative site
#include <iostream>
using namespace std;
// Returns the maximum value that can be put in a knapsack of capacity W
int knapsackRecursive(int profits[], int profitsLength, int weights[], int capacity, int currentIndex) {
// Base Case
if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 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
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex] + knapsackRecursive(profits, profitsLength, weights, capacity - weights[currentIndex], currentIndex + 1);
int profit2 = knapsackRecursive(profits, profitsLength, weights, capacity, currentIndex + 1);
// Return the maximum of two cases:
// (1) nth item included
// (2) not included
return max(profit1, profit2);
}
int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
return knapsackRecursive(profits, profitsLength, weights, capacity, 0);
}
int main() {
int profits[] = {1, 6, 10, 16}; // The values of the jewelry
int weights[] = {1, 2, 3, 5}; // The weight of each
cout << "Total knapsack profit = " << knapSack(profits, 4, weights, 7) << endl;
cout << "Total knapsack profit = " << knapSack(profits, 4, weights, 6) << endl;
}
Explanation
On line 14, we start from the beginning of the weight array and check if the item is within the maximum capacity. If it is, we call the knapsack() function recursively with the item and save the result in profit1.
Then we recursively call the function, exclude the item, and save the result in the profit2 variable. On line 21, we return the greater of profit1 and profit2
Pseudocode:
Here's a pseudocode explanation of how this program functions.
for each item 'i' starting from the end
create a new set which INCLUDES item 'i' if the total weight does not exceed the capacity, and recursively process the remaining capacity and items
create a new set WITHOUT item 'i', and recursively process the remaining items
return the set from the above two sets with higher profit
This program contains many overlapping subproblems, but they're calculated each time rather than stored. Repeated calculations increase runtime drastically. To avoid recalculating we can instead use dynamic programming to memoize the solution to subproblems for reuse.
Optimized dynamic programming solution
Now, we'll optimize our recursive solution through the addition of top-down dynamic programming to handle the overlapping subproblems.
Since we have two changing values (capacity and currentIndex) in our recursive function knapsackRecursive(), we can use a two-dimensional array to store the results of all the solved sub-problems. As mentioned above, we need to store results for every sub-array (i.e. for every possible index i) and for every possible capacity c.
This is the optimal solution for the knapsack problem in both time and space complexity.
Time complexity: $O(N*C)$, our memoization table stores results for all subproblems and will have a maximum of $N*C$ subproblems.
Auxiliary space: $O(N*C + N)$, $O(N*C)$ space for the memoization table, and $O(N)$ space for recursion call-stack.
Tips: During the interview, make sure to talk through your thought process with the interviewer so they can see your problem-solving skills.
Solution
#include <iostream>
#include <vector>
using namespace std;
int knapsackRecursive(vector< vector<int> > lookupTable, int profits[], int profitsLength, int weights[], int capacity, int currentIndex) {
// base checks
if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0)
return 0;
// if we have already solved the problem, return the result from the table
if (lookupTable[currentIndex][capacity] != 0)
return lookupTable[currentIndex][capacity];
// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex] + knapsackRecursive(lookupTable, profits, profitsLength, weights,
capacity - weights[currentIndex], currentIndex + 1);
// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(lookupTable, profits, profitsLength, weights, capacity, currentIndex + 1);
lookupTable[currentIndex][capacity] = max(profit1, profit2);
return lookupTable[currentIndex][capacity];
}
int knapSack(int profits[], int profitsLength, int weights[], int capacity) {
vector< vector<int> > lookupTable(
profitsLength,
std::vector<int>(capacity + 1, 0));
return knapsackRecursive(lookupTable, profits, profitsLength, weights, capacity, 0);
}
int main() {
int profits[] = {1, 6, 10, 16};
int weights[] = {1, 2, 3, 5};
cout << "Total knapsack profit = " << knapSack(profits,4, weights, 7) << endl;
cout << "Total knapsack profit = " << knapSack(profits,4, weights, 6) << endl;
}
Explanation
To implement dynamic programming we only need to change 5 lines.
In line 9, we create a two-dimensional array, dp, to hold the results of any solved subproblem. This allows us to use these memoized solutions later rather than recalculating the answer.
In lines 22 and 23, we create a case that checks dp to see if the current sub-problem's solution has already been found. If we have, we return the memoized solution and move onto the next subproblem.
In lines 38, we calculate the maximum possible value of the bag if we include the current item in profit1 and the maximum value of the bag if we exclude the current item in profit2. We then save the higher of these in our two-dimensional array dp.
In line 39, we return the item that makes the highest knapsack value. This is a partial result that ends one recursive call before the next begins. Once this has occurred for all possible combinations, the first call will return the actual result.
What to learn next
Thanks for completing this deep dive into the 0-1 knapsack problem. Confidence with dynamic programming coding interview questions comes from practice and exposure to popular problem different variants.
As you're preparing for your next coding interview, here are some more DP questions you'll want to study:
- Longest common substring problem
- Palindrome subsequence problem
- Fibonacci numbers problem
- Staircase problem
- Coin change problem
Educative's course, Grokking Dynamic Programming Patterns for Coding Interviews, contains solutions to all these problems in multiple programming languages. Each solution has an in-depth, line-by-line solution breakdown to ensure you can expertly explain each solution to the interviewer. By the end of the course, you'll be able to walk into dynamic programming coding interviews confident that you're prepared for anything they can throw at you.
Happy interviewing!
Top comments (0)