遞歸解決動態規劃

可能重複：
Dynamic Programming and Knapsack Application 遞歸解決動態規劃

我一直在試圖瞭解動態規劃，但隨着每一個新的問題我有點糊塗瞭如何編寫遞歸它。

採取以下問題：有一個長×高金屬片可以由機垂直地切成兩片的任一個或horizontally.Both L，H是整體的，所述切口還沿着積分values.There發生是矩形模式l（i）×h（i），i≤n（l，h也是積分的），其中第i個模式具有c（i）。設計一種有效的算法來裁剪紙張，從而最大化利潤總額。

現在我想解決它，我們將創建一個LxH表格（這將填補diaganally）。但是我們如何形成解決這個問題的遞歸呢？

來源

2012-10-05 user978278

你應該用遞歸O啓動（2^N ）解決方案，並着眼於如何將其優化爲多項式解決方案，而不是相反。 – jli

@jli我該如何開始接近這個問題？ – user978278

同樣的問題[這裏]（http://stackoverflow.com/questions/12626854/dynamic-programming-and-knapsack-application） – Haile

我會嘗試像每一個T（L，H），確認之間的最佳替代品：

收集利潤馬上
切百般水平
切斷一切可能的方式垂直

喜歡的東西：

T(L, H) = max(
    c(L, H), 
    T(i, H)+T(L-i, H), // 0<i<L 
    T(L, i)+T(L, H-i) // 0<i<H 
)

來源

2012-10-05 21:28:41

我不明白爲什麼你真的想使用遞歸，而你有一個dp關係。回溯遞歸通常非常低效，因爲其複雜度通常爲O（2^N）或更高。

然而，這些指數的算法是多少這樣的：

function rec(state) 
    if state = end 
     return 
    Choose the current element 
    rec(state + 1) 
    Don't choose the current element 
    rec(state + 1)

你的情況，這也許是這樣的蠻力：

function rec(rect r) 
     if r is empty 
     return 0 
     Max = 0 
     for i = 1 to r.width 
      for j = 1 to r.hight 
      rect g = cut(r, i, j) 
      Max = max(Max, profit(g) + rec(r - g)) 
     return Max

來源

2012-10-05 21:41:27

遞歸解決動態規劃

回答

相關問題