Core Dump Fehler in der dynamischen Programmierung

Question

Ich modifiziere ein Programm, das die geringste Anzahl von Münzen für eine bestimmte Menge an Änderung bestimmt bestimmt. Dieses Münzsystem hat nur drei Münzen: 0,01 $, 0,06 $, 0,10 $. Also für 13 Cent, die Mindestanzahl, wenn Münzen 3 sind. Für 56 Cent ist die Mindestanzahl 6 usw. Das Programm macht diesen Teil, mein Teil ist es, die Memotabelle zurück zu verfolgen, um die Anzahl der verwendeten Münzen zu bestimmen. Zum Beispiel, für 13 Cent ist das Minimum 3 Münzen und diese Münzen wären 2 6-Cent-Münzen und 1 1-Cent-Münze.

Das Memo Tabelle unten erzeugt sieht ungefähr so ​​aus:

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 

Für diese so etwas wie wir immer unten rechts beginnen. Ich versuche das rekursiv zu tun. Ich habe ein Muster bemerkt. Wenn wir eine Nummer haben und die Nummer darüber nicht die gleiche Nummer ist, "springen" wir nach links von derselben Zeile cent Leerzeichen. Also in der unteren Reihe, der 10 cent Zeile, am Ende sehen wir einen Sprung von 13 zu 3, was 10 Leerzeichen ist. Wenn eine Nummer und die Nummer oben die gleiche Nummer ist, bedeutet das, dass die Münze nach vielen Malen nicht mehr benutzt wird und wir uns eine Reihe nach oben bewegen. In der obigen Tabelle beginnen wir in der unteren rechten Ecke, 3. Die Zahl direkt darüber ist auch eine 3, da es also 0 "Sprünge" gab, ist die Anzahl von 10 Cent-Münzen 0 und wir bewegen uns in die nächste Reihe, die 6 cent Reihe.

Jetzt vergleichen wir 3 und 13. Diese beiden Zahlen sind nicht gleich, also bewegen wir uns über 6 Leerzeichen. So haben wir 1 "Jump" ab sofort. Jetzt schauen wir uns 2 und 7 an. Diese beiden sind auch nicht gleich, also bewegen wir uns über 6 mehr Leerzeichen und jetzt haben wir 2 "Sprünge". Jetzt vergleichen wir 1 und 1 und sie sind gleich, so dass wir eine Zeile weitergehen und von diesem Punkt aus beginnen. Da wir in dieser letzten Zeile 2 "Sprünge" hatten, ist die Anzahl der verwendeten 6 cent Münzen 2. Für diesen letzten Teil wird es verwirrend. Wenn wir uns eine Reihe nach oben bewegen, beginnen wir in derselben Spalte, in der wir uns befanden. Da wir 1 und 1 verglichen haben, werden wir von dieser Spalte fortfahren. Da dies die letzte Zeile ist, Zeile 0, ist die Menge der verbleibenden Änderung immer die Nummer an der Spitze. In meinem Beispiel sind wir eine Zeile nach oben gerückt und haben begonnen, um 1 so die Anzahl der verwendeten Münzen ist 1. Das heißt, die Gesamtzahl der verwendeten Münzen ist:

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

Ich weiß, dass dies in einer sehr verwirrenden Weise formuliert ist. Hoffentlich zeigt mein Code das besser. Hier ist, wie ich versucht, dies zu implementieren:

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 
     } 
    } 
} 

Dieser Code kompiliert, aber wenn ich es benutze ich eine Nachricht, die sagt: „matrix.h: 48: Object & Matrix :: at (uint, uint) [mit Object = unsigned int; uint = unsigned int]: Assertion `Zeile < Zeilen & & Spalte < Spalten fehlgeschlagen. Abgebrochen (Core Dumped)" und ich habe keine Ahnung warum. Weiß jemand, warum ich diese Core-Dump-Nachricht bekommen würde?

Answer 1

Sie müssen überprüfen, ob i und a weniger als 0, bevor Sie versuchen memo zuzugreifen und/oder denom.

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; 

    ... 
    ... 

} 

Hinweis: Wenn i und a können höhere Werte haben als die Größen von memo und denom Sie müssen das auch überprüfen. Aber in Ihrem Code scheint es so, als ob Sie sie immer dekrementieren, also ist es wahrscheinlich nicht der Fall.