动态编程递归给出错误的结果

I am trying to solve a variant of Knapsack Problem and have written a recursive solution for it. But my solution is returning a wrong value. I guess my algo is flawed. Can you please help me find the glitch.

我正在尝试解决背包问题的一个变种,并为它编写了一个递归解决方案。但我的解决方案是返回错误的值。我想我的算法有缺陷。能帮我找到故障吗?

Here is my code.

这是我的代码。

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

问题的目的:通过最佳地使用给定的最大预算来找到最大的乐趣

Following are my input.

以下是我的意见。

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

The correct answer to the program should be 5. Mine is returning 7. I have drawn the recursion tree in the attempt to debug. My findings: While choosing item 0 ( right sub-tree), val = 2 + (11,1). This (11,1) will lead to max ( (11,2) and 0 ). (11,2) is 5 so the final result is 2+5 = 7. In this DP technique my algo should not have chosen 11,2 as sum of the budget exceeds the given one. But this is the basic skeleton I found for a recursive DP. Is this algo flawed or I have mistaken it.

该程序的正确答案应该是5.我正在返回7.我已经尝试调试时绘制了递归树。我的发现:在选择项目0(右子树)时,val = 2 +(11,1)。这(11,1)将导致max((11,2)和0)。 (11,2)是5所以最终结果是2 + 5 = 7.在这种DP技术中,我的算法不应该选择11,2作为预算的总和超过给定的一个。但这是我为递归DP找到的基本骨架。这个算法有缺陷还是我弄错了。

Thanks

Chidambaram

2 个解决方案

#1

The problem is that during the call calc_budget(b, i) you write fields of tbl for other indices than [b][i]. I will try to explain the issue by using the recursive definition of calc_budget(b, i).

问题是在调用calc_budget(b,i)期间,您为除[b] [i]之外的其他索引编写tbl字段。我将尝试使用calc_budget(b,i)的递归定义来解释该问题。

We start by defining the recurrence relation. Let F(b, i) be the maximum fun you can have with the parties i, ..., n and the maximum budget b. Then,

我们首先定义递归关系。让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

So far so good.calc_budget(b, i) should exactly calculate this number, and it should use tbl as a cache for already computed values. In other words, after the first time the call calc_budget(b, i) is made, tbl[b][i] == F(b, i) must be true.

到目前为止,good.calc_budget(b,i)应该准确计算这个数字,它应该使用tbl作为已计算值的缓存。换句话说,在第一次调用calc_budget(b,i)之后,tbl [b] [i] == F(b,i)必须为真。

Here's some pseudocode that achieves this:

这是一些实现此目的的伪代码:

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]

I hope you now agree that since tbl is really just a cache for already computed values, it would seem very odd to write e.g. tbl[b-budget[i]][i] in a call to calc_budget(b, i).

我希望你现在同意,因为tbl实际上只是已经计算过的值的缓存,所以写入例如tbl [b-budget [i]] [i]在对calc_budget(b,i)的调用中。

#2

First, I do not think 0 is good enough to indicate weather a sub problem has been calculated before, because there are some sub problems whose answer is actually 0. Second, there are a mistake in your code,you should have set the value of tbl[b][i] before you return the value. Try this:

首先,我认为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];

Hope it helps!

希望能帮助到你!

#1