Knapsack Problem

4 min readApr 11, 2022

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 forms of this question: fractional and 0–1. You can divide goods up to boost the worth of the pack using the fractional variation. Breaking objects in the 0–1 variation is not possible.

The restricted knapsack problem is another common type, which restricts your programme by preventing you from selecting the same item twice. When an element is selected, the software must determine whether or not it should be included in the package.

You’ll come across versions that feature volume as a limited characteristic at the senior level. In this example, each item has a specific volume, and the knapsack has a volume limit.

What skills does it test?

This task is popular because it assesses a variety of skills at once and can be changed to throw candidates off. To put it another way, you must fully comprehend the problem’s logic and code. Memorization alone will not get you very far.

A dynamic programming approach is always the best solution for the knapsack issue. This question might be used by the interviewer to evaluate if you have any dynamic programming skills and if you work for an efficient solution.

Recursion is another prominent solution to the knapsack problem. If interviewers prioritise both skill sets, they may ask you to develop both a recursive and dynamic solution. This is a popular option since it allows interviewers to assess your ability to transition from a recursive to a dynamic solution.

The knapsack problem also assesses your understanding of combinatorial optimization problems. As all combinatorial optimization problems seek maximum advantage within restrictions, this has a wide range of applications in the workplace.

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

Brute force recursion is the most obvious answer to this problem. This is a brute-force solution because it calculates the total weight and value of all potential subgroups, then chooses the one with the highest value while staying under the weight limit.

While this is a viable approach, it is not ideal due to the exponential time complexity. If a recursive method is required, use this solution. It’s also a fantastic place to start for a dynamic solution.

Time complexity: O(2^{n})O(2n), due to the number of calls with overlapping subcalls

Auxiliary space: O(1)O(1), no additional storage is needed.

Optimized dynamic programming solution

To tackle the overlapping subproblems, we’ll now optimise our recursive solution by adding top-down dynamic programming.

We may use a two-dimensional array to hold the outcomes of all the solved sub-problems because our recursive procedure knapsackRecursive() has two changeable values (capacity and currentIndex). As previously stated, we must store results for each sub-array (that is, for each potential index I and capacity c.

In terms of both time and space complexity, this is the best solution for the knapsack issue.

Time complexity: O(N*C)O(N∗C), our memoization table stores results for all subproblems and will have a maximum of N*CN∗C subproblems.

Auxiliary space: O(N*C + N)O(N∗C+N), O(N*C)O(N∗C) space for the memoization table, and O(N)O(N) space for recursion call-stack.

solution:

Pseudo-code

The pseudo-code for this problem is

Time Complexity: Time complexity of the sorting + Time complexity of the loop to maximize profit = O(NlogN) + O(N) = O(NlogN)

Space Complexity: O(1)