Wenn Sie einen Satz Münzen mit unterschiedlichen Nennwerten und einem Wert v haben, möchten Sie die geringste Anzahl Münzen finden, die zur Darstellung des Werts v erforderlich ist.
ZB für den Münzsatz 1,5,10,20 ergeben sich 2 Münzen für die Summe 6 und 6 Münzen für die Summe 19.
Meine Hauptfrage lautet: Wann kann dieses Problem mit einer gierigen Strategie gelöst werden?
Bonuspunkte: Ist diese Aussage eindeutig falsch? (Aus: Woran erkennt man, ob der gierige Algorithmus für das Problem des minimalen Münzenwechsels ausreicht? )
In diesem Artikel wurde jedoch der Beweis erbracht, dass der Greedy-Algorithmus für den ersten und den zweiten Denom-Wert für alle funktioniert, und es wird empfohlen, lediglich den Greedy-Algorithmus gegen den optimalen DP-Algorithmus zu verwenden, um ihn zu überprüfen. http://www.cs.cornell.edu/~kozen/papers/change.pdf
Ps. Beachten Sie, dass die Antworten in diesem Thread unglaublich mies sind - deshalb habe ich die Frage neu gestellt.
quelle
Antworten:
Ein Münzsystem ist kanonisch, wenn die vom Greedy-Algorithmus veränderte Anzahl Münzen für alle Beträge optimal ist.
Das Papier D. Pearson. Ein Polynom-Zeit-Algorithmus für das Change-Making-Problem. Operations Reseach Letters, 33 (3): 231-234, 2005 bietet einen -Algorithmus zur Entscheidung, ob ein Münzsystem kanonisch ist, wobei die Anzahl der verschiedenen Arten von Münzen ist. Aus dem Abstract:O(n3) n
Das Papier ist ziemlich kurz.
Für ein nicht-kanonisches Münzsystem gibt es einen Betrag für den der Greedy-Algorithmus eine suboptimale Anzahl von Münzen erzeugt; heißt Gegenbeispiel . Ein Münzsystem ist eng, wenn sein kleinstes Gegenbeispiel größer ist als die größte Einzelmünze.c c
Der Artikel Kanonische Münzsysteme für Probleme beim Umtausch bietet die notwendigen und ausreichenden Bedingungen für kanonische Münzsysteme mit bis zu fünf Münzen sowie einen -Algorithmus zur Entscheidung, ob ein dichtes Münzsystem mit Münzen kanonisch ist.O(n2) n
Es gibt auch einige Diskussionen in dieser Frage .
quelle
canonical coin system
. Es wäre großartig, wenn Sie ein Beispiel hinzufügen könnten, z. B. wie das vorgeschlagene System getestet wird1,5,10,20