動態編程練習

我一直在努力通過動態編程練習，我似乎無法掌握它。我會在這裏寫下這個問題，也是解決方案，明確說明我不瞭解的內容。動態編程練習

我們給出了2個序列u1,u2,...,un和d1,d2,...,dm以及由正整數C=[cij]構成的尺寸爲n x m的矩陣。如果 i1 < 12 <..< ik和j1 < j2 <...< jk被稱爲k對 ((ui1, dj1),(ui2,dj2),...,(uik,djk))的列表是非相交的。的「列表的兼容性」被說成是對和的兼容性，它是由，即Ci1j1 + Ci2j2 + ... + Cikjk

實施例：考慮矩陣C = [Cij]，所以Cij = squared(i + j)。讓我成爲 i = 1, 2, 3, j = 1, 2, 3, 4和k = 2。一些2個不相交對的列表是這些((u1, d2),(u3, d3))，其兼容性爲9 + 36 = 45, ((u2, d2),(u3, d4))，兼容性爲16 + 49 = 65,和((u1, d1),(u2, d4)),，兼容性爲4 + 36 = 40。一些列出了沒有非交叉如下：((u2, d2),(u3, d1)),((u1, d4),(u3, d3)),((u3, d2),(u2, d3))

解決方案：

M（I，J，T）=從UI採取噸非交叉雙最大成本，...，UN和DJ，... DM

遞推方程：
M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).}

M(i, j, 0) = 0
M(i, j, t) = −∞, if t > min{n − i + 1, m − j + 1}
M(i, j, t) = 0, if i > n or j > m

我不把reccurrence下非常好，我們爲什麼要分配給−∞時M(i, j, t)但t > min{n − i + 1, m − j + 1} 0時i > n或j > m

的解決方案是M（1，1，K）。

來源

2015-04-06 Marcus Aurelius

M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).} 
      = max 
      { 
       M(i+1, j+1, t-1) + c(i, j), <- we know the maximum cost of t-1 
               non-intersecting pairs taken from 
               i+1,...,n and j+1,...,m to which 
               we prepend the pair (i, j). 
       M(i, j+1, t), <- keep it at t elements and don't prepend anything, 
            and take the one containing elements from 
            i,...,n and j+1,...,m 
       M(i+1, j, t) <- same, but take elements from i+1,...,n and j,...,m 
      }

這涵蓋所有情況：要麼我們在前面加上當前元素，並增加1的長度或不增加長度，並採取最大的這個（缺乏）需要採取行動的可能性。你可能會問：「但M(i+1,j+1,t)呢？這也是一種有效的可能性。」它是，但它由另外兩種情況所覆蓋：M(i+1,j,t)將檢查M(i+1,j+1,t)並在需要時返回。你可以自己添加它來重現，這不會是錯的，只是多餘的。

爲什麼我們分配-∞到M（I，J，T）當t>分鐘{N - I + 1，M - J + 1}

因爲不能有一個解決方案在這種情況下。在步驟i中，您只能從第一個序列中選取n - i + 1個元素（因爲您已經選取了i）。 j相同。如果t > min{n - i + 1, m - j + 1}，那麼您將無法從其中一個列表中選擇所需數量的元素，並將其標記爲負無窮大。

但0時i>名詞或j>米

這僅僅是處理超出範圍錯誤。我不確定他們爲什麼選擇0，我會爲此選擇負無窮大，或者只是爲了保持一致性，或者只是通過在實現中添加條件來完全避免它（如果i + 1 >= n然後忽略此分支，儘管您仍然需要返回0/-infinity如果沒有分支是有效的），但它並不重要。

如果您返回0並且答案是否定的，那麼您將遇到問題。當然，對於你的問題，由於C的構建方式，我們不能有一個負面的解決方案（因爲C包含數字的平方，總是>= 0）。所以你可以用0而不是第一種情況下的負無窮大。

練習：您能否寫出類似的重現，但解決辦法是由M(n, m, k)給出？先用文字定義它，然後用數學方法。

來源

2015-04-06 23:17:20 IVlad

動態編程練習

回答

相關問題