The 0-1 knapsack problem is commonly used to illustrate the use of dynamic programming (DP in short). Despite the “scary” term, DP is mostly used to simplify recursive solutions and optimise for a better time complexity. A recursive solution which has multiple overlapping subproblems (like when we compute the Fibonacci sequence recursively) is a good candidate for DP.
In the knapsack problem, we are given
n number of items. Each item has a specific weight and a value. For example, I have a vase that weighs 500g and has a value of $20. We are also given a sack which can hold up to a weight of
w. Given this constraint, we need to optimise the selection of the items such that we can pick the greatest value within the means of the knapsack capacity.
The result is the maximum value we can achieve with the current set of items and weight constraint.
We can think of solving the knapsack problem recursively. For every item, we have 2 choices: either we select the item and we put it into the sack, or we reject the item (i.e. item does not go into the knapsack).
Hence, we try both choices for each item and we see which yields a better value. If we do select the
nth item, we reduce the current available weight capacity of the sack and recurse with the other
(n-1) items. If an item in the current recursive call exceeds the avaiable capacity of the sack,
(w), we ignore it and recurse with the other
The above, when translated into code, will look something like this in Python:
Of course, the above is not the most efficient way to do due to many overlapping subproblems. It yields a exponential time complexity of
(2^n) - for each item we make 2 choices.
Expanding the recursive stack, we can see a lot of duplicate calculations (overlapping subtrees). Rather than solving the same subproblems again, we can simply store the result somewhere and first check if the result is available. If it is, we use the computed result. Else, we compute it.
Here, we have initialised a 2D array,
store, to store computations. If they are required again, these can be simply retrieved, thus avoiding duplicate computations.
Here, we build the table in a bottom-up manner.
Using DP, we have simplified the problem and optimised the time complexity to
n is the number of items and
w is the weight the knapsack can hold.
Subscribe to Harish V
Get the latest posts delivered right to your inbox