Rod-Cutting Problem using dynamic programming

Question

I wrote the following code for solving the Rod-Cutting Problem using dynamic programming:

Rod Cutting Problem: Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces and also find the size of the pieces to be cut.

import random

prices = {x:random.randrange(x, 2*x) for x in range(1,101)}

def find_optimum_revenue(length, prices, memo={}):
    '''This function finds the maximum possible revenue
       that can be generated by cutting a rod of
       length = length and the prices for each rod of length n
       is stored in prices such that prices[n] finds the price
       of the rod.'''

    if length == 1: # Base Case: You can't cut a rod of length == 1
        return prices[1]

    elif length in memo:
        return memo[length]

    else:
        # The first list will contain all the possible revenues after
        # cutting the rod. We add the list [prices[length]] to add the
        # possibility that we may sell the rod as is and not cut it.

        possible_revenues = [find_optimum_revenue(half, prices, memo) + \
                            find_optimum_revenue
                             (length - half, prices, memo) \
                    for half in range(1, length//2+1)] + [prices[length]] 

        memo[length] = max(possible_revenues) # Saving in dictionary for future use
        return memo[length]

get_price = lambda pieces: sum(prices[rod] for rod in pieces)

def find_optimum_cuts(length, prices, memo={}):
    '''This function finds the length of pieces to be cut so
       as to generate the maximum revenue that can be generated
       by cutting a rod of length = length and the prices for
       each rod of length n is stored in prices such that prices[n]
       finds the price of the rod.'''

    if length == 1: # Base Case: You can't cut a rod of length == 1
        return (1,)

    elif length in memo:
        return memo[length]

    else:
        # The first list will contain all the possible revenues after
        # cutting the rod. We add the list [prices[length]] to add the
        # possibility that we may sell the rod as is and not cut it.

        best_cuts = [find_optimum_cuts(half, prices, memo) + \
                    find_optimum_cuts(length - half, prices, memo) \
                    for half in range(1, length//2+1)] + [(length,)]

        memo[length] = max(best_cuts, key=get_price) # Saving in dictionary for future use
        return memo[length]

print(find_optimum_revenue(100, prices))
print(find_optimum_cuts(100, prices))

It works correctly for all the test cases I have tried and is not broken. The first function finds the maximum revenue and the second the pieces to be cut. I am thinking of merging them as it would save time. The prices list contains the prices of different sizes of rods. Is it possible to reduce the time and memory consumption and make the code better and more Pythonic? Also, can you please tell me its time complexity? I believe it to be \$O(n^2)\$ but I am not sure.

Answer 1

I rather like your memo parameter. It makes for a faster function. If you are interested, Python 3.2 added the functools.lru_cache function that is used as a decorator and accomplishes the same thing as your memo.

Since possible_revenues is used just to find its max value, it would be more efficient to use a generator expression because the values are generated on demand instead of all being stored in memory. To do that, simply change [ and ] to ( and ). edit: you would also need to change from ... + ... to itertools.chain(..., ...), importing itertools of course. When you have an open bracket (any kind, {[(), the logical line continues until it is closed. Because of that, you don't need the backslash at the end of the line. I would also suggest that you put the open parenthesis for the second call to find_optimum_revenue() on the same line as the function name. When I first saw those lines, it looked like you had used a variable and a tuple, but forgot to put a comma between them.

lambda functions are meant to be used where it would be awkward to define a function. For example, you could use a lambda as an argument to sorted(). It is helpful because you don't need to go through the whole def line just for a one-time-use function. If you are giving a name to a lambda function, that is a sign that it is not just a simple pass-it-to-another-function deal. Naming lambdas is actually against PEP 8, the Python style guide. Instead, use a def line. If not for the reasons above, using def makes it easier to search for it. If I want to search for a function definition, I search for "def function_name(". It would be hard to remember which functions were defined formally, and which were lambdas.

Answer 2

Your docstrings are more like paragraphs that run on. Python has good guidelines for docstrings that are worth looking up. But the basic idea is to try keep it short and direct rather than descriptive. And you should have a singular summary on one line first, before the further details. Here's how find_optimum_revenue could look:

"""Return maximum possible revenue from length sized rod given prices.

Cached values are stored in memo.
Finds the maximum value based on all the possible cuts of the rod."""

You don't need the backslashes for defining your possible_revenues list. Since they're enclosed in your [], the line breaks will be ignored when the expression is being read. I'd also separate out adding prices[length] for readability. You can then have two shorter comments split out this way:

    # All possible revenues from cutting the rod
    possible_revenues = [find_optimum_revenue(half, prices, memo) + 
                         find_optimum_revenue(length - half, prices, memo)
                         for half in range(1, length//2+1)]
    # Possible revenue from full length uncut rod
    possible_revenues.append(prices[length])

I would personally change the flow too, to this:

if length == 1:
    return prices[1]

elif length not in memo:
    # determine max values

return memo[length]

It's a small thing, but it saves having two return memo[length] lines and makes it clearer that you're only doing the calculation if the value isn't cached.