Rod Cutting

Here is the Rod-Cutting Problem implemented in Python:

def rod_cut(arr,length):
    gain = [ 0 for x in xrange(length+1)]
    pos  = [ 0 for x in xrange(length+1)]

    for l in xrange(1,length+1):
        q = -10
        for j in xrange(1,l+1):
            if q < arr[j] + gain[l-j] :
                q = arr[j] + gain[l-j]
                pos[l] = j
        gain[l] = q

    print "The total optimal gain: %s"%(gain[length],)
 
    a = ""
    while pos[length] != 0:
        a = a+str(pos[length])+" "
        length = length - pos[length]
     
    print "Cut at lengths: " + a


# Test case:

l = [0,1,5,8,9,10,17,17,20,24,30]
rod_cut(l,9)