Sinead is an expert sandwich maker. Her sandwich palace smell of freshly baked bread and is devoted to fulfilling your hunger. The sandwiches come in 3 different sizes. The 10 cm sandwich cost 3 Euros, the 20 cm sandwich cost 5 Euros and the 30 cm sandwich cost 10 Euros. Sinead bakes her bread every day, and the length of the baguettes varies. They are typically 50 cm, 60 cm, or 70 cm. Conscientious of wasting less and making the most profit, Sinead got thinking about how she can run her operation better. She is trying to figure out what is the best way to cut baguettes to make sandwiches. Can we help her with some computer science?
According to ingredients and market prices, this is the table of fees per sandwich length:
| Length (cm) | 0 | 10 | 20 | 30 | 40 | 50 | 60 | 70 |
|---|---|---|---|---|---|---|---|---|
| Price (Euros) | 0 | 3 | 5 | 10 | 12 | 14 | 16 | 18 |
For example, a 10 cm sandwich cost 3 Euros and a 20 cm, cost 5 Euros. Would you buy a 70 cm sandwich? I think I would if I were starving and wanted to have it for lunch and dinner. Having those enormous sandwiches prices is absurd, but you will that it comes handy at some point.
The smallest sandwich length acceptable is 10 cm. Sinead is looking for the best way to cut a baguette to maximise her profits. How should she cut a 50 cm baguette? What about a 60 cm and a 70 cm one?
The following image shows all the different cuts for a 50, 60 and 70 cm baguette. Each cut is a multiple of 10. As you can see, there are many possibilities.
Our goal is to find the best cut for a 50, 60 or 70 cm baguette. Let first solve the problem of finding the best profit that we can make with a 10 cm baguette. When the length is 10 cm, we already have the answer because we can’t divide it anymore. The maximum profit for a 10 cm baguette is 3 Euros.
# 0 10 20 30 40 50 60 70 cm
prices = [0, 3, 5, 10, 12, 14, 16, 18]
best_profit_1 = prices[1]
When the length is 20, we can either keep it as it is or split it in 2. The profit is either 5 euros or 3 + 3 = 6 euros. The maximum profit for a 20 cm baguette is then 6 (split it in 2).
best_profit_2 = max(
prices[1] + best_profit_1,
prices[2]
)
For length equals 30, we have to choose between: 3 or 2 + 1 or 1 + 1 + 1. As we already calculated the maximum profit for 20, we can reuse the formula.
best_profit_3 = max(
prices[1] + best_profit_2,
prices[2] + best_profit_1,
prices[3]
)
For length equals 40, we have to choose between: 4 or 3 + 1 or 2 + 2 or 2 + 1 + 1 or 1 + 1 + 1 + 1. As we calculated earlier the maximum profit for 20 and 30 we can reuse the formulas.
best_profit_4 = max(
prices[1] + best_profit_3,
prices[2] + best_profit_2,
prices[3] + best_profit_1,
prices[4],
)
Do you see the pattern? We reuse the values of smaller lengths. Let’s see if we can wrap this in a for loop for length equals 50 cm.
best_profits = [
0,
best_profit_1,
best_profit_2,
best_profit_3,
best_profit_4
]
best_profit_5 = 0
for i in range(1, 6):
best_profit_5 = max(
best_profit_5, prices[i] + best_profits[5 - i]
)
For length equals 60 cm, let’s try creating a reusable function that wraps that in a for loop.
best_profits = [
0,
best_profit_1,
best_profit_2,
best_profit_3,
best_profit_4
best_profit_5
]
def best_profit_for_l(prices: List[int], l: int) -> int:
# This function will not work for length inferior to 1.
if l < 1:
return 0
best_profit_l = -1
for i in range(1, l + 1):
best_profit_l = max(
best_profit_l,
prices[i] + best_profits[l - i]
)
return best_profit_l
best_profit_for_l(prices, 6)
This solution requires us to prepopulate the best_profits list. Maybe we don’t need to do that thanks to recursion. Indeed best_profit_5 was calculated with best_profit_l(prices, 5), best_profit_4 was calculated with best_profit_l(prices, 4) and so forth. Instead of using the list of precomputed values, we can recursively execute the function.
def best_profit_for_l(prices: List[int], l: int) -> int:
# This function will not work for length inferior to 1.
if l < 1:
return 0
best_profit_l = -1
for i in range(1, l + 1):
best_profit_l = max(
best_profit_l,
prices[i] + best_profit_for_l(prices, l - i)
)
return best_profit_l
best_profit_for_l(prices, 7)
This algorithm uses recursion to calculate the best profit of a given length by calculating the best yield of smaller baguette: it operates in a top-down manner. Below is the final top-down recursive algorithm.
def top_down_recursive(prices: List[int], l: int) -> int:
if l < 1: # base case
return 0
best_profit_l = -1
for i in range(1, l + 1):
best_profit_l = max(
best_profit_l,
prices[i] + top_down_recursive(prices, l - i)
)
return best_profit_l
This animation shows the recursive call of the above function top_down_recursive([0, 3, 5, 10, 12, 14, 16, 18], 3).
Each node is a subproblem. We can see from the tree that there is duplicate work done. For example, we are doing four times the computation for length equals one decimetre (10 cm) and, two times the computation for length equals two decimetres (20 cm). On a more significant problem, there will be even more duplication, which will make the algorithm not efficient. How can we save ourselves from doing this extra work? We can use a technique called memoization.
Memoization is a technique where we cache and reuse previous computations. If we already calculated the best profit for a specific length, we reuse the result. Otherwise, we compute it and save it for later.
Let’s say we have a function called do_calculation(value), this is how we would add memoization:
memo = [-1] * 10 # initialise an array of length 10 with a value of -1
if memo[value] > -1:
# We already computed the best profit for this length.
return memo[value]
else:
result = do_calculation(value)
memo[value] = result # Save for next time!
Let’s add this to our previous code!
def top_down_recursive_with_memo(prices: List[int], l: int) -> int:
memo = l * [-1]
memo[0] = 0
def memoized(prices: List[int], l: int) -> int:
if memo[l - 1] < 0:
memo[l - 1] = top_down_recursive(prices, l)
return memo[l - 1]
return memoized(prices, l)
This animation shows the recursive steps of the above function call recursive_cut_with_memo([0, 3, 5, 10, 12, 14, 16, 18], 3). Compare it with the previous one. You will see that the call tree is smaller. There is less recursion because we reuse results.
Great, we found a way to get the best profit by baguette length and talked about optimising it with memoization. Let’s execute our code to get the best profits.
>>> prices = [0, 3, 5, 10, 12, 14, 16, 18]
>>> top_down_recursive_with_memo(prices, 5)
16
>>> top_down_recursive_with_memo(prices, 6)
20
>>> top_down_recursive_with_memo(prices, 7)
23
Our baker is happy with these answers but remembers that we also wanted to get the cutting pattern. How should we split the baguette to arrive at these numbers? Let’s see how we can do that in the next section.
The previous solutions use a top-down approach. Remember we were using recursion because we needed the answer for smaller lengths. Could we reverse it by using a bottom-up approach? First, calculate the solution for a shorter length and then arrive at the desired length. Let’s translate the previous code in a non-recursive fashion.
Changing the direction and angle with whom you solve a problem is an efficacious trick. See the Inversion principle
The plan is to start with the smallest length and reuse the solution when dealing with longer baguette. By comparing every combinations we will find which cut lead to the best profit.
Let’s list the different combinations for each length:
The best profit is given by using the best combination:
Let’s replace values by their variables:
We can spot a relation here which we can turn into code.
>>> length = 4
>>> cuts = []
>>> for l in range(1, length + 1):
>>> for m in range(1, l + 1):
>>> r = l - m
>>> cuts.append((m, r))
>>>
>>> print(cuts)
[(1, 0), (1, 1), (2, 0), (1, 2), (2, 1), (3, 0), (1, 3), (2, 2), (3, 1), (4, 0)]
Based on those two for loops, we can add the code that will calculate the profit for a given length and store it for later use. We pre-calculate the solution for smaller baguette, knowing that we will reuse them for longer ones.
We store the best profit for each length in the best_profit_for_length list. This list is initially set with -1. Additionally, we store which cut led to the best profit in the solutions list.
def bottom_up_tabulation(prices: List[int], length: int) -> Tuple[List[int], List[int]]:
best_profit_for_length = (length + 1) * [-1] # Table of best profit by length.
best_profit_for_length[0] = 0 # When length = 0, the profit is 0.
solutions = (length + 1) * [0]
for l in range(1, length + 1):
for m in range(1, l + 1):
profit_l = prices[m] + best_profit_for_length[l - m]
if profit_l > best_profit_for_length[l]:
best_profit_for_length[l] = profit_l
solutions[l] = m
return best_profit_for_length[length], solutions
After executing the above function with bottom_up_tabulation(prices, 7) this is how the best_profit_for_length and solutions lists look like in the end:
| length (decimetre) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| best_profit_for_length | 0 | 3 | 6 | 10 | 13 | 16 | 20 | 23 |
| solutions | 0 | 1 | 1 | 3 | 1 | 1 | 3 | 1 |
From this table we can read (using the best_profit_for_length row):
Good news, the results are the same as the recursive version of the algorithm. We now have this bottom-up algorithm that gives us the best profit for any length. We stored the results of computations in a table to reuse them later. This bottom-up method of storing intermediate results is a process called tabulation.
Remember that our baker also wanted the cutting patterns. Thanks to the tabulation we can find this answer quickly. Remember how we stored the best cut for a particular sub-length? We can read the table backwards to find the cutting pattern.
The solutions list contains our answer!
| length (decimetre) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| best_profit_for_length | 0 | 3 | 6 | 10 | 13 | 16 | 20 | 23 |
| solutions | 0 | 1 | 1 | 3 | 1 | 1 | 3 | 1 |
From this table we can read (using the solutions row) the best way to cut a baguette:
For a 70 cm baguette (length equals seven decimetres). First cut one decimetre. You are left with 60 cm. The sixth column tells you to now cut 30 cm from the remaining 60. You are left with 30 cm. The third column tells you to stop here and not subdivide anymore.
The optimal cutting pattern for a 70 cm is then: 10 cm, 30 cm, 30 cm.
Now that we know how to read the table to find the cutting pattern, we can implement it in code. The algorithm to find the solution from the solutions array loops over and subtract values. A while loop can help us here:
>>> pattern = []
>>> rest = 7 # decimetre
>>> while rest > 0:
>>> pattern.append(solutions[rest])
>>> rest -= solutions[rest]
>>>
>>> print(patter)
[1, 3, 3]
Let’s incorporate that in the final code with a function called get_best_profit_and_cut_pattern.
def bottom_up_tabulation(prices: List[int], length: int) -> Tuple[List[int], List[int]]:
best_profit_for_length = (length + 1) * [-1] # Table of best profit per length.
best_profit_for_length[0] = 0 # When length = 0, the profit is 0.
solutions = (length + 1) * [0]
for l in range(1, length + 1):
for m in range(1, l + 1):
profit_l = prices[m] + best_profit_for_length[l - m]
if profit_l > best_profit_for_length[l]:
best_profit_for_length[l] = profit_l
solutions[l] = m
return best_profit_for_length, solutions
def get_best_profit_and_cut_pattern(prices: List[int], length: int) -> Tuple[int, List[int]]:
best_profit_for_length, solutions = bottom_up_tabulation(prices, length)
pattern = []
rest = length
while rest > 0:
pattern.append(solutions[rest])
rest -= solutions[rest]
return best_profit_for_length[length], tuple(pattern)
Let’s try executing this function:
>>> prices = [0, 3, 5, 10, 12, 14, 16, 18]
>>> get_best_profit_and_cut_pattern(prices, 7)
(23, (1, 3, 3))
>>> get_best_profit_and_cut_pattern(prices, 6)
(20, (3, 3))
>>> get_best_profit_and_cut_pattern(prices, 5)
(16, (1, 1, 3))
That’s all! We finally solved the problem. For a given baguette size we can find out the best profit you can expect and the best way to subdivide it.
The answer for our baker is:
The problem we just solved is an interpretation of the famous rod-cutting problem. When we are working with a limited quantity of things and trying to maximise or minimise something were, are dealing with an optimisation problem. The quantity to maximise or minimise could be, for example, cost, waste, or profit. Dynamic programming is a technique to solve such problems and avoid repeating work. To solve a problem with dynamic programming, it must have two properties:
Dynamic programming was invented by Richard Bellman in the 1950s and has since been applied to various industries and problems. In my opinion, the name dynamic programming is somewhat complicated and doesn’t convey much meaning. Wikipedia has some insights on the origin of the name . The word dynamic makes me think that we are talking about an algorithm that has moving parts. It doesn’t operate linearly. It goes back and forth.
We helped the bakery solve their optimisation problem by using several mental models and techniques. Here is a recapitulation.
Dynamic programming is different from Divide And Conquer. Both technique help to solve problems by solving smaller subproblems first and combining them later. Dynamic programming differs by two requirements: the problem has overlapping subproblems, and an optimal solution can be found by using the optimal solutions of subproblems. For example, with Quicksort, the famous divide and conquer sorting algorithm, we split the list of numbers iteratively. Those smaller lists (subproblems) are not overlapping: it’s unlikely that many sub-lists are identical.
Recursion is a natural tool when dealing with divide and conquer problems. Recursion is a top-down approach. Dynamic programming can help making recursive problems with many overlapping subproblems more efficient.
The tabulation method is a bottom-up technique where we iteratively fill a table with results of subproblems until we reach the main problem. The values in the table are reused through the computation. One drawback of tabulation is that some subproblems will be solved even though they might not be reused.
Memoization is a technique of caching and reusing the results of previous computations. Adding memoization to a function is easy.