Algoritmo para determinar os valores de pagamento em dinheiro “habituais” para um determinado preço

Question

Você anda em uma loja, selecione vários produtos, em seguida, ir ao balcão para pagar a sua factura. O total é de uma certa quantidade (A). Você chegar em sua carteira, bolsa ou bolso e colocar algum dinheiro (P), onde P> = A, eo caixa dá-lhe mudar.

Dado o conjunto de moedas e notas que estão em circulação, quais são os valores mais prováveis ??para P?

Alguns exemplos, assumindo que as contas disponíveis são de US $ 5, $ 10, $ 20, $ 50 e $ 100, e as moedas disponíveis são 5c, 10c e 25c:

A = $ 151,24
P[1] = $ 160.º (8x $ 20) ou ($ 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

Muitos desses números parecem intuitivo, mas tenho a sensação de que o algoritmo é difícil de definir.

Answer 1

Há também outros fatores, que não são susceptíveis de pagar com 6 x 0,25, você usaria 1 x 1,00 e 2 x 0,25 vez. Geralmente 0,25 haveria mais, em seguida, 3, 0,10 haveria mais, em seguida, 2, e 0,05 haveria mais, em seguida, 1.

Além disso, no mundo real, muitas pessoas nunca se preocupar com valores menos de 1,00, eles alawys pagamento com contas e "manter a mudança".

O mesmo se aplica a 5.00, 10.00 e 20.00, para a compra de mais de um par de dólares as pessoas vão usar um 5,00 ou 10,00 vez. Claro 20,00 são as mais comuns em circulação graças a máquinas ATM.

O que é este software para? você está realmente tentando modelo compras reais e precisa de resultados precisos, ou uma simulação simples, que não tem que ser rigoroso?

Answer 2

"O mais provável" torna este um problema muito complicado. Você precisa saber a disponibilidade relativa e distribuição de cada tipo de moeda. Por exemplo, 22% de todas as contas em circulação é de US $ 20, tornando-os muito mais propensos a ser usado de US $ 10 ou US $ 50 contas para valores entre $ 10 e $ 100.

Answer 3

Este é realmente um problema conhecido, é uma variante do binpacking se eu não sou enganado ...

Às vezes é chamado o algoritmo de caixas (ou algoritmo guloso). Você pode encontrar uma implementação nesta apresentação: http: // www. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf , consulte a página 11/12/13 ..

(para esclarecer, os caixas normais algoritmo retorna apenas a quantidade mínima de moedas necessárias para pagar a parte de trás do cliente. Mas você pode mudar a solução de programação dinâmica para calcular todas as combinações possíveis)

Answer 4

OH! @ # $% ^ & * () _, Agora estou realmente pi..ed.

Eu só escreveu pseudocódigo e estimativa de complexidade por 10 minutos, e quando eu posto há apenas o botão "Eu sou um ser humano", sem qualquer oportunidade de entrar em alguma coisa e meu post completo está desaparecido (e, claro, desta vez eu não fazer uma cópia da janela de edição, apenas no caso ...), ok isso aqui estão a versão curta:

Número de moedas normalmente super-monótona (ou seja, cada valor é> que a soma dos valores anteriores), e por isso você pode usar ganancioso para obter as moedas exatas para A.

Agora use este conjunto de multi P de moedas, adicioná-lo à (até agora vazia) conjunto de resultados (um conjunto de multisets), e para o (até agora muito vazio) conjunto de trabalho.

Agora repita até que o conjunto de trabalho está vazia:

Tome conjunto P para fora do conjunto de trabalho, P '= P, para cada moeda c em P: P' = P.replace (c, nextBiggerCoin), removeSmallestCoin (enquanto P sem menor moeda ainda> A)

Se o P' ainda não está em conjunto de resultados, colocá-lo em conjunto de resultados e conjunto de trabalho

Meu complexidade imaginado era O (s * n ^ 2), com é o número de soluções.

Answer 5

É um sistema de ponto-de-venda. Quando o preço final é calculado, o caixa tem que entrar na quantidade de dinheiro fornecido pelo cliente. Há três botões "atalho" que devem ser definidas para os "prováveis" quantidades para tornar a vida do caixa mais fácil. A perfeição absoluta não é necessário. - eJames (Nov 19 em 22:28)

Eu não acho que há um algoritmo perfeito para isso. Se eu fosse você, eu iria encontrar uma fonte de dados de POS existente para um grande número de transações em dinheiro e avaliar que as gamas mais específicas de preços. Veja como as pessoas costumam pagar por intervalos específicos de preços (mudança exata é muito mais provável), e elaborar uma fórmula melhor ajuste para as gamas mais diferenciados.

Answer 6

Eu estava realmente a pessoa que acabou implementando este assim que achei melhor para deixar o resultado final. Não é bonito, mas é rápido e não tem nenhum loops ou matrizes. Eu não considero isso uma solução para a questão conceitual, mas não resolve o problema prático.

Na maioria das situações, o uso real é limitada à faixa de US $ 5 a US $ 200. A maioria das pessoas não costumam puxar para fora $ 500 em dinheiro em uma base regular:)

Eu decidi olhar para os vários casos de $ 0 a US $ 5, US $ 5 a US $ 10,. . . US $ 45 a $ 50. Nós tivemos 3 botões para que em todos os casos, o primeiro botão (mais baixo) seria o próximo valor R $ 5 acima do preço. Então, se ele foi de US $ 7,45, em seguida, $ 8 foi o primeiro botão, $ 13,34 -> $ 15, $ 21,01 -.> $ 25

Isso deixa os botões de 2º e 3º. Cada caso tem respostas óbvias dado os valores padrão de US $ 5, $ 10, $ 20, $ 50 contas. por exemplo: Olhando $ 24,50, em seguida, 1 -> $ 25, 2 -> $ 30, 3 -> $ 40. Estes podem ser encontrados usando uma mesa e algum senso comum.

Eu também achei que usando valores maior $ 50 poderia simplesmente combinar suas abaixo $ 50 homólogos. ou seja: $ 72,01 seria a mesma resposta quanto $ 22,01, e assim por diante. A única ressalva é com números superiores a 60 e inferior a 70. Esse caso requer lidar com a possibilidade de 4 $ 20 contas.

O algoritmo também dimensiona muito bem na faixa de US $ 100 a US $ 200. Acima disso é um caso raro no varejo.