1

私はナップザック問題の変種を解決しようとしており、そのための再帰的な解決策を書きました。しかし、私の解決策は間違った値を返しています。私のアルゴリズムに欠陥があると思います。グリッチを見つけるのを手伝ってくれませんか。

これが私のコードです。

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 の基本的なスケルトンです。このアルゴリズムに欠陥がありますか、それとも私が間違っていますか。

ありがとう

チダンバラム

4

2 に答える 2

0

問題は、呼び出し中に以外のインデックスの のcalc_budget(b, i)フィールドを書き込むことです。の再帰的定義を使用して、この問題を説明しようとします。tbl[b][i]calc_budget(b, i)

再帰関係を定義することから始めます。パーティーと最大の予算F(b, i)で最大の楽しみを手に入れましょう。それで、i, ..., nb

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)true でなければなりません。

これを実現する疑似コードを次に示します。

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-10T15:53:05.577 に答える