[Algorithm] Classic 0/1 Knapsack Problem - Dynamic Programming Solution (with C++ Code)

To watch the youtube video that goes over this problem, click here.

Problem Statement

A thief is robbing a museum and he only has a single knapsack to carry all the items he steals.

​The knapsack has a capacity for the amount of weight it can hold. Each item in the museum has a weight and a value associated with it.

Given the knapsack capacity and the weight and values of the items in the museum, find the maximum value the thief can steal. (Problem on HackerRank.)

A picture showing the setup of the classic 0/1 knapsack problem. We can solve this using dynamic programming.

---

Naive Solution: Try All Possible Ways Of Taking Items

The naive solution involves keeping track of the current value and weight of the knapsack, going through each item, and trying both ways of handling the item: we either leave it behind, or pick it up (if we have enough capacity left to hold its weight).

We can code this solution with a simple recursive function. Here's the C++ code for handling the naive knapsack solution:

The time complexity is O(2^numItems) because every recursive loop has two choices.
The space complexity is O(numItems) because each recursive loop travels down to each item and so the stack space goes that high.

---

Dynamic Programming (Best) Solution: Calculate Best Values Possible per Valid Knapsack Weights

The dynamic programming solution, like most DP solution, involves storing the best possible answer while going through each valid solution.

In the case of the knapsack problem, the DP solution is to generate a DP table that stores the maximum value a thief can steal at each item for each valid knapsack weight.

We build this table up by going through each item/knapsackWeight combination and taking the max of the choice "take this item, or don't" and choosing the highest value.

The dynamic programming C++ code that shows how to solve the knapsack problem is as follows:

The time complexity is O(numItems*knapsackCapacity) because that's the size of the DP table.
The space complexity is O(numItems*knapsackCapacity) because that's the size of the DP table.

Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels. 

Twitter: @srcmake
Discord: srcmake#3644
Youtube: srcmake
Twitch: www.twitch.tv/srcmake
​Github: srcmake