動的プログラミングのコアダンプエラー

Question

与えられた変更量に必要なコインの数を最小限に抑えるプログラムを変更しています。このコインシステムには、$ 0.01、$ 0.06、$ 0.10の3つのコインしかありません。したがって、13セントの場合、コインが3の場合の最小数。56セントの場合、最小数は6です。プログラムはその部分を行います。私の部分はメモテーブルをトレースして、使用された各コインの数を決定します。たとえば、13セントの場合、最低3枚のコインがあり、そのコインは2セントのコインと1セントのコインになります。

以下の生成メモテーブルのようなものになります。このような何かのために

1cent 0 1 2 3 4 5 6 7 8 9 10 11 12 13 
6cent 0 1 - 3 - - - 2 - - - - - 3 
10cent 0 - - 3 - - - - - - - - - 3 

を私たちは常に右下に開始します。私はこれを再帰的にやろうとしています。私はパターンに気づいた。数字があり、それより上の数字が同じでない場合は、同じ行の左に「ジャンプ」しますcentスペース。したがって、最下行の10 cent行では、最後に13から3にジャンプして10個のスペースが表示されます。数字と上記の数字が同じ数字である場合、それは何度もコインが使用されなくなったことを意味し、行を上に移動します。上の表の右下にある3から始めます。真上の数字も3であるので、0の "ジャンプ"があるので、使用される10セントコインの数は0であり、次の行、すなわち6 cent行に移動します。

ここでは、3と13を比較します。これらの2つの数字は等しくないので、6スペースを移動します。したがって、我々は今のところ1 "jump"を持っています。今度は2と7を見る。これらの2つも同じではないので、6スペースをさらに移動し、現在は2 "jumps"を持っています。今度は1と1を比較して、それらが等しいので、行を上に移動して、その点から開始します。この過去の行で2 "ジャンプ"があったので、使用された6 centコインの数は2です。この最後の部分では、混乱します。行を上に移動すると、同じ列で開始します。 1と1を比較していたので、その列から再開します。これが最後の行、行0であるため、変更の残量は常に先頭の数字になります。私の例では、我々は行を移動し、1で始まり、従って1 centのコインの数は1です。つまり、使用されているコインの総数は次のとおりです。

1 cent: 1 
6 cent: 2 
10 cent: 0 

これは非常に混乱した形で言われています。うまくいけば、私のコードはこれをより良く示すことができます。ここで私はこれを実装しようとした方法です：

void countCoins(uint i, uint a, uint coinVal, 
       const vector<uint> & denom, 
       Matrix<uint> & memo) 
{ 
    uint numCoins = 0; 

    // Check the current value with the value above it 
    if(memo.at(i, a) != memo.at(i - 1, a)) 
    { 
     if(denom.at(i) == coinVal) 
     { 
     numCoins++; 
     } 

     countCoins(i, a - denom.at(i), coinVal, denom, memo); // If not equal, "jump" over 
    } 
    else 
    { 
     if(i > 0) 
     { 
     countCoins(i - 1, a, coinVal, denom, memo); // If equal, move up a row 
     } 
     else 
     { 
     numCoins += a; // If equal and the row number is 0 
     } 
    } 
} 

「、matrix.hこのコードはコンパイルが、私はそれを実行したときに、私が言うメッセージが出る：48：&マトリックスオブジェクト::（UINT、UINT）で[with Object = unsigned int; uint = unsigned int]：アサーション `row <行& & col < cols 'failed。 アボート（コアダンプ）"と私は理由を知りません。なぜこのコアダンプされたメッセージが得られるのか誰にも分かりますか？

Answer 1

あなたがmemoおよび/またはdenomにアクセスしようとする前に、iとa未満0であるかどうかを確認する必要があります。

void countCoins(uint i, uint a, uint coinVal, 
       const vector<uint> & denom, 
       Matrix<uint> & memo) 
{ 
    if (i < 0) { 
     // handle edge case and return 
    } 

    if (a < 0) { 
     // handle edge case and return 
    } 

    uint numCoins = 0; 

    ... 
    ... 

} 

注：iとaはmemoの大きさよりも高い値を持つことができ、denomあなたもそのをチェックする必要がある場合。しかし、あなたのコードでは、あなたが常にそれらを減らしているように思えます。