Dynamic Programming

Introduction

TODO: What is dynamic programming?

TODO: Motivate why the examples provided are interesting to look at.

Fibonacci Sequence

Introduction

The Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. The sequence commonly begins with $0$ and $1$, so the sequence is written as:

Mathematically, the Fibonacci sequence is commonly defined by the following recurrence relation:

For our purposes, we are interested in computing a single term of the sequence.

Naive Recursive Algorithm

A very simple algorithm is to simply implement our definition as a recursive function, though the runtime performance is a nasty $O \parens{2^n}$. Calculating $F_{42}$ took 45 seconds with an AMD Ryzen 7 5800HS CPU:

def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

print(fib(12)) # 144

from timeit import timeit
timeit(lambda : fib(42), number=1) # approx. 45 seconds

Top-Down Memoization Algorithm

One way to speed it up is the recognition that once we’ve computed a term of the sequence, we can store it for future use. This algorithm runs in $O \parens{n}$ time since we calculate each term only once:

def fib(n):
    memo = {0: 0, 1: 1}
    def _fib(n):
        if n not in memo: memo[n] = _fib(n - 1) + _fib(n - 2)
        return memo[n]
    return _fib(n)

print(fib(12)) # 144

from timeit import timeit
timeit(lambda : fib(42), number=1) # approx. 1.8e-05 seconds (18 microseconds)
timeit(lambda : fib(994), number=1) # approx. 0.00040 seconds (400 microseconds)
timeit(lambda : fib(995), number=1) # Python 3.10.9 'maximum recursion depth exceeded' error

Interestingly, if we calculate for $n = 995$ or higher, Python throws a maximum recursion depth exceeded error.

Bottom-Up Algorithm

You may have already spotted that rather than start from $F_n$ and recursively figuring out what we need to solve it, we could instead start from $F_2$ (and hardcode the base cases $F_0$ and $F_1$) and work our way upwards. This algorithm also runs in $O \parens{n}$:

def fib(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(1, n):
        a, b = b, a + b
    return b

print(fib(12)) # 144

from timeit import timeit
timeit(lambda : fib(42), number=1) # approx. 4.7e-06 seconds (4.7 microseconds)
timeit(lambda : fib(994), number=1) # approx. 3.9e-05 seconds (39 microseconds)
timeit(lambda : fib(1000000), number=1) # approx. 5.6 seconds

References

• Wikipedia: The mathematical notation was taken from here. Also, I stole a bit of the wording from it for the introduction.

0-1 Knapsack Problem

Problem Statement

You have a bag with a maximum weight carrying limit, and a set of items. Each item has a weight and dollar value. Find a subset of items with the largest dollar value possible that can fit within in the bag’s weight limit.

There is only one copy of each item available for you to take. Each item is either taken in its entirety, or not taken at all. You cannot “partially take” an item.

Example

Suppose your bag can only carry up to $\qty{15}{\kilo\gram}$ in total. The possible items we can choose from are shown in the table below:

The optimal solution is to take all items except Item 1. The total value of these items is $\dollars{10} + \dollars{2} + \dollars{2} + \dollars{1} = \dollars{15}$. The total weight of these items is $\qty{4}{\kilo\gram} + \qty{2}{\kilo\gram} + \qty{1}{\kilo\gram} + \qty{1}{\kilo\gram} = \qty{8}{\kilo\gram}$, which is clearly within the bag’s $\qty{15}{\kilo\gram}$ limit.

If we took Item 1, we will only have $\qty{3}{\kilo\gram}$ remaining. We wouldn’t be able to take Item 2, which is a significantly valuable item in the list. The best we can do is to take Item 3 and Item 5, giving us a total of $\dollars{4} + \dollars{2} + \dollars{1} = \dollars{7}$.

Naive Brute Force Solution

We can try enumerating every possible subset of items:

By rejecting all subsets above the weight limit ($\qty{15}{\kilo\gram}$) and getting the highest-value subset, we can clearly see that this will lead to an optimal solution. However, the runtime complexity is $O \parens{2^n}$.

Bottom-Up Tabulation Algorithm

Let:

• $W = {}$the bag’s carrying weight limit.
• $N = {}$the number of items we can choose from.
• $\braces{S_1, S_2, \dots, S_I} = {}$the set of all items we can choose from. (This intentionally uses one-based indexing.)
• $w_i = {}$the weight of item $S_i$.
• $v_i = {}$the dollar value of item $S_i$.

For this solution, we will assume integer weight values, $W \ge 0$, and $w_i \le W$ for all possible $w_i$.

Our main data structure will be a table $m \brackets{i, w}$ with size $\parens{N + 1} \times \parens{W + 1}$. For example:

$i$ corresponds to the subset of items we have currently selected from. For our example:

• $i = 0$ means we have selected from an empty set $\{\}$.
• $i = 1$ means we have selected from $\braces{S_1}$.
• $i = 2$ means we have selected from $\braces{S_1, S_2}$.
• $i = 3$ means we have selected from $\braces{S_1, S_2, S_3}$.
• $i = 4$ means we have selected from $\braces{S_1, S_2, S_3, S_4}$.
• $i = 5$ means we have selected from $\braces{S_1, S_2, S_3, S_4, S_5}$.

$w$ corresponds to hypothetical weight limits up until the weight limit $W$. For example:

• $w = 0$ corresponds to a bag of weight limit $\qty{0}{\kilo\gram}$,
• $w = 1$ corresponds to a bag of weight limit $\qty{1}{\kilo\gram}$,
• $w = 2$ corresponds to a bag of weight limit $\qty{2}{\kilo\gram}$, etc.

Each cell of $m\brackets{i, w}$ is the highest total dollar value possible for the given $i$ and $w$.

To fill the remaining cells, we must apply an optimal substructure. This can be expressed simply as:

(1) states the trivial case where choosing from zero items will always optimally total zero value. This lets us prefill zeroes in the first row as shown in the initial table above.

TODO: Make the table reference above clear? Original Latex version has an actual \cref{}.

(2) is a recursive equation based around a yes/no decision on whether or not to include an item in the bag. Importantly, this equation only references the previous row $i - 1$, meaning that we must calculate each row in order starting from $i = 1$. Without concerning ourselves with the details of the calculation, let’s fill out this first row $i = 1$:

Using the results of row $i = 1$, we can now calculate row $i = 2$:

…and so on.

To understand how equation (2) works and how we’ve been calculating these rows, let’s use the $i = 3$ row as an example since this is where things get more interesting:

Let’s take a closer look at how $\colorbox{\mylightblue}{$m \brackets{3, 5}$}$ is calculated. $m \brackets{3, 5}$ is the highest dollar value of a bag with a carrying capacity of $\qty{5}{\kilo\gram}$, selecting only from the set of items $\braces{S_1, S_2, S_3}$. If we apply equation (2), we get:

The last line (3) reads that we choose the best dollar value of two options:

• Option 1: We put item $S_3$ in the bag. To calculate this option, we are essentially taking the empty $\qty{5}{\kilo\gram}$ bag, putting item $S_3$ into it, and then asking for the best dollar value that we can put in the space that remains in the bag using only the previous items $\braces{S_1, S_2}$. The weight of item $S_3$ is $w_3 = \qty{2}{\kilo\gram}$, so the remaining space is $w - w_3 = 5 - 2 = \qty{3}{\kilo\gram}$.
• Option 2: We don’t put item $S_3$ in the bag. To calculate this option, we ask what the highest dollar value of a bag with a carrying capacity of the same $\qty{5}{\kilo\gram}$, except we select only from items $\braces{S_1, S_2}$.

Continuing on from (3):

This matches what is written in the cell.

Continuing until the whole table is complete, we get:

Thus, the best dollar value that we can put in a $\qty{15}{\kilo\gram}$ bag using items $\braces{S_1, S_2, S_3, S_4, S_5}$ is $\colorbox{\mylightgreen}{$m \brackets{5, 15}$} = \dollars{15}$.

To read back an optimal set of items, we must backtrack starting from $\colorbox{\mylightgreen}{$m \brackets{5, 15}$}$. The idea is to first look directly backwards to see if the weight is the same, otherwise we subtract the value and the weight and check the appropriate cell. If done correctly, we touch the following cells:

To understand how it works, let’s start from the beginning at $\colorbox{\mylightgreen}{$m \brackets{5, 15}$}$:

Directly behind $\colorbox{\mylightgreen}{$m \brackets{5, 15}$}$ is $\colorbox{\mylightblue}{$m \brackets{4, 15}$}$. Here, we check for one of two possible branches:

• Branch 1: If $\colorbox{\mylightgreen}{$m \brackets{5, 15}$} \ne \colorbox{\mylightblue}{$m \brackets{4, 15}$}$, then we know that our optimal set does contain item $S_5$. This is because the optimal set’s composition must have changed when we introduced the new item $S_5$.
• Branch 2: If $\colorbox{\mylightgreen}{$m \brackets{5, 15}$} = \colorbox{\mylightblue}{$m \brackets{4, 15}$}$, then we say that our optimal set does not necessarily contain item $S_5$. This is because the optimal set’s composition doesn’t need to have changed when we introduced the new item $S_5$.

(Side note: Branch 2 is carefully worded to say that it’s possible but uncertain that item $S_5$ can be included in the optimal set, but that we know for certain that it can be left out, hence we “say” that the optimal set does not necessarily contain $S_5$. It simplifies our discussion to skip over checking if we can include $S_5$.)

In this example, we see that $\colorbox{\mylightgreen}{$m \brackets{5, 15}$} \ne \colorbox{\mylightblue}{$m \brackets{4, 15}$}$, so we take item $S_5$ as part of the optimal set.

Now, depending on the branch, we will visit a new cell. This is simply the corresponding cell as described by equation (2):

• If we took Branch 1: We visit $m \brackets{i - 1, w - w_i}$. In this case, we visit $\colorbox{\mylightred}{$m \brackets{4, 14}$}$.
• If we took Branch 2: We visit $m \brackets{i - 1, w}$. In this case, we visit $\colorbox{\mylightblue}{$m \brackets{4, 15}$}$.

This process can repeat until we arrive at the $i = 0$ row.

Thus, we backtrack through the table:

• took Branch 1 at $m \brackets{5, 15}$,
• took Branch 1 at $m \brackets{4, 14}$,
• took Branch 1 at $m \brackets{3, 13}$,
• took Branch 1 at $m \brackets{2, 11}$, and
• took Branch 2 at $m \brackets{1, 7}$.

TODO: The original Latex version has a direct reference back to the backtracking table rather than just saying “the table”. Maybe we should figure out how to make this clearer here?

Therefore, our optimal set is $\braces{S_5, S_4, S_3, S_2}$, which has a total value of $\dollars{15}$.

This tabulation algorithm runs in $O\parens{NW}$ time and space. Further minor improvements to the algorithm are possible and is left as an exercise for the reader.

Naive Top-Down Recursion Algorithm

TODO: Write this section!

Top-Down Memoization Algorithm

TODO: Write this section!

References

• Wikipedia: The example and the mathematical notation was taken from here.
• GeeksforGeeks: Online practice problem.