Dynamic Programming - Rod Cutting while keeping tab on indices at which the cut was made

Question

In the classical rod-cutting Dynamic programming problem - where do I make cuts on a rod of lenght n to maximize the price I obtain by selling either the full rod, or parts of it thereof. See also, problem statement here for details -Understanding the bottom-up rod cut implementation

How do I keep a tab of the indices - ie where in the original rod did I make the cuts ? I don't seem to have a fair understanding of knowing how to keep indices at which the rod was eventually cut. Here is my code -:

# price is dict of revenue we get for the corresponding rod-length
price={1:1,2:5,3:8,4:9,5:10,6:17,7:17,8:20,9:24,10:30}

def cut_rod(n,price):
    if n==0:
        return 0
    revenue=-999
    for i in range(1,n+1): 
  ##I do this, since my price[1] ie the keys to the price dictionary start from 1...n
        revenue=max(revenue,price[i]+cut_rod(n-i,price))
    return revenue

n=4 # print the maximum revenue we earn for rod of length 4
revenue=cut_rod(n,price)
print "revenue for rod of length %d is %d" %(n,revenue)

For the rod of length 4, I make cuts on 2 and 2 (ie midway) - how we do memorize these indices ?

Edit : I have an approximate idea that I need to keep tab of all revenues seen so far, with the corresponding cut locations - but I just seem to get lost in the main call - should I be storing this between the subsequent calls in a dict structure and just look it up later. I also think that the indices will be a dict(for look-ups later) with "list" as values, since for some combinations of rod length - we may cut more than once.

+1 for intuitive explanation, should you be answering .

Answer 1

So I've modified your code a bit to do two things:

1) Return "indicies" or cuts where the max val was found.

2) Store previously calculated results in a dict

import copy
price={1:1,2:5,3:8,4:9,5:10,6:17,7:17,8:20,9:24,10:30}
max_price = {}

def cut_rod(n,price):
    if n==0:
        #We are returning 0 and the empty list for a rod of size 0 as we don't cut
        #This is our base case
        return 0,[]
    revenue=-999
    #If we have already calculated the max price for the length, return price and indicies
    if n in max_price.keys():
        return max_price[n][0],copy.copy(max_price[n][1])
    cuts = []
    for i in range(1,n+1): 
            #Get the revenue and indicies from the smaller piece
        smaller_revenue,smaller_cuts =  cut_rod(n-i,price)
            #If we get a better price, set the indicies and revenue for the length
        if smaller_revenue + price[i] > revenue:
            smaller_cuts.append(i)
            cuts = smaller_cuts
            revenue = smaller_revenue + price[i]
    #store the calculated max results for rod of length n
    #need to copy to avoid linking
    max_price[n] = (revenue,copy.copy(cuts))
    return revenue, cuts

So all we are doing is using DP to remember where we cut for the max price for size n. We have to copy.copy() to eliminate accidentally modifying lists we made "permanent".

For example,

If we call cut_rod(1,price)

it will eventually call cut_rod(0,price)

which will return 0 and []

Our revenue will be -999, so price[1] + 0 will be > -999

The cuts for 1 will be [1].

Feel free to run

n = 10
revenue,cuts = cut_rod(n,price)print "revenue for rod of length %d is %d" %(n,revenue)
print "Cuts were sizes:"
print cuts
print max_price

To see length of sub rods and the full dict.

Output:

revenue for rod of length 10 is 30

Cuts were sizes:
[10]
#key = rod length, value = (revenue, [where cuts were made])
{1: (1, [1]), 2: (5, [2]), 3: (8, [3]), 4: (10, [2, 2]), 5: (13, [3, 2]), 6: (17, [6]), 7: (18, [6, 1]), 8: (22, [6, 2]), 9: (25, [6, 3]), 10: (30, [10])}