Dynamische Programmierung

[Julia]

Hallo Forum,

ich bin gerade dabei, mich auf die Algorithmen-Klausur vorzubereiten, aber bin mit der dynamischen Programmierung nie so richtig warm geworden.

Hier ist eine Aufgabe hierzu:

---

Gegeben sei eine Menge M von n Münzen mit Werten v_1, v_2,...,v_n in N. Sie sollen nun einen bestimmten Betrag S mit Hilfe dieser Münzen zusammensetzen. Jede Münze darf dabei nur einmal verwendet werden. Mittels Dynamischer Programmierung soll nun die minimale Anzahl an Münzen aus M bestimmt werden, die dazu nötig ist.

Vervollständigen Sie die folgende rekursive Funktion M(i, b). Diese gibt die minimale Anzahl von Münzen an, die nötig ist um unter Verwendung der ersten i Münzen den Betrag b zu erzielen, falls dies überhaupt möglich ist. Formulieren Sie mit Hilfe der Rekursionsformel in Stichworten einen möglichst effizienten Algorithmus und geben Sie Laufzeit und Speicherplatzbedarf Ihres Algorithmus an.

---

Ich habe folgende Idee:

Dabei entspricht M(b,i-1) dem Fall, dass wir die Münze i nicht nehmen und M(b-v_i,i-1)+1 dem Fall, dass wir die Münze nehmen und daher vom Betrag abziehen.

Dann wäre Algorithmus im Pseudo-Code:

findeMinAnzahl(S,v_i...v_n)
  if (b=0) return ∞
  if (b<0 oder (i=0 und b>0)) return 0
  else
    Matrix M // Deklarieren
    for i=1 to n
      for b=1 to S
         M[b][i]= ∞ // Füllen M mit ∞  
    for i=1 to n
      for b=1 to S
         M[b][i]=min{M[b][i-1], M[b-v_i][i-1]+1} //Hier wird schon Matrix M angesprochen
    x = M[n,S]
    return x

Und die Laufzeit und Speicherbedarf wären dann Θ(n*S).

Ist es richtig? Oder was mache ich falsch?

Schönen Dank im Voraus und viele Grüße

Julia