Algoritmo per determinare il & # 8220; usuale & # 8221; importi di pagamento in contanti per un determinato prezzo

Question

Entrate in un negozio, selezionate diversi prodotti, quindi andate al bancone per pagare il conto. Il totale è un importo ( A ). Ti infili nel portafoglio, nella borsa o nella tasca e metti un po 'di denaro ( P ), dove P > = A e la cassa ti dà il resto.

Dato l'insieme di monete e banconote in circolazione, quali sono i valori più probabili per P ?

Alcuni esempi, supponendo che le fatture disponibili siano $ 5, $ 10, $ 20, $ 50 e $ 100 e le monete disponibili siano 5c, 10c e 25c:

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

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

A = $ 0,95
P [1] = $ 1 (4 x 25c)
P [2] = $ 5

Molti di questi numeri sembrano intuitivi, ma ho la sensazione che l'algoritmo sia difficile da definire.

Answer 1

Ci sono anche altri fattori, non è probabile che tu paghi con 6 x 0,25, invece utilizzeresti 1 x 1,00 e 2 x 0,25. Generalmente 0,25 non sarebbe più di 3, 0,10 non sarebbe più di 2 e 0,05 non sarebbe più di 1.

Anche nel mondo reale, molte persone non si preoccupano mai di valori inferiori a 1,00, pagano sempre con fatture e "mantengono il cambiamento".

Lo stesso vale per le 5.00, le 10.00 e le 20.00, per gli acquisti più di un paio di dollari le persone useranno invece le 5.00 o le 10.00. Naturalmente le 20.00 sono le più diffuse in circolazione grazie ai bancomat.

A cosa serve questo software? stai effettivamente provando acquisti effettivi modello e hai bisogno di risultati accurati o una semplice simulazione che non deve essere rigorosa?

Answer 2

" Molto probabilmente " rende questo un problema molto complicato. Dovresti conoscere la relativa disponibilità e distribuzione di ciascun tipo di valuta. Ad esempio, il 22% di tutte le fatture in circolazione sono $ 20, il che rende molto più probabile che vengano utilizzate rispetto a $ 10 o $ 50 per importi compresi tra $ 10 e $ 100.

Answer 3

Questo è in realtà un problema noto, è una variante di binpacking se non lo sono sbaglia ...

A volte viene chiamato l'algoritmo di cassa (o algoritmo goloso ). È possibile trovare un'implementazione in questa presentazione: http: // www. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf , vedi pagina 12/11/13 ..

(per chiarire, l'algoritmo dei cassieri normali restituisce solo la quantità minima di monete necessarie per rimborsare il cliente. Ma è possibile modificare la soluzione di programmazione dinamica per calcolare tutte le possibili combinazioni)

Answer 4

OH! @ # $% ^ & amp; * () _, ora sono davvero felice ...

Ho appena scritto pseudocodice e stima della complessità per 10 minuti, e quando inserisco c'è solo il pulsante "Sono un essere umano" senza alcuna possibilità di inserire qualcosa e il mio post completo non c'è più (e ovviamente, questa volta non ho fatto una copia della finestra di modifica, per ogni evenienza ...), ok, ecco la versione breve:

Numero di monete di solito super monotone (cioè ogni valore è > rispetto alla somma dei valori precedenti), quindi puoi usare avido per ottenere le monete esatte per A.

Ora usa questa serie multipla di monete, aggiungila al set di risultati (fino ad ora vuoto) (un set di multiset) e al set di lavoro (fino ad ora vuoto).

Ora ripeti finché il set di lavoro non è vuoto:

Prendi il set P dal set di lavoro, P '= P, per ogni moneta c in P: P' = P.replace (c, nextBiggerCoin), rimuovi SmallCoin (purché P senza la moneta più piccola sia ancora > A)

Se la P 'non è ancora nel set di risultati, inseriscilo nel set di risultati e nel working set

La mia ipotesi complessità era O (s * n ^ 2), con s il numero di soluzioni.

Answer 5

  

È per un sistema di punti vendita. Quando viene calcolato il prezzo finale, il cassiere deve inserire l'importo in contanti fornito dal cliente. Esistono tre "scorciatoie". pulsanti che dovrebbero essere impostati sul "probabile" equivale a semplificare la vita del cassiere La perfezione assoluta non è necessaria. & # 8211; eJames (19 novembre alle 22:28)

Non penso che ci sia un algoritmo perfetto per questo. Se fossi in te, troverei una fonte di dati POS esistenti per un gran numero di transazioni in contanti e lo valuterei su particolari intervalli di prezzi. Scopri come le persone di solito pagano per specifiche fasce di prezzo (la variazione esatta è molto più probabile) e trova una formula più adatta alle gamme più differenziate.

Answer 6

In realtà ero la persona che ha finito per implementare questo, quindi ho pensato che fosse meglio pubblicare il risultato finale. Non è carino ma è veloce e non ha loop o array. Non lo considero una soluzione alla domanda concettuale, ma risolve il problema pratico.

Nella maggior parte dei casi, l'utilizzo effettivo è limitato a un intervallo compreso tra $ 5 e $ 200. La maggior parte delle persone di solito non preleva regolarmente $ 500 in contanti :)

Ho deciso di esaminare i vari casi da $ 0 a $ 5, da $ 5 a $ 10,. . . $ 45 a $ 50. Avevamo 3 pulsanti, quindi in ogni caso, il primo pulsante (più basso) sarebbe il prossimo valore di $ 5 sopra il prezzo. Quindi, se era $ 7,45, allora $ 8 era il primo pulsante, $ 13,34 - > $ 15, $ 21,01 - & GT; $ 25.

Questo lascia i pulsanti 2 ° e 3 °. Ogni caso ha risposte ovvie dati i valori standard di $ 5, $ 10, $ 20, $ 50 fatture. ad es .: guardando $ 24,50, quindi 1- $ 25, 2- $ $ 30, 3- $ 40 $. Questi possono essere trovati usando una tabella e un po 'di buon senso.

Ho anche scoperto che l'uso di valori maggiori di $ 50 potrebbe semplicemente corrispondere ai loro equivalenti inferiori a $ 50. vale a dire: $ 72,01 sarebbe la stessa risposta di $ 22,01 e così via. L'unica avvertenza è con numeri maggiori di 60 e inferiori a 70. In questo caso è necessario gestire la possibilità di 4 $ 20 fatture.

L'algoritmo si adatta bene anche nell'intervallo da $ 100 a $ 200. Sopra questo è un caso raro nel commercio al dettaglio.