Algorithmus, um die „üblichen“ Cash Zahlungsbeträge für einen bestimmten Preis zu bestimmen

Question

Sie gehen in einen Laden, mehrere Produkte auswählen, dann weiter mit dem Zähler Ihre Rechnung zu bezahlen. Die Summe ist eine gewisse Menge (A). Sie gelangen in den Geldbeutel, Geldbörse oder Tasche und etwas Geld weglegen (P), wobei P> = A, und die Kassiererin gibt Ihnen ändern.

die Menge der Münzen und Scheine gegeben, die im Umlauf sind, was die wahrscheinlichsten Werte für P sind?

Einige Beispiele, unter der Annahme, dass die zur Verfügung stehenden Rechnungen sind $ 5, $ 10, $ 20, $ 50 und $ 100, und die verfügbaren Münzen sind 5c, 10c und 25c:

A = $ 151,24
P[1] = $ 160 (8x 20 $) oder (100 $ + 3x $ 20)
P[2] = $ 155 (+ $ 50 $ 100 + $ 5)

A = $ 22.65
P[1] = $ 25 ($ 20 + $ 5)
P[2] = $ 30 ($ 20 + $ 10)
P[3] = $ 40 ($ 20 + $ 20)

A = $ 0.95
P[1] = von $ 1 (4 x 25c)
P[2] = $ 5

Viele dieser Zahlen scheinen intuitiv, aber ich habe das Gefühl, dass der Algorithmus schwer zu.

Answer 1

Es gibt auch andere Faktoren, Sie sind nicht geeignet, mit 6 x 0,25 zu zahlen, würden Sie 1 verwenden x 1,00 und 2 x 0,25 statt. Im Allgemeinen 0,25 nicht mehr als 3 wäre, würde 0,10 betragen nicht mehr als 2, und 0,05 wäre nicht mehr als 1.

Auch in der realen Welt, viele Menschen nie weniger mit Werten stören dann 1,00, alawys sie mit Rechnungen bezahlen und „die Änderung halten“.

Das gleiche gilt für 5.00, 10.00 und 20.00 Uhr, für den Kauf mehr als ein paar Dollar Leute stattdessen ein 5,00 oder 10,00 verwenden. Natürlich 20.00 sind die am häufigsten im Umlauf dank Geldautomaten.

Was ist diese Software für? versuchen Sie tatsächlich tatsächliche Käufe Modell und genaue Ergebnisse benötigen oder eine einfache Simulation, die nicht streng sein muss?

Answer 2

„Wahrscheinlich“ macht dies ein sehr heikeles Problem. Sie müßten die relative Verfügbarkeit und Verteilung von jeder Art von Währung kennen. Zum Beispiel 22% aller Rechnungen im Umlauf ist $ 20, so dass sie viel eher als $ 10 verwendet werden oder $ 50 Rechnungen für Beträge zwischen $ 10 und $ 100.

Answer 3

Dies ist eigentlich ein bekanntes Problem, es ist eine Variante von binpacking wenn ich mich nicht irrt ...

Manchmal ist es die Kassierer Algorithmus genannt (oder Greedy-Algorithmus ). Sie können eine Implementierung in dieser Präsentation finden: http: // www. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf finden Sie auf Seite 11/12/13 ..

(zu klären, der normalen Kassierer Algorithmus liefert nur die minimale Menge an Münzen benötigt, um die Kunden zurück zu zahlen. Aber man könnte die dynamische Programmierlösung verändert all möglichen Kombinationen zu berechnen)

Answer 4

OH! @ # $% ^ & * () _, Jetzt bin ich wirklich pi..ed.

Ich schrieb nur Pseudo-Code und Komplexität Schätzung für 10 Minuten, und wenn ich dort Post ist nur die Schaltfläche „Ich bin ein Mensch“ ohne jede Möglichkeit, etwas und meine komplette Post zu betreten ist weg (und natürlich, dieses Mal habe ich nicht eine Kopie des Bearbeitungsfensters machen, nur für den Fall ...), ok so sind hier die Kurzversion:

Anzahl der Münzen in der Regel Super monoton (das heißt jeder Wert> als Summe der vorherigen Werte), laden Sie daher gierig verwenden können, um die genaue Münzen für A zu erhalten.

Sie nun dieses Multi-Set P von Münzen verwenden, füge sie den (bis jetzt leer) Ergebnismenge (eine Reihe von Multimengen), und die (bis jetzt leer zu) Workingset.

Nun wiederholen, bis der Arbeitssatz leer ist:

Nehmen Sie

gesetzt P aus dem Arbeitssatz, P '= P, für jede Münze c in P: P' = P.replace (c, nextBiggerCoin), removeSmallestCoin (solange P ohne kleinste Münze noch> A)

Wenn die P‘noch nicht in Ergebnismenge ist, es in Ergebnismenge gesetzt und Working Set

Meine vermutete Komplexität war O (n * n ^ 2), wobei s die Anzahl der Lösungen.

Answer 5

  

Es ist für ein Point-of-Sale-System. Wenn der Endpreis berechnet wird, hat der Kassierer in der Menge an Bargeld durch die Kunden zu gelangen. Es gibt drei „Abkürzung“ Tasten, die auf die „wahrscheinlich“ Beträge eingestellt werden sollte die Kassiererin das Leben leichter zu machen. Absolute Perfektion ist nicht erforderlich. - eJames (19. November um 22:28 Uhr)

Ich glaube nicht, dass es ein perfekter Algorithmus dafür ist. Wenn ich Sie wäre, würde ich eine Quelle der vorhandenen POS-Daten für eine große Anzahl von Bargeldtransaktionen zu finden und zu bewerten, dass über bestimmte Bereiche der Preise. Finden Sie, wie Menschen in der Regel zahlen für bestimmte Bereiche der Preise (genaue Veränderung ist viel wahrscheinlicher), und erarbeiten eine Best-Fit-Formel für die differenzierten Bereiche.

Answer 6

Ich war eigentlich die Person, die diese eine Umsetzung endete so dachte ich es am besten, um das Endergebnis zu veröffentlichen. Es ist nicht schön, aber es ist schnell und hat keine Schleifen oder Arrays. Ich glaube nicht, eine Lösung für die konzeptionelle Frage dies aber das praktische Problem löst.

In den meisten Fällen ist die tatsächliche Nutzung auf den $ 5 begrenzt auf 200 $ Bereich. Die meisten Menschen in der Regel nicht auf einer regelmäßigen Basis $ 500 in bar herausziehen:)

habe ich beschlossen, von $ 0 bis $ 5, $ 5 auf den verschiedenen Fällen zu schauen, um 10 $. . . $ 45 bis 50 $. Wir hatten 3 Tasten so in jedem Fall die erste Taste (niedrigste) wäre der nächste Wert $ 5 über dem Preis. Also, wenn es 7,45 $ dann 8 $ die erste Taste war, 13,34 $ -> $ 15, $ 21.01. -> 25 $

Damit bleibt die 2. und 3. Tasten. Jeder Fall hat offensichtliche Antworten die Standardwert von $ 5, $ 10, $ 20 gegeben, $ 50 Rechnungen. zB: Ein Blick auf $ 24.50 dann 1 -> $ 25, 2 -> $ 30, 3 -> 40 $. Diese können gefunden werden unter Verwendung einer Tabelle und etwas gesunden Menschenverstand.

Ich fand auch, dass mehr mit den Werten $ 50 einfach ihre unter $ 50 Kollegen passen könnte. dh: $ 72,01 wäre die gleiche Antwort wie $ 22.01, und so weiter. Die einzige Einschränkung ist, mit Zahlen, die größer als 60 und weniger als 70. Dieser Fall erfordert die Möglichkeit von 4 $ 20 Rechnungen Handhabung.

Der Algorithmus skaliert auch gut in die $ 100 bis $ 200 Bereich. Darüber befindet sich ein seltener Fall im Einzelhandel.