Dynamic Programming solution to the rod cutting problem http://faculty.ycp.edu/~dbabcock/PastCourses/cs360/lectures/lecture12.html

rod_cutting.py

from collections import namedtuple
from itertools import combinations

Rod = namedtuple('Rod', ['length', 'price', ])


def optimal_price(rods,total_length=20):

    zero_rod = Rod(length=0,price=0)
    if total_length > len(rods):
        zero_rods = [zero_rod for rod in range(total_length-len(rods))]

    rods.extend(zero_rods)

    all_rods = [zero_rod]
    all_rods.extend(rods)

    subproblem_prices = [rod.price for rod in all_rods]

    for i in range(1, len(all_rods)):
        print "------- Iteration: {} ---------".format(i)
        if i % 2 == 1:
            loop_range = (i+1)/2
        else:
            loop_range = (i+1)/2 + 1

        max_price = 0
        for j in range(loop_range):
            print "{} - {}".format(j, i-j)
            i_j_price = subproblem_prices[j] + subproblem_prices[i-j]
            if i_j_price > max_price:
                max_price = i_j_price

        subproblem_prices[i] = max_price


    return subproblem_prices


def run():
    values = [(1,1), (2,5), (3,8), (4,9), (5,10), (6,17), (7,17), (8,20), (9,24), (10,30)]
    rods = [Rod(length=i, price=j) for i, j in values]

    return optimal_price(rods, 1000)