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

[pl]

Dynamische Programmierung ist eine Methode zum algorithmischen Lösen eines Optimierungsproblems durch Aufteilung in Teilprobleme und systematischen Speicherung von Zwischenresultaten. lt. Wikidingsda.

Wo ist jetzt bei Dir das Optimierungsproblem und wie teilt man das in Teilprobleme auf. Das wäre mein Ansatz. MfG