Info

Wissenschaft Informatik
#1

hallo ihr informatiker:wink:

ich steig bei folgender aufgabe nicht wirklich durch bzw. bin noch fleißig am überlegen…

Beim Münzwechselsproblem sind zahlen a_1, a_2,…,a_m Element N mit a_1=1 und ein Betrag n Element N gegeben. Die m Zahlen a_1,…,a_m geben die Werte der Münzen einer Währung an.
Das Problem besteht darin, die minimale Anzahl von diesen Münzen zu bestimmen, die den Betrag n darstellen. Folgender Algorithmus löst das Problem:

a) erzeuge ein array b[0],…,b[n].
b) setze b[0]:= 0

please help me…

#2

Hallo,

ein Aufteilungsproblem ist eigentlich trivial: man nimmt die grösste Münze, die kleiner ist als der Betrag, von dem zieht man diese Münze ab und macht mit dem Rest genauso weiter - also immer die grössten Münzen zuerst verbraten.

In der Praxis kommen Randbedingungen dazu, z.B. dass man nicht beliebig viele Münzen von jeder Sorte in der Kasse hat, diese Bedingung ändert aber auch nicht viel.

Gruss Reinhard

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]