Dynamisches Programmieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 08:58 So 03.02.2019 | | Autor: | Hela123 |
| Aufgabe | Gegeben sei eine Menge M von n Münzen mit Werten [mm]v_1, v_2,...,v_n \in \IN [/mm]. Sie sollen nun einen bestimmten Betrag S mit Hilfe dieser Münzen zusammensetzen, d.h eine Teilmenge [mm]U \subseteq 1, 2,..., n[/mm] finden, so dass [mm]S = \sum_{i \in U} v_i [/mm]. 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.
(a) 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.
[mm]M(b,i)=\left\{\begin{matrix}
\infty, & \mbox{falls } b=0 \\
0, & \mbox{falls } b<0 \vee(i=0 \wedge b>0) \\
..., & \mbox{falls } ...
\end{matrix}\right.[/mm]
(b) Formulieren Sie mit Hilfe der Rekursionsformel aus Teil a) in Stichworten einen möglichst effizienten Algorithmus, der M(S, |M|) mittels Dynamischer Programmierung berechnet. Geben Sie dabei Eingabe und Ausgabe an und denken Sie an die Initialisierung verwendeter Datenstrukturen und Variablen.
(c) Geben Sie Laufzeit und Speicherplatzbedarf Ihres Algorithmus aus Aufgabenteil b) an. Begründen Sie kurz Ihre Angaben! |
Hallo Forum,
ich bin gerade dabei, mich auf die Klausur vorzubereiten, aber bin mit der dynamischen Programmierung nie so richtig warm geworden.
(a) Hier habe ich folgende Idee:
[mm]M(b,i)=\left\{\begin{matrix}
\infty, & \mbox{falls } b=0 \\
0, & \mbox{falls } b<0 \vee(i=0 \wedge b>0) \\
min \{ M(b,i-1), M(b-v_i,i-1)+1 \}, & \mbox{falls } b>0 \wedge i>0
\end{matrix}\right.[/mm]
Dabei entspricht [mm]M(b,i-1)[/mm] dem Fall, dass wir die Münze i nicht nehmen und [mm]M(b-v_i,i-1)+1[/mm] dem Fall, dass wir die Münze nehmen und daher vom Betrag abziehen.
Macht es Sinn?
(b) Hier habe ich Folgendes:
Eingabe: S (Gesamtbetrag), n=|M| (Gesamtanzahl an Münzen), [mm] v_i...v_n [/mm] (Münzenwerte)
Ausgabe: x (Minimale Anzahl an benötigten Münzen)
[mm] findeMinAnzahl(S,v_i...v_n)
[/mm]
if [mm](b=0)[/mm] return [mm]\infty[/mm]
if [mm](b<0 \vee(i=0 \wedge b>0))[/mm] return 0
else
Matrix M // Deklarieren
for i=1 to n
for b=1 to S
M[b][i]= [mm]\infty[/mm] // Füllen M mit [mm]\infty[/mm]
for i=1 to n
for b=1 to S
M[b][i]=min [mm] \{M[b][i-1], M[b-v_i][i-1]+1\} [/mm] //Hier wird schon Matrix M angesprochen
x = M[n,S]
return x
Ist es richtig?
(c) Da wir 2 Schleifen durchlaufen müssen, sollte Laufzeit sowie Speicherbedarf [mm]\Theta (n*S)[/mm] sein. Ist es korrekt?
Vielen Dank im Voraus und viele Grüße
Hela123
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Do 07.02.2019 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
