Solving the Knapsack Problem with Dynamic Programming
Tags: computerscience, algorithms
Published: 2019-05-28 01:59:42

## What is the Knapsack Problem?
Consider a backpack (or "knapsack") that can hold up to a certain amount of weight. You have a set of items at your disposal, each being worth a different value and having a different weight. You want to fill the backpack with the most valuable combination of items without overburdening it and going over the weight limit. This is the [Knapsack Problem](https://en.wikipedia.org/wiki/Knapsack_problem). It's one of the most well studied [combinatorial optimization](https://en.wikipedia.org/wiki/Combinatorial_optimization) problems and a popular introduction to [dynamic programming](https://dev.to/vaidehijoshi/less-repetition-more-dynamic-programming-fl). In this post, we'll explain two variations of the knapsack problem:

1. Items can be selected repeatedly (the grocery store variation)
1. Items can be selected at most once (the museum variation)

Before we dive in, though, let's first talk briefly about what Dynamic Programming entails.

## Detour: Brief Introduction to Dynamic Programming
You may have heard the term "dynamic programming" come up during interview prep or be familiar with it from an algorithms class you took in the past. At it's most basic, Dynamic Programming is an algorithm design technique that involves identifying subproblems within the overall problem and solving them starting with the smallest one. Results of smaller subproblems are [memoized](https://en.wikipedia.org/wiki/Memoization), or stored for later use by the subsequent larger subproblems. Consider the following array, _A_:

![](https://thepracticaldev.s3.amazonaws.com/i/9y7m98z4pohtvqf9usi9.png)

Say we want to do a prefix sum across the array and we're specifically interested in element 4 (highlighted in red). Simple enough, just loop over and add up the values before it. Now let's say we want to know the prefix sum up to element 5. What about element 2? Do we need to loop over them all again for each one? Using Dynamic Programming we can do this a bit more efficiently using an additional array _T_ to memoize intermediate values.

Let _T[i]_ be the prefix sum at element _i_. We can then say **T[i] = T[i-1] + A[i]**. Here _T[i-1]_ represents a smaller subproblem -- all of the indices prior to the current one. Now look at the array _T_ below to help visualize this:

![](https://thepracticaldev.s3.amazonaws.com/i/zzqbnvd9l887x2uyb416.png)

This was a pretty simple example of Dynamic Programming, but we will use these same thought processes and techniques to solve the knapsack problem. Now back to our regularly scheduled programming...

---

## Knapsack Problem Restated
Let's restate the problem a bit more formally this time. We have the following:

* A knapsack that can hold a total weight _W_
* A collection of _n_ items to choose from
* Each of these _n_ items has a weight _w_ that can be selected from the array _w<sub>1</sub>...w<sub>n</sub>_
* Each of these _n_ items has a value _v_ that can be selected from the array _v<sub>1</sub>...v<sub>n</sub>_

We want to choose the optimal combination of items from such that we maximize the total value of our items without exceeding the maximum weight limit _W_.

### Our Knapsack and Items
For the sake of the problems below, we'll consider the following knapsack and collection of items:

**Knapsack:** _W_ = 15
**Items:**

| **Item** | **Weight** | **Value** |
|------|--------|-------|
| 1    | 2      | 1     |
| 2    | 10     | 20    |
| 3    | 3      | 3     |
| 4    | 6      | 14    |
| 5    | 18     | 100   |


---

## Repeated Selection (Grocery Store Variant)
The first variation of the knapsack problem allows us to repeatedly select the same item and place it in the bag. I call this the "Grocery Store" variant because I like to think of it as being like [Supermarket Sweep](https://en.wikipedia.org/wiki/Supermarket_Sweep) where participants race to fill a shopping cart with the highest valued items possible. Since the grocery store has lots of stock available, it's fine to pick the same item multiple times.

### Define our Subproblem
First let's define our subproblem. Let _w_ be a weight less than our max weight _W_. Or, in other words, **0 ≤ _w_ ≤ _W_**. Given that, we can define our subproblem as:

**K(_w_) = max value attainable with a total weight ≤ _w_**

So basically, each subproblem will operate on a smaller and smaller weight limit and we'll try our items available against that smaller limit.

### Define our Recurrence
**Base Case:** **K(0) = 0**
**Recurrence:** **K(_w_) = max( for(_i_..._n_) { K(_w_ - _w<sub>i</sub>_) + _v<sub>i</sub>_, if _w<sub>i</sub>_ ≤ _w_ } )**

What we're doing here is trying all possibilities for items to add while factoring in the weight capacity reduction incurred by that item. We use the _max()_ function to ensure we select the subproblem parameters that yield the highest value. Our base case is **K(0)** yielding a value of 0 because no item has a weight ≤ 0.

### Memoization Table Structure
For this problem we should be able to use a simple 1-dimensional table (array) from _w<sub>1</sub>_ to _W_ in length. In each index of this table we'll store the max value obtainable at that sub-weight and since we are able to pick the same items multiple times we do not need to store any information about the items chosen.

### Python Implementation
Below is a sample implementation in Python. Feel free to tweak the values for the items and _W_ to see what happens!
{% replit @tcdowney/knapsack-repetition %}

### Runtime Analysis
Let's take a look at the complicated bit of the code above and determine it's Big O upper bound.

```python
for w in range(1, W + 1):
  max_sub_result = 0
  for i in range(1, n):
    wi = item_weights[i]
    vi = item_values[i]
    if wi <= w:
      subproblem_value = K[w - wi] + vi
      if subproblem_value > max_sub_result:
        max_sub_result = subproblem_value 
  K[w] = max_sub_result
```

Within the outer loop over the _W_ weights we have a nested loop over the _n_ items. Within these loops the comparisons and lookups from **K[]** take constant time. This means our algorithm is dominated by the nested loops so it is _O(nW)_ in time complexity.

---

## Single Selection (Museum Variant)
The first variation of the knapsack problem allows us to pick an item at most once. I call this the "Museum" variant because you can picture the items as being one-of-a-kind artifacts. Here there is only one of each item so we even if there's an item that weights 1 lb and is worth the most, we can only place it in our knapsack once.

### Define our Subproblem
Our approach here will be very similar to the "Repeated Selection" variant with the caveat that we now have to keep track of the items that we've used. So let's take that into account when defining our subproblem! 

Let _i_ be a item from our _n_ items such that **0 ≤ _i_ ≤ _n_**.
Additionally, as before, let _w_ be a weight less than our max weight _W_. Or, in other words, **0 ≤ _w_ ≤ _W_**.

Given these conditions, we can define our subproblem as:

**K(_i_, _w_) = max value attainable with a subsect of objects in 1, ..., _i_ that have a total weight ≤ _w_**

### Define our Recurrence
**Base Case 1:** **K(0, _w_) = 0**
**Base Case 2:** **K(_i_, 0) = 0**
**Recurrence:** 

If **_w<sub>i</sub>_ ≤ _w_**:
**K(_i_, _w_) = max(K(_i_ - 1, _w_ - _w<sub>i</sub>_) + _v<sub>i</sub>_, K(_i_ - 1, _w_ - _w<sub>i</sub>_))**
Else:
**K(_i_, _w_) = K(_i_ - 1, _w_)**


This recurrence is a bit more complicated than the previous one, so let's take a second to deconstruct it. Our base cases are either when we're at item 0 which represents the empty set of items or when we're at weight 0 where we can no longer add any item to the knapsack. Since nothing can be added in either of these cases, our maximum value is 0.

Now for the recurrence we first have to check whether or not we have room to add the item in question to the knapsack. If we do have room we then try two possibilities:

1. We add the current item to the knapsack: **K(_i_ - 1, _w_ - _w<sub>i</sub>_) + _v<sub>i</sub>_**
1. We do not add the current item: **K(_i_ - 1, _w_ - _w<sub>i</sub>_)**

We take the maximum value of these two scenarios via _max()_.

If the item does not fit in the knapsack (i.e. **_w<sub>i</sub>_ > _w_**) then there is no point in considering what value we might get from it and we simply follow the **K(_i_ - 1, _w_ - _w<sub>i</sub>_)** path.

### Memoization Table Structure
Since our problem definition **K(_i_, _w_)** takes two parameters, a simple 1-dimensional array won't suffice. We will need a 2-dimensional table with dimensions from 0..._n_ and 0..._W_. In each index of this table we'll store the max value obtainable for each item _i_ at sub-weight _w_.

Spoilers, but for the problem above the final version of this table will look like this:

|   | 0 | 1 | 2 | 3 | 4 | 5 | 6  | 7  | 8  | 9  | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|----|----|----|----|----|----|----|----|----|----|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1  | 1  | 1  | 1  | 20 | 20 | 21 | 21 | 21 | 21 |
| 3 | 0 | 0 | 1 | 3 | 3 | 4 | 4  | 4  | 4  | 4  | 20 | 20 | 21 | 23 | 23 | 24 |
| 4 | 0 | 0 | 1 | 3 | 3 | 4 | 14 | 14 | 15 | 17 | 20 | 20 | 21 | 23 | 23 | 24 |
| 5 | 0 | 0 | 1 | 3 | 3 | 4 | 14 | 14 | 15 | 17 | 20 | 20 | 21 | 23 | 23 | 24 |

### Python Implementation
Below is a sample implementation in Python. Uncomment and run the Pandas code at the bottom to see the 2D table visualized.
{% replit @tcdowney/knapsack-no-repeat %}

### Runtime Analysis
Let's take a look at the complicated bit of the code above and determine it's Big O upper bound.

```python
for i in range(1, n):
  for w in range(1, W + 1):
    wi = item_weights[i]
    vi = item_values[i]

    if wi <= w:
      K[i][w] = max([K[i - 1][w - wi] + vi, K[i - 1][w]])
    else:
      K[i][w] = K[i - 1][w]
```

The analysis for this problem is very similar to what we did earlier. The outer loop over the _n_ items contains an inner loop over the _W_ weights.. Within these loops the comparisons, _max()_, and the lookups from **K[][]** take constant time. This means our algorithm is dominated by the nested loops so it is _O(nW)_ in time complexity.

---

## Summary

There you have it, two variations of the knapsack problem with table-based Dynamic Programming solutions. Hopefully you found this post helpful. If not, I at least found it helpful for myself to write it!

---

**Cover Image Photo Credit:**
_"Fjallraven Grid" by [Mitchell Griest](https://unsplash.com/@griestprojects) on [Unsplash](https://unsplash.com/)_

I felt this photo really captured the concepts of knapsacks and memoization tables. 😂