以最大增益順序跳轉 - 動態編程

Question

我們有一系列項目1，...，n，每個項目都有一個分數（i）。如果我們選擇一個項目，那麼我們不能選擇i + 1，... i + rest（i）項。目標是最大化總分。

我們可以用動態規劃解決這個問題。

對於第一項我們有兩個選項。或選擇它並轉到其餘（1）+ 1項目或不選擇它並轉到第二項目。

的遞歸函數：

c[i] = max{ c[i - 1], c[i + rest(i) + 1] + score(i) } 

與此遞歸函數的問題是，它的子問題意味着子問題之間創建週期不是獨立的。

我認爲這將是理想的有類似

c[i] = max{ c[i - 1], c[i - itemThatWentToItem(i)] + score(i) } 

也許一個解決辦法是有一個功能，讓所有導致項目我，然後把它們之間的最大比分的項目。

另一個想法是將此問題轉換爲DAG中的最長路徑，並針對所有子圖執行此操作。

任何想法？

Answer 1

除了註釋。是的，它可以用遞歸來實現，這樣的：

def C(i, n): 
    if i > n: 
    return 0 
    return max(C(i+1, n), C(i+rest(i)+1)+score(i)) 
print C(0,n) 

這是最好的（最快）來計算從後面值。像（注：陣列被索引1到n）：

# initialize array with lot of zeros: length + max score(i) 
cs = [0] * (n+max(rest(i) for i in range(0,n)+1) 
for i in range(n, 0, -1): 
    cs[i] = max(cs[i+1], cs[i+rest(i)+1]+score(i)) 
print cs[1]