Das war eine Interviewfrage:
Bei einem gegebenen Betrag, sagen wir $ 167,37, finden Sie alle möglichen Möglichkeiten, die Veränderung für diesen Betrag unter Verwendung der in der Währung verfügbaren Nennwerte zu generieren.
Wer sich einen raum- und zeiteffizienten Algorithmus und unterstützenden Code vorstellen kann, bitte teilen.
Hier ist der Code, den ich geschrieben habe (funktioniert). Ich versuche die Laufzeit zu finden, jede Hilfe wird geschätzt
%Vor%BEARBEITEN
Dies ist ein spezifisches Beispiel für das hier beantwortete Kombinations- / Teilmengenproblem.
Finden Sie alle möglichen Kombinationen von Zahlen zu eine bestimmte Summe erreichen
--- Ich behalte meine Antwort unten (wie es jemandem nützlich war), allerdings ist es zugegebenermaßen keine direkte Antwort auf diese Frage ---
ORIGINAL ANTWORT
Die gebräuchlichste Lösung ist die dynamische Programmierung:
Zuerst finden Sie den einfachsten Weg, um 1 zu ändern, dann verwenden Sie diese Lösung, um Änderungen für 2, 3, 4, 5, 6 usw. vorzunehmen. Bei jeder Iteration "überprüfen" Sie, ob Sie kann "rückwärts" gehen und die Anzahl der Münzen in Ihrer Antwort verringern. Zum Beispiel bis zu "4" müssen Sie Pfennige hinzufügen. Aber sobald Sie auf "5" kommen, können Sie alle Pfennige entfernen, und Ihre Lösung hat nur eine Münze: den Nickel. Aber dann, bis 9, müssen Sie wieder Pennies hinzufügen, etc etc usw.
Die dynamische Programmiermethodik ist jedoch nicht garantiert, um schnell zu sein.
Alternativ können Sie eine gierige Methode verwenden, bei der Sie kontinuierlich die größtmögliche Münze auswählen. Dies ist extrem schnell, aber nicht immer eine optimale Lösung. Wenn Ihre Münzen jedoch 1 5 10 und 25 sind, funktioniert Greedy perfekt und ist viel schneller als die lineare Programmiermethode.
Memoization (Art von) ist dein Freund hier. Eine einfache Implementierung in C:
%Vor%Also, was wir hier wirklich machen, sagt:
1) Unser einziger möglicher Weg, 0 Münzen zu machen, ist 0 (dies ist unser Basisfall)
2) Wenn wir versuchen, den Wert m zu berechnen, dann prüfen wir jede Münze k. Solange k & lt; = m, können wir diese Münze k in einer Lösung verwenden
3) Nun, wenn wir k in einer Lösung verwenden können, können wir nicht einfach die Lösung für (m-k) nehmen und sie zu unserer aktuellen Summe hinzufügen?
Ich würde versuchen, das im wirklichen Leben zu modellieren.
Wenn Sie an der Kasse wären und Sie wüssten, dass Sie $ 167,37 finden müssten, würden Sie wahrscheinlich zuerst $ 200 als das "einfachste" Zahlungsmittel betrachten, da es nur zwei Noten sind. Dann, wenn ich es hatte, kann ich $ 170, d. H. $ 100, $ 50 und $ 20 (drei Noten) betrachten. Siehst du, wohin ich gehe?
Versuchen Sie formal, mit der minimalen Anzahl von Banknoten / Münzen zu überbieten. Dies wäre viel einfacher aufzuzählen als die ganze Reihe von Möglichkeiten.
Benutze keine Floats, selbst kleinste Ungenauigkeiten werden deinen Algorithmus zerstören.
Gehen Sie von der größten zur niedrigsten Münze / Banknote. Rufen Sie für jeden möglichen Betrag die Funktion rekursiv auf. Wenn keine Münzen mehr übrig sind, bezahlen Sie den Rest in Einsen und drucken Sie die Lösung aus. So sieht es in Pseudo-C aus:
%Vor%Tags und Links algorithm java c data-structures