Algoritmo para determinar los montos de pago en efectivo "habituales" para un precio determinado

Question

Entras en una tienda, seleccionas varios productos y luego vas al mostrador para pagar tu factura. El total es una cantidad ( A ). Metió la mano en su billetera, cartera o bolsillo y dejó algo de efectivo ( P ), donde P > = A , y el cajero te da el cambio.

Dado el conjunto de monedas y billetes que están en circulación, ¿cuáles son los valores más probables para P ?

Algunos ejemplos, suponiendo que las facturas disponibles son $ 5, $ 10, $ 20, $ 50 y $ 100, y las monedas disponibles son 5c, 10c y 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

Muchos de estos números parecen intuitivos, pero tengo la sensación de que el algoritmo es difícil de precisar.

Answer 1

También hay otros factores, no es probable que pague con 6 x 0.25, en su lugar usaría 1 x 1.00 y 2 x 0.25. Generalmente 0.25 no sería más que 3, 0.10 no sería más que 2 y 0.05 no sería más que 1.

También en el mundo real, muchas personas nunca se molestan con valores inferiores a 1.00, siempre pagan con facturas y "mantienen el cambio".

Lo mismo se aplica a 5.00, 10.00 y 20.00, para compras de más de un par de dólares, las personas usarán 5.00 o 10.00 en su lugar. Por supuesto, las 20.00 son las más comunes en circulación gracias a los cajeros automáticos.

¿Para qué es este software? ¿realmente está intentando comprar modelos reales y necesita resultados precisos, o una simulación simple que no tiene que ser rigurosa?

Answer 2

" Lo más probable " hace que este sea un problema muy complicado. Debería saber la disponibilidad relativa y la distribución de cada tipo de moneda. Por ejemplo, el 22% de todas las facturas en circulación son $ 20, por lo que es mucho más probable que se usen que las facturas de $ 10 o $ 50 por montos entre $ 10 y $ 100.

Answer 3

Esto es realmente un problema conocido, es una variante de binpacking si no estoy equivocado ...

A veces se llama algoritmo de cajero (o algoritmo codicioso ). Puede encontrar una implementación en esta presentación: http: // www. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf , vea la página 11/12/13 ..

(para aclarar, el algoritmo de cajero normal solo devuelve la cantidad mínima de monedas necesarias para devolver al cliente. Pero podría cambiar la solución de programación dinámica para calcular todas las combinaciones posibles)

Answer 4

OH! @ # $% ^ & amp; * () _, ahora estoy realmente pi..ed.

Acabo de escribir pseudocódigo y estimación de complejidad durante 10 minutos, y cuando publico solo aparece el botón "Soy un ser humano" sin ninguna oportunidad de ingresar algo y mi publicación completa se ha ido (y, por supuesto, esta vez no hice una copia de la ventana de edición, por si acaso ...), ok, aquí está la versión corta:

Número de monedas generalmente super monótono (es decir, cada valor es > que la suma de los valores anteriores), por lo tanto, puede usar codicioso para obtener las monedas exactas para A.

Ahora use este conjunto múltiple de monedas P, agréguelo al conjunto de resultados (hasta ahora vacío) (un conjunto de conjuntos múltiples) y al conjunto de trabajo (hasta ahora también vacío).

Ahora repita hasta que el conjunto de trabajo esté vacío:

Saque el conjunto P del conjunto de trabajo, P '= P, para cada moneda c en P: P' = P.replace (c, nextBiggerCoin), retireSmallestCoin (siempre que P sin la moneda más pequeña todavía > A)

Si la P 'aún no está en el conjunto de resultados, colóquela en el conjunto de resultados y en el conjunto de trabajo

Mi complejidad adivinada era O (s * n ^ 2), con s el número de soluciones.

Answer 5

  

Es para un sistema de punto de venta. Cuando se calcula el precio final, el cajero tiene que ingresar la cantidad de efectivo provista por el cliente. Hay tres '' atajos '' botones que deben establecerse en " probable " equivale a facilitar la vida del cajero. La perfección absoluta no es necesaria. - eJames (19 de noviembre a las 22:28)

No creo que haya un algoritmo perfecto para esto. Si yo fuera usted, encontraría una fuente de datos POS existentes para una gran cantidad de transacciones en efectivo y la evaluaría en rangos particulares de precios. Descubra cómo las personas suelen pagar rangos de precios específicos (el cambio exacto es mucho más probable) y elabore una fórmula que se ajuste mejor a los rangos más diferenciados.

Answer 6

En realidad, fui la persona que terminó implementando este, así que pensé que era mejor publicar el resultado final. No es bonito, pero es rápido y no tiene ningún bucle o matriz. No considero que esto sea una solución a la pregunta conceptual, pero resuelve el problema práctico.

En la mayoría de las situaciones, el uso real está limitado al rango de $ 5 a $ 200. La mayoría de las personas no suelen sacar $ 500 en efectivo de forma regular :)

Decidí mirar los diversos casos de $ 0 a $ 5, $ 5 a $ 10,. . . $ 45 a $ 50. Teníamos 3 botones, así que en todos los casos, el primer botón (el más bajo) sería el siguiente valor de $ 5 por encima del precio. Entonces, si fue $ 7.45, entonces $ 8 fue el primer botón, $ 13.34 - > $ 15, $ 21.01 - > $ 25.

Esto deja los botones segundo y tercero. Cada caso tiene respuestas obvias dados los valores estándar de billetes de $ 5, $ 10, $ 20, $ 50. por ejemplo: mirar $ 24.50 y luego 1- > $ 25, 2- > $ 30, 3- > $ 40. Estos se pueden encontrar usando una tabla y algo de sentido común.

También descubrí que el uso de valores superiores a $ 50 podría simplemente coincidir con sus equivalentes inferiores a $ 50. es decir: $ 72.01 sería la misma respuesta que $ 22.01, y así sucesivamente. La única advertencia es con números mayores que 60 y menores que 70. Ese caso requiere manejar la posibilidad de 4 billetes de $ 20.

El algoritmo también escala muy bien en el rango de $ 100 a $ 200. Por encima de eso es un caso raro en el comercio minorista.