Reputation: 4123
I am trying to implement the rod cutting algorithm illustrated in CLRS, but I find myself having a hard time getting the indices correct. Here is my implementation of the memoization version:
import sys
def rod_cutting_memoization(p,n):
r = [None for i in range(n+1)]
r[0] = 0
rod_cutting_memoization_aux(p,n,r)
return r
def rod_cutting_memoization_aux(p,n,r):
print r
if r[n] is not None:
return r[n]
if n is 0:
return 0
else:
q = -100
for i in range(n):
q = max(q, p[i] + rod_cutting_memoization_aux(p,n-i-1,r))
r[n] = q
p=[1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
n = int(sys.argv[1])
print rod_cutting_memoization(p,n)
Starting from n=2, the code is saying int + None. The pseudo code in the book was written with index staring from 1. I always have this issue with converting algorithm with indexing from 1 to 0. Is there a general approach to solve this?
Upvotes: 2
Views: 458
Reputation: 1125398
Your recursive rod_cutting_memoization_aux()
function only returns values for r[n] is not None
and for n == 0
. If neither of those conditions is True
, then the function just ends without an explicit return
, which means None
is returned instead.
This means that the line:
q = max(q, p[i] + rod_cutting_memoization_aux(p,n-i-1,r))
will try to sum p[i]
with None
for some values of p, n - i - 1, r
.
You need to return something other than None
from the recursive call to prevent this; presumably an integer needs to be returned.
Upvotes: 2