5
\$\begingroup\$

I tried to learn dynamic programming going from recursion to memoized version with the RodCutting problem: Returns the best obtainable price for a rod of length n and price[] as prices of different pieces.

Have you any suggestions on the code (or the way to make test), i tried to keep as simple and generic to mimic on others similar problems (i could have erase the n from input and calculate inside the function but it would confuse the solution).


"""
Inspiration of DP from: https://wellsr.com/python/optimizing-recursive-functions-with-python-memoization/
"""

def cutRod(price, n):
    """
    Returns the best obtainable price for a rod of length n
    and price[] as prices of different pieces
    """
    res = price[n-1] # One piece without cut
    for i in range(n-1):
        res = max(res,price[i]+cutRod(price,n-(i+1))) #i+1 cut
    return res

def cutRodMemo(price, n):
    """
    Returns the best obtainable price for a rod of length n
    and price[] as prices of different pieces
    """
    # 1.Define memo table
    memo = [None]*n
    memo[0] = price[0]
    # 2.Memoize recursive approach
    def cutRodAux(price,n,memo):
        if memo[n-1]:
            return memo[n-1]
        res = price[n-1]
        for i in range(n-1):
            res = max(res,price[i]+cutRodAux(price,n-(i+1),memo)) 
        memo[n-1]= res
        return res
    return cutRodAux(price,n,memo)





if __name__ == '__main__':
    import unittest
    f = cutRod

    class Test(unittest.TestCase):
        def test(self): 
            args = [(([10,24,30,40],4),48),
                      (([1, 5, 8, 9, 10, 17, 17, 20],8),22)
                    ]
            for i,o in args:
                prices,size = i
                self.assertEqual(cutRod(prices,size), o)
                self.assertEqual(cutRodMemo(prices,size), o)
         
    unittest.main()

    
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  1. Don't put tests in the same file as the main script
  2. f = cutRod - f seems unused
  3. Defining a function right in the middle of another one isn't very pretty. Move it up to the beggining or preferrably make a separate function altogether.
  4. Removing n from the input would actually be a good idea as right now you are providing redundant information.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.