動態規劃 - 棒切割，同時保留製表切割的指標

Question

在經典的切割棒動態規劃問題中 - 在哪裏可以切割長度爲n的棒來最大化我通過出售全杆或其部分。詳情請參閱此處的問題陳述 - Understanding the bottom-up rod cut implementation

如何保留指標的選項卡 - 即在原始棒的哪個位置進行切割？ 我對於知道如何保持杆最終被切割的指標似乎沒有公平的理解。 這裏是我的代碼 - ：

# 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) 

對於長度爲4杆，我就2和2（即中途）的削減 - 我們如何記住這些指標？

編輯：我有一個大致的想法，我需要保持所有收入的標籤到目前爲止，與相應的切割位置 - 但我似乎迷失在主要通話 - 我應該存儲這之間的隨後在dict結構中調用，稍後再查看它。 我也認爲索引將是一個字典（稍後查找）與「列表」作爲值，因爲對於棒長度的一些組合 - 我們可能會減少不止一次。

+1爲了直觀的解釋，你應該回答。

Answer 1

所以我修改你的代碼有點做兩件事情：

1）返回「indicies」或割傷，其中最大VAL被發現。

2）店鋪前面。所有我們正在做的是使用DP記住，我們削減最高價爲大小n計算結果在一個字典

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 

。我們必須copy.copy（）來消除意外修改我們製作的「永久」列表。

例如，

如果我們調用cut_rod(1,price)

它最終將調用cut_rod(0,price)

將返回0 and []

我們的收入將是-999，所以price[1] + 0 will be > -999

的削減1將是[1]。

隨意運行

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 

要查看子杆和完整字典的長度。

輸出：

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])}