CODEWITHSUNDEEP
pythonalgorithm
zsljulius
zsljulius

Reputation: 4123

recursion confusion - rod cutting algorithm

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

Answers (1)

Martijn Pieters
Martijn Pieters

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

Related Questions