动态规划递归给出了错误的结果

我想解决背包问题的一个变种，并为它写了一个递归解决方案。但我的解决方案正在返回一个错误的值。我想我的算法是有缺陷的。你能帮我找到故障吗？动态规划递归给出了错误的结果

这是我的代码。

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

动态规划递归给出了错误的结果

回答

相关问题