Münzproblem
-
Es sei eine (endliche) Menge von Münzen mit unterschiedlichem Wert gegeben. Es gilt einen Geldbetrag mit so wenig Münzen wie möglich zu wechseln. Dabei darf jede Münze beliebig oft gewechselt werden.
Im Allgemeinen löst man dieses Problem mittels dynamischer Programmierung, allerdings gibt es auch Münzmengen für die sich dieses Problem mittels eines Greedy Algorithmus lösen lässt.
Welche Bedingung muss eine Münzmenge erfüllen, damit man es mittels Greedy-Ansatz lösen kann?
-
mh, eine hinreichende bedingung ist:
für alle münzen muss gelten, dass der wert aller münzen die mehr wert sind ein vielfaches ist.