Warum funktioniert der Algorithmus zum gierigen Münzwechsel bei einigen Münzsätzen nicht?

Ich verstehe, wie der gierige Algorithmus für das Münzwechselproblem (zahlen Sie einen bestimmten Betrag mit der minimal möglichen Anzahl von Münzen) funktioniert - er wählt immer die Münze mit dem größten Nennwert aus, der die verbleibende Summe nicht überschreitet - und findet immer die richtige Lösung für spezifische Münzsets.

Bei einigen Münzsätzen gibt es jedoch Summen, für die der Greedy-Algorithmus fehlschlägt. Zum Beispiel {1, 15, 25}wählt der Greedy-Algorithmus für die Menge und die Summe 30 zuerst 25, wobei ein Rest von 5 und dann fünf Einsen für insgesamt sechs Münzen übrig bleiben. Die Lösung mit der minimalen Anzahl von Münzen besteht jedoch darin, zweimal 15 zu wählen.

Welche Bedingungen muss ein Münzsatz erfüllen, damit der gierige Algorithmus die minimale Lösung für alle Summen findet?

Ein Satz, der eine Matroid bildet ( https://en.wikipedia.org/wiki/Matroid ), kann verwendet werden, um das Münzwechselproblem mithilfe eines gierigen Ansatzes zu lösen. Kurz gesagt, eine Matroid ist ein geordnetes Paar M = (S, l), das die folgenden Bedingungen erfüllt:

1. S ist eine endliche nicht leere Menge
2. l ist eine nicht leere Familie von Teilmengen von S, die als unabhängige Teilmengen bezeichnet werden. Wenn also B-> l und A eine Teilmenge von B sind, dann ist A -> l
3. Wenn A-> l, B-> l und | A | <| B |, dann gibt es ein Element x-> BA, so dass AU {x} -> l

In unserer Frage des Münzwechsels ist S eine Menge aller Münzen in abnehmender Reihenfolge. Wir müssen einen Wert von V durch die Mindestanzahl von Münzen in S erreichen

In unserem Fall ist l eine unabhängige Menge, die alle Teilmengen enthält, sodass für jede Teilmenge Folgendes gilt: Die Summe der darin enthaltenen Werte ist <= V.

Wenn unsere Menge eine Matroid ist, ist unsere Antwort die maximale Menge A in l, in der kein x weiter hinzugefügt werden kann

Um zu überprüfen, sehen wir, ob die Eigenschaften von Matroid in der Menge S = {25,15,1} gelten, wobei V = 30. Nun gibt es zwei Teilmengen in l: A = {25} und B = {15,15} Seit | A | <| B |, dann gibt es ein Element x-> BA, so dass AU {x} -> l (gemäß 3) {25,15} also zu l gehören sollte, aber es ist ein Widerspruch seit 25 + 15> 30

S ist also keine Matroid und daher funktioniert der gierige Ansatz nicht.

In jedem Fall, in dem es keine Münze gibt, deren Wert, wenn er zur niedrigsten Stückelung addiert wird, niedriger als das Doppelte des Wertes ist, der unmittelbar darunter liegt, funktioniert der Greedy-Algorithmus.

dh {1,2,3} funktioniert, weil [1,3] und [2,2] denselben Wert addieren, {1, 15, 25} jedoch nicht, weil (für die Änderung 30) 15 + 15> 25 +1

Dies ist ein Wiederholungsproblem. Vorgegeben eine Menge von Münzen {Cn, Cn-1, . . ., 1}, so daß für 1 <= k <= n, Ck > Ck-1, wird der Greedy - Algorithmus die minimale Anzahl von Münzen ergeben , wenn Ck> Ck-1 + Ck-2 und für den Wert V=(Ck + Ck-1) - 1, den Greedy - Algorithmus auf die Teilmenge von Münzen Anwendung {Ck, Ck-1, . . ., 1}, wobei die Ck <= VErgebnisse in weniger Münzen als die Zahl, die sich aus der Anwendung des Greedy-Algorithmus auf die Teilmenge der Münzen ergibt {Ck-1, Ck-2, . . ., 1}.

Der Test ist einfach: Für `1 <= k <= n Test die Anzahl der Münzen, die der Greedy-Algorithmus für einen Wert von Ck + Ck-1 - 1 ergibt. Führen Sie dies für den Münzsatz {Ck, Ck-1 ,. . ., 1} und {Ck-1, Ck-2 ,. . ., 1}. Wenn für ein k das letztere weniger Münzen ergibt als das erstere, funktioniert der Greedy-Algorithmus für diesen Münzsatz nicht.

Betrachten Sie beispielsweise mit n = 4 den Münzsatz {C4, C3, C2, 1} = {50,25,10,1}. Beginnen Sie mit k = n = 4, dann V = Cn + Cn-1 - 1 = 50 + 25-1 = 74 als Testwert. Für V = 74 ist G {50,25,10,1} = 7 Münzen. G {25, 10, 1} = 8 Münzen. So weit, ist es gut. Nun sei k = 3. dann ist V = 25 + 10-1 = 34. G {25, 10, 1} = 10 Münzen, aber G {10, 1} = 7 Münzen. Wir wissen also, dass der Greedy-Algorithmus die Anzahl der Münzen für den Münzsatz {50,25,10,1} nicht minimiert. Wenn wir andererseits diesem Münzsatz ein Nickel hinzufügen, ist G {25, 10, 5, 1} = 6 und G {10, 5, 1} = 7. Ebenso gilt für V = 10 + 5-1 = 14 erhalten wir G {10, 5, 1} = 5, aber G {5,1} = 6. Wir wissen also, dass Greedy für {50,25,10,5,1} arbeitet.

Das wirft die Frage auf: Wie sollte der Nennwert von Münzen lauten, um den Greedy-Algorithmus zu erfüllen, der die kleinste Anzahl von Münzen im ungünstigsten Fall für einen Wert von 1 bis 100 ergibt? Die Antwort ist ganz einfach: 100 Münzen mit jeweils unterschiedlichen Werten von 1 bis 100. Dies ist wahrscheinlich nicht sehr nützlich, da bei jeder Transaktion linear nach Münzen gesucht wird. Ganz zu schweigen von den Kosten, so viele verschiedene Stückelungen zu prägen und zu verfolgen.

Wenn wir nun primär die Anzahl der Stückelungen minimieren wollen, während wir sekundär die resultierende Anzahl von Münzen für einen von Greedy produzierten Wert von 1 bis 100 minimieren wollen, dann Münzen in Stückelungen von Potenzen von 2: {64, 32, 16, 8, 4 , 2, 1} ergeben maximal 6 Münzen für einen Wert von 1: 100 (die maximale Anzahl von Einsen in einer Sieben-Bit-Zahl, deren Wert kleiner als 100 ist). Dies erfordert jedoch 7 Stückelungen Münze. Der schlechteste Fall für die fünf Nennwerte {50, 25, 10, 5, 1} ist 8, was bei V = 94 und V = 99 auftritt. Münzen mit Potenzen von 3 {1, 3, 9, 27, 81} erfordern auch nur 5 Stückelungen, um von Greedy gewartet werden zu können, ergeben jedoch auch einen Worst-Case von 8 Münzen mit Werten von 62 und 80. Verwenden Sie schließlich eine der fünf Stückelungen Teilmenge von {64, 32, 16, 8, 4, 2, 1}, die '1' nicht ausschließen kann und die Greedy erfüllt, führt auch zu maximal 8 Münzen. Es gibt also einen linearen Kompromiss. Durch Erhöhen der Anzahl der Stückelungen von 5 auf 7 wird die maximale Anzahl von Münzen verringert, die erforderlich sind, um einen Wert zwischen 1 und 100 von 8 auf 6 darzustellen.

Wenn Sie andererseits die Anzahl der zwischen einem Käufer und einem Verkäufer ausgetauschten Münzen minimieren möchten , vorausgesetzt, jede hat mindestens eine Münze jeder Stückelung in der Tasche, entspricht dieses Problem den geringsten Gewichten, die zum Ausgleichen erforderlich sind Gewicht von 1 bis N Pfund. Es stellt sich heraus, dass die geringste Anzahl von Münzen, die bei einem Kauf umgetauscht werden, erreicht wird, wenn die Münzwerte in Potenzen von 3 angegeben werden : {1, 3, 9, 27, . . .}.

Siehe /puzzling/186/whats-the-fewest-weights-you-need-to-balance-any-weight-from-1-to-40-pounds .

Ein Münzsystem ist kanonisch, wenn die Anzahl der Münzen, die durch den Greedy-Algorithmus geändert werden, für alle Beträge optimal ist.

Dieses Papier bietet einen O (n ^ 3) -Algorithmus zur Entscheidung, ob ein Münzsystem kanonisch ist, wobei n die Anzahl der verschiedenen Arten von Münzen ist.

Für ein nicht-kanonisches Münzsystem gibt es einen Betrag, cfür den der Greedy-Algorithmus eine suboptimale Anzahl von Münzen erzeugt; cwird als Gegenbeispiel bezeichnet. Ein Münzsystem ist eng, wenn sein kleinstes Gegenbeispiel größer ist als die größte Einzelmünze.

Heute habe ich eine ähnliche Frage zu Codeforces gelöst (Link wird am Ende bereitgestellt). Mein Fazit war, dass das Münzwechselproblem, um durch den gierigen Alogrithmus gelöst zu werden, folgende Bedingung erfüllen sollte:

1. Beim Sortieren von Münzwerten in aufsteigender Reihenfolge sollten alle Werte für das Element größer als aktuell durch das aktuelle Element teilbar sein.

zB Münzen = {1, 5, 10, 20, 100}, dies gibt die richtige Antwort, da {5,10, 20, 100} alle durch 1 teilbar sind, {10,20, 100} alle durch 5 teilbar sind, { 20.100} alle sind durch 10 teilbar, {100} alle sind durch 20 teilbar.

Hoffe das gibt eine Idee.

996 A - Nehmen Sie an der Lotterie teil https://codeforces.com/blog/entry/60217

Ein leicht zu merkender Fall ist, dass jeder Satz von Münzen so, dass, wenn sie in aufsteigender Reihenfolge sortiert sind und Sie haben:

coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]

Dann funktioniert ein gieriger Algorithmus, der solche Münzen verwendet.

Abhängig von der Reichweite, die Sie abfragen, kann es zu einer optimaleren Zuordnung (in Bezug auf die Anzahl der erforderlichen Münzen) kommen. Ein Beispiel hierfür ist, wenn Sie den Bereich (6..8) berücksichtigen und die Münzen <6, 7, 8> anstelle von <1, 2, 4, 8> haben.

Die effizienteste Zuweisung von Münzen, die über N + abgeschlossen ist, entspricht den oben genannten Regeln, sodass Sie die Münzen 1, 2, 4, 8 ... erhalten. Das ist nur die binäre Darstellung einer beliebigen Zahl. In gewissem Sinne ist die Konversation zwischen Basen ein gieriger Algorithmus für sich.

Ein Beweis für die Ungleichung> = 2N liefert Max Rabkin in dieser Diskussion: http://olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf