How to Solve Cutting Rod Problem

This solution uses memoization.

#!/usr/bin/env python

def find_max(list_tuples):
    if len(list_tuples) == 0:
        return None
    maximum = list_tuples[0]
    for i in xrange(1, len(list_tuples)):
        if maximum[0] < list_tuples[i][0]:
            maximum = list_tuples[i]
    return maximum

memo = {}
def cutting_rod(prices, ncuts):
    if ncuts == 0:
        return (0, [])
    if ncuts in memo:
        return memo[ncuts]
    tmp = []
    for i in xrange(0, ncuts):
        r = cutting_rod(prices, ncuts-i-1)
        new_list = list(r[1])
        new_list.append(i)
        value = prices[i] + r[0]
        tmp.append((value, new_list))
    result = find_max(tmp)
    memo[ncuts] = result
    return result

if __name__ == '__main__':
    p = [2, 5, 6, 7]
    r = cutting_rod(p, len(p))
    print "Prices:", p
    print "Optimal value:", r[0]
    print "Indices:", r[1]
    print "Cuts:", [p[x] for x in r[1]]

Output:

Prices: [2, 5, 6, 7]
Optimal value: 10
Indices: [1, 1]
Cuts: [5, 5]