Algorithme pour déterminer les montants de paiement en espèces «habituels» pour un prix donné

Question

Vous entrez dans un magasin, sélectionnez plusieurs produits, puis rendez-vous au comptoir pour payer votre facture. Le total est un certain montant ( A ). Vous accédez à votre portefeuille, à votre sac à main ou à votre poche et déposez de l'argent ( P ), où P > = A et le caissier vous donne le changement.

Étant donné l'ensemble des pièces et des billets en circulation, quelles sont les valeurs les plus probables pour P ?

Quelques exemples, en supposant que les billets disponibles sont 5 $, 10 $, 20 $, 50 $ et 100 $ et que les pièces disponibles sont 5c, 10c et 25c:

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

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

P [3] = 40 $ (20 $ + 20 $)

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

Beaucoup de ces chiffres semblent intuitifs, mais j’ai le sentiment que l’algorithme est difficile à cerner.

Answer 1

Il y a aussi d'autres facteurs, vous ne payerez probablement pas avec 6 x 0,25, vous utiliseriez plutôt 1 x 1,00 et 2 x 0,25. Généralement 0,25 ne serait pas plus de 3, 0,10 ne serait pas plus de 2 et 0,05 ne serait pas plus de 1.

De même, dans le monde réel, de nombreuses personnes ne s’inquiètent jamais des valeurs inférieures à 1,00, elles paient toujours avec des factures et "conservent les modifications".

Même chose pour 5.00, 10.00 et 20.00, pour des achats de plus de quelques dollars, les utilisateurs utiliseront un 5.00 ou 10.00 au lieu de cela. Bien sûr, 20,00 sont les plus courants en circulation grâce aux distributeurs automatiques de billets.

À quoi sert ce logiciel? essayez-vous réellement de modéliser des achats réels et avez-vous besoin de résultats précis? Ou bien d'une simple simulation qui ne doit pas forcément être rigoureuse?

Answer 2

" Probablement " rend ce problème très délicat. Vous devez connaître la disponibilité et la distribution relatives de chaque type de devise. Par exemple, 22% de tous les billets en circulation coûtent 20 dollars, ce qui les rend beaucoup plus susceptibles d’être utilisés que des billets de 10 ou 50 dollars pour des montants compris entre 10 et 100 dollars.

Answer 3

C’est un problème connu, c’est une variante de binpacking si je ne le suis pas. se tromper ...

Parfois, on l'appelle l'algorithme de la caisse (ou l'algorithme glouton ). Vous pouvez trouver une implémentation dans cette présentation: http: // www. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf , voir page 11/12/13 ..

(pour clarifier, l’algorithme de la caisse normale ne renvoie que le minimum de pièces nécessaires pour rembourser le client. Mais vous pouvez modifier la solution de programmation dynamique pour calculer toutes les combinaisons possibles)

Answer 4

OH! @ # $% ^ & amp; * () _, maintenant je suis vraiment inquiet.

Je viens d'écrire une estimation de la complexité et du pseudo-code pendant 10 minutes, et lorsque je poste, il ne reste plus que le bouton "Je suis un être humain". sans aucune possibilité de saisir quelque chose et mon message complet est parti (et bien sûr, cette fois-ci, je n'ai pas fait de copie de la fenêtre de modification, juste au cas où ...), ok voici la version courte:

Nombre de pièces généralement super monotones (c'est-à-dire que chaque valeur est supérieure à la somme des valeurs précédentes), vous pouvez donc utiliser les mots gourmands pour obtenir les pièces exactes de A.

Maintenant, utilisez ce jeu de pièces multi, ajoutez-le au jeu de résultats (un jeu de multisets) (et jusqu’à présent vide), ainsi qu’au jeu de travail (également vide jusqu’à présent).

Répétez l'opération jusqu'à ce que le groupe de travail soit vide:

Prenez l'ensemble P de l'ensemble de travail, P '= P, pour chaque pièce de monnaie c dans P: P' = P.replace (c, nextBiggerCoin), supprimezSmallestCoin (tant que P ne contient pas encore la plus petite pièce > A)

Si le P 'n'est pas encore dans le jeu de résultats, placez-le dans le jeu de résultats et dans le jeu de travail

Ma supposée complexité était O (s * n ^ 2), avec s le nombre de solutions.

Answer 5

  

Il s’agit d’un système de point de vente. Lorsque le prix final est calculé, le caissier doit entrer le montant en espèces fourni par le client. Il existe trois " raccourcis " boutons qui doivent être réglés sur le bouton "probable" des montants pour faciliter la vie du caissier. La perfection absolue n'est pas nécessaire. & # 8211; eJames (19 nov à 22h28)

Je ne pense pas qu’il existe un algorithme parfait pour cela. Si j'étais vous, je trouverais une source de données de PDV existantes pour un grand nombre de transactions en espèces et l'évaluerais sur des fourchettes de prix particulières. Trouvez comment les gens paient habituellement pour des gammes de prix spécifiques (le changement exact est beaucoup plus probable) et trouvez la formule la mieux adaptée pour les fourchettes les plus différenciées.

Answer 6

J'étais en fait la personne qui a finalement implémenté celui-ci, alors j'ai jugé préférable d'afficher le résultat final. Ce n'est pas joli mais c'est rapide et n'a pas de boucles ou de tableaux. Je ne considère pas cela comme une solution à la question conceptuelle mais cela résout le problème pratique.

Dans la plupart des cas, l’utilisation réelle est limitée à 5 $ à 200 $. La plupart des gens ne retirent généralement pas 500 dollars en espèces de façon régulière:)

J’ai décidé d’examiner les différents cas allant de 0 à 5 dollars, de 5 à 10 dollars. . . 45 $ à 50 $. Nous avions 3 boutons donc dans tous les cas, le premier bouton (le plus bas) serait la prochaine valeur de 5 $ au-dessus du prix. Donc, si c'était 7,45 $ alors 8 $ était le premier bouton, 13,34 $ - > 15 USD, 21,01 USD - > 25 $.

Cela laisse les 2ème et 3ème boutons. Chaque cas a des réponses évidentes compte tenu des valeurs standard de billets de 5, 10, 20 et 50 dollars. Par exemple: En regardant 24,50 $ puis 1-> 25 $, 2-> 30 $, 3-> 40 $. Ceux-ci peuvent être trouvés en utilisant un tableau et un peu de bon sens.

J'ai également constaté que l'utilisation de valeurs supérieures à 50 USD pourrait simplement correspondre à leurs équivalents inférieurs à 50 USD. c'est-à-dire que 72,01 $ correspondrait à la même réponse que 22,01 $, et ainsi de suite. La seule réserve concerne les numéros supérieurs à 60 et inférieurs à 70. Cette affaire nécessite la possibilité de traiter 4 billets de 20 $.

L’algorithme évolue également dans la plage de 100 à 200 dollars. Au-dessus, il s’agit d’un cas rare dans le commerce de détail.