動態規劃遞歸給出了錯誤的結果

我想解決揹包問題的一個變種，併爲它寫了一個遞歸解決方案。但我的解決方案正在返回一個錯誤的值。我想我的算法是有缺陷的。你能幫我找到故障嗎？動態規劃遞歸給出了錯誤的結果

這是我的代碼。

int calc_budget(int b, int i){ 
    // If we have reached the end 
    if(i >= nParty){ 
      tbl[b][i] = 0; 
      return tbl[b][i]; 
    } 

    //If remaining capacity is not able to hold the ith capacity, move on to next element 
    if(budget[i] > b){ 
      if(tbl[b][i+1] == 0){ 
        tbl[b][i+1] = calc_budget(b,i+1); 
      } 
      return tbl[b][i+1]; 
    } 
    else{ //If the ith capacity can be accomodated 
      //Do not include this item 
      if(tbl[b][i+1] == 0){ 
        tbl[b][i] = calc_budget(b,i+1); 
      } 

      // Include this item and consider the next item 
      if(tbl[b-budget[i]][i+1] == 0){ 
        tbl[b-budget[i]][i] = fun[i] + calc_budget(b-budget[i], i+1); 
      } 

      // We have the results for includinng ith item as well as excluding ith item. Return the best (max here) 
      return max(tbl[b][i], tbl[b-budget[i]][i]); 
    } 

}

Objective of the problem: To find the maximum fun by optimally using the given max budget

以下是我的輸入。

budget[3] = {19,12,19} 
fun[3] = {2,4,5} 
calc_budget(30,0) 
allowed budget: 30

程序的正確答案應該是5.我正在返回7.我已經繪製了遞歸樹以嘗試調試。我的發現：在選擇項目0（右子樹）時，val = 2 +（11,1）。這（11,1）將導致最大（（11,2）和0）。（11,2）是5，所以最終結果是2 + 5 = 7。在這種DP技術中，我的算法不應該選擇11,2作爲預算總和超過給定的。但是這是我爲遞歸DP發現的基本骨架。這算法有缺陷還是我誤解了它。

感謝

奇丹巴拉姆

來源

2013-04-10 CHID

的問題是，在通話過程中calc_budget(b, i)你寫的其他指數比[b][i]的tbl領域。我將嘗試使用calc_budget(b, i)的遞歸定義來解釋問題。

我們從定義遞歸關係開始。讓F(b, i)成爲您與各方的最大樂趣i, ..., n和最高預算b。然後，

F(b, n+1) = 0 
F(b, i) = F(b, i+1) // if budget[i] > b 
      = max(F(b, i+1), fun[i] + F(b - budget[i], i+1)) // otherwise

到目前爲止好。 calc_budget(b, i)應該精確計算此數字，並且應該使用tbl作爲已計算值的緩存。換句話說，在第一次撥打calc_budget(b, i)後，tbl[b][i] == F(b, i)必須爲真。

下面是一些僞代碼實現這一點：

initialize tbl[b][i] = -1 for all b, i. 

def calc_budget(b, i): 
    if tbl[b][i] != -1: return tbl[b][i] 

    if i == n + 1: 
     tbl[b][n+1] = 0 
    else: 
     if budget[i] > b: 
      tbl[b][i] = calc_budget(b, i+1) 
     else: 
      tbl[b][i] = max( 
          calc_budget(b, i+1), 
          fun[i] + calc_budget(b - budget[i], i+1) 
          ) 

    return tbl[b][i]

我希望你現在同意，因爲tbl實際上只是已經計算值的緩存，它似乎很奇怪，例如寫tbl[b-budget[i]][i]致電calc_budget(b, i)。

來源

2013-04-10 15:53:05 blubb

首先，我不認爲0表示天氣的子問題已經計算過，因爲有一些子問題的答案實際上是0. 其次，代碼中存在錯誤，您應該在返回值之前設置了tbl [b] [i]的值。試試這個：

// We have the results for includinng ith item as well as excluding ith item. Return the best (max here)  
tbl[b][i]=max(tbl[b][i], tbl[b-budget[i]][i]); 
return tbl[b][i];

希望它有幫助！

來源

2013-04-12 09:46:01 Chasefornone

動態規劃遞歸給出了錯誤的結果

回答

相關問題