私はナップザック問題の変種を解決しようとしており、そのための再帰的な解決策を書きました。しかし、私の解決策は間違った値を返しています。私のアルゴリズムに欠陥があると思います。グリッチを見つけるのを手伝ってくれませんか。
これが私のコードです。
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 の基本的なスケルトンです。このアルゴリズムに欠陥がありますか、それとも私が間違っていますか。
ありがとう
チダンバラム