Reputation: 1620
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 .
Upvotes: 1
Views: 2004
Reputation: 8346
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])}
Upvotes: 1