Dynamic Programming: The Rod Cutting Problem

Input: You are given

length of rod L a natural number and

List sizes [l1, l2, .., lk] of possible lengths that we can cut the rod and
List prices how much money does each length of rod yield [p1, p2, .., pk]
Note: The sizes and prices list must have the same length.

Assumptions: k ≥ 1, L is positive whole number, li are all positive, whole numbers, and prices pi are positive.

Question: Why are they reasonable assumptions to make? What do we do if these assumptions do not hold? Ask us on the forum.

L = 100
sizes = [ 1, 3, 5, 10, 30, 50, 75]
prices = [ 0.1, 0.2, 0.4, 0.9, 3.1, 5.1, 8.2]

Optimal Substructure(Attempt 1)
Suppose we have length L left for now, we can decide on a possible cut now and then optimally solve for the remaining length of the
rod.

1. If we choose to cut li length now, that pays off pi revenue.

2. Then we can decide how to cut the remaining length L-li optimally.
3. Once we solve step (2), the solution for (1) simply appends a cut of length li before the decisions for (2) are carried out.

Thus, we see that the problem has optimal substructure property.

Defining a recurrence
Based on this, we define: maxRevenue(L) as the maximum revenue that can be obtained for length L of rod. Note that sizes and
prices are also arguments to this function but in this formulation they are going to remain fixed. So we do not list them explicitly.

First, we consider the actual recurrence and then write down the base cases (though this is the reverse of how we ought to do things,
technically speaking).

maxRevenue(L) = max

What are the base cases:

\text{maxRevenue}(L) = 0 whenever L= 0. If no rod to cut then nothing to do.

\text{maxRevenue}(L) = - \infty whenever L < 0. If there is negative rod to cut, we will "punish" the cutter infinitely.

Question: How can \text{maxRevenue}(\hat{L}) end up with an argument \hat{L} < 0? What is the physical meaning in terms of the
cutting a rod? Why is it OK to assign it to -\infty? If you are unable to grok these, ask us on piazza.

# Naive Attempt to Implement the Recurrence

def maxRevenue_Recursive(L, sizes, prices):

if L == 0:
return 0
if L < 0:
return (-100000000) # Just a large negative number will do
k = len(sizes)
assert len(prices) == k
# Let us implement the max of
optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
[Link](0) # also add 0 to cover the case where we waste
bestValueSoFar = max(optionValues)
return bestValueSoFar

# WARNING: Will run for a long time

print(maxRevenue_Recursive(30, sizes, prices))

3.1

# WARNING: Will run for a really long time

print(maxRevenue_Recursive(50, sizes, prices))

---------------------------------------------------------------------------
KeyboardInterrupt Traceback (most recent call last)
<ipython-input-16-2681916da924> in <module>()
 1 # WARNING: Will run for a really long time
----> 2 print(maxRevenue_Recursive(50, sizes, prices))

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
 10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
 9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)
<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in <listcomp>(.0)
9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

<ipython-input-4-d11013c46a8d> in maxRevenue_Recursive(L, sizes, prices)

9 assert len(prices) == k
10 # Let us implement the max of
---> 11 optionValues = [ (prices[i] + maxRevenue_Recursive(L-sizes[i], sizes, prices)) for i in range(k) ]
12 [Link](0) # also add 0 to cover the case where we waste
13 bestValueSoFar = max(optionValues)

KeyboardInterrupt:

Memoization
The recurrences above take too long, unfortunately. Are you wondering why? If so, just add a print statement to see what values of L are
being called. You will find that the same values of L are being called repeatedly billions of time. This causes lots of unnecessary work that
can be avoided through Memoization.

In memoization, we will simply store the results for previously computed lengths so that we can simply retrieve them from our store. To do
so we will use a memo table T.

T[0], ..., T[L] will store the values of maxRevenue for lenghts 0 to L. In particular, T[0] = 0 by the base case.

def maxRevenue_Memoize(L, sizes, prices):

T = [0]*(L+1) # create an array of size L+1 and fill it with all 0s
k = len(sizes)
assert len(prices) == k

for l in range(1, L+1):

optionValues = [ (prices[i] + T[l-sizes[i]]) for i in range(k) if l - sizes[i] >= 0 ]
[Link](0)
T[l] = max(optionValues)
return T[L]

print(maxRevenue_Memoize(30, sizes, prices))

3.1

print(maxRevenue_Memoize(50, sizes, prices))

5.1000000000000005

print(maxRevenue_Memoize(300, sizes, prices))

32.8

Recovering The Solution

 The last step is to recover the actual solution instead of just the overall value.

The key is to not just record the maximum but also to record for each l , which choice yields the maximum

def maxRevenue_Memoize_With_Solution_Recovery(L, sizes, prices):

T = [0]*(L+1) # create an array of size L+1 and fill it with all 0s
S = [-1] * (L+1) # create an array to also record the best option for each l
# let us use -1 for the "waste" option
k = len(sizes)
assert len(prices) == k

for l in range(1, L+1):

T[l] = 0
# compute the value for each cut with the corresponding cut
optionsWithSolutions = [(prices[i] + T[l-sizes[i]], i) for i in range(k) if l - sizes[i] >= 0]
[Link] ((0, -1)) # also keep the option of wasting
# The above code is in python using comprehensions.
# if you are a python newbie still, this is equivalent code below
## BEGIN ALTERNATIVE CODE
# bestOptionSoFar = -1 # Let us us -1 for the waste option
# for i in range(k): ## Iterate through all options
# li = sizes[i]
# if l - li >= 0:
# option_value = prices[i] + T[l - li]
# if option_value > T[l]:
# T[l] = option_value
# bestOptionSoFar = i
#S[l] = bestOptionSoFar
(T[l], S[l]) = max(optionsWithSolutions) # max of a tuple compares lexicographically
# Now for solution recovery
cuts = []
l = L
while l > 0:
option_id = S[l] # Which option gave the best result for l?
if option_id >= 0: # If it is an option that involves a cut
[Link](sizes[option_id]) # Add the cut to the list
l = l - sizes[option_id] # Reduce the remaining size
else:
break # If best option is to waste, then we are done
return T[L], (cuts) # Returen max revenue and list of cuts

print(maxRevenue_Memoize_With_Solution_Recovery(30, sizes, prices))

(3.1, [30])

print(maxRevenue_Memoize_With_Solution_Recovery(50, sizes, prices))

(5.1000000000000005, [30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

print(maxRevenue_Memoize_With_Solution_Recovery(100, sizes, prices))

(10.7, [75, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

print(maxRevenue_Memoize_With_Solution_Recovery(130, sizes, prices))

(13.8, [75, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

print(maxRevenue_Memoize_With_Solution_Recovery(300, sizes, prices))

(32.8, [75, 75, 75, 75])

print(maxRevenue_Memoize_With_Solution_Recovery(1330, sizes, prices))

(145.00000000000003, [75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 30, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 75, 75, 1])

A Different Approach To Formulating the Recurrence

Previously, we staged the cuts to be made at each step by considering all possible options available and looking at the optimal way of
handling the remaining length. Note however, that this results in the same cut being repeated multiple times. Perhaps instead of saying
[1,1,1,1,1,1,1,1,1, 30, 30] , we could say make cuts of 1 unit length 9 times, and 30 unit length 2 times. This could
be even more efficient and yields a different way of thinking about this problem.

we have lengths [l1, ..., lk] and prices [p1, ..., pk] . First let us consider the length l1 and make a decision on how
many cuts of length l1 should be made. If L is the current rod length, we can consider making k_1 = 0, \ldots, \lfloor \frac{L}{l_1}
\rfloor cuts of length l1 . The remaining sub problem will have lengths [l2,..., lk] , prices [p2, .. , pk] and remaining rod
length will be L - k1 * l1

This way of looking at things leads us to a different recurrence:

Let \text{maxRevenue}(L, i) denote the maximum revenue we obtain if the current remaining length is L and we are allowed to look at
lengths from [li, ..., lk] and prices [pi, ... , pk] . Here L is a positive number and i ranges from 1 to k+1 .

Let us first write down the recurrence and then the base case:

\text{maxRevenue} (L, i) = \left\{ \begin{array}{ll} 0 & \leftarrow \text{Waste the current length} \\ \text{maxRevenue}(L, i+1) & \leftarrow\
\text{Apply the length}\ l_i\ \text{0 times} \\ p_i + \text{maxRevenue}(L - l_i, i+1) & \leftarrow\ \text{Apply the length}\ l_i\ \text{1 times} \\
\vdots & \vdots \\ k_i p_i + \text{maxRevenue}(L - k_i l_i, i+1) & \leftarrow\ \text{Apply the length}\ l_i\ k_i\text{times} \\ \end{array}\right.

Wherein k_i = \left\lfloor \frac{L}{l_i} \right\rfloor.

The base cases are

\text{maxRevenue}(0, j) = 0, the rod has entirely been cut.

\text{maxRevenue}(L, k+1) = 0, if L > 0 since we do not have any possible lengths left to consider.
\text{maxRevenue}(L, j) = -\infty , if L < 0.

def maxRevenueNew(L, j, prices, sizes):

k = len(prices)
assert len(sizes) == k
if L == 0:
return 0
if L < 0:
return - 1000000
if j >= k: # Note that pseudocode array indices are from 1 to k. Python indices are 0 to k-1
return 0
ki = L // sizes[j]
if ki <= 0:
return 0
lstOfOptions = [ (i * prices[j] + maxRevenueNew(L-i*sizes[j], j+1, prices, sizes)) for i in range(ki+1) ]
return max(lstOfOptions)

# It is now much faster than before :-)

maxRevenueNew(30, 0, prices, sizes)

3.1

maxRevenueNew(50, 0, prices, sizes)

5.1

maxRevenueNew(100, 0, prices, sizes)

10.7

# But it should be sped up even further

maxRevenueNew(300, 0, prices, sizes)

32.8

Memoization
To speed up the maxRevenue recurrence, we design a new memo table T with rows labeled l = 0, \ldots, L and columns j = 1, \ldots, k+1.

\begin{array}{|c|l|l|l|l| l| } \hline & j=1 & j=2 & \cdots & j=k & j=k+1 \\ \hline l=0 & 0 & 0 & \cdots & 0 & 0 \\ \hline l=1 & & & \cdots & & 0 \\
\hline \vdots & & & \ddots & & 0 \\ \hline l=L & ? & & \cdots & & 0 \\ \hline \end{array}

The problem seeks the value for l = L and j = 1. The corresponding cell is marked with a ? in the figure above. Once we fill this cell, the
value can be returned as the solution.

Note that each cell (l, j) depends on the value of cells (\hat{l}, j+1) where \hat{l} < l. These values need to be computed before we are
able to compute the value for (l,j). Therefore, we start to fill the cells from l = 0, \ldots, L and j = k+1, \ldots, 0 i.e, right to left and top to
bottom.

def maxRevenueNew_Memoize(L, sizes, prices):

k = len(sizes)
assert len(prices) == k
# Build a two dimensional tbl in python
# The entire table is filled with zeros
tbl = []
# Also record which option is best to reconstruct solution
sol = []
for i in range(L+1):
[Link]([0]*(k+1))
[Link]([-1]* (k+1))
 for l in range(L+1):
for j in range(k-1, -1, -1): # Iterate from k-1 down to 0
ki = l // sizes[j]
valuesToConsider = [ ((i * prices[j] + tbl[ l-i*sizes[j] ][j+1]), i) for i in range(ki+1) ]
[Link]((0, -1))
(val, option_id) = max(valuesToConsider)
tbl[l][j] = val
sol[l][j] = option_id
# Now retrieve the solution
cuts = []
l = L
j = 0
while l > 0 and j < k:
option_id = sol[l][j]
if option_id == -1:
break
if (option_id > 0):
[Link]('Cut length = %d , %d times' % (sizes[j], option_id))
l = l - option_id * sizes[j]
j = j + 1
return tbl[L][0], cuts

maxRevenueNew_Memoize(30, sizes, prices)

(3.1, ['Cut length = 30 , 1 times'])

maxRevenueNew_Memoize(50, sizes, prices)

(5.1, ['Cut length = 1 , 20 times', 'Cut length = 30 , 1 times'])

maxRevenueNew_Memoize(111, sizes, prices)

(11.899999999999999,
['Cut length = 1 , 6 times',
'Cut length = 30 , 1 times',
'Cut length = 75 , 1 times'])

maxRevenueNew_Memoize(300, sizes, prices)

(32.8, ['Cut length = 75 , 4 times'])

maxRevenueNew_Memoize(3124, sizes, prices)

(341.2,
['Cut length = 1 , 19 times',
'Cut length = 30 , 1 times',
'Cut length = 75 , 41 times'])