Алгоритм определения «обычных» денежных сумм по заданной цене

Question

Вы заходите в магазин, выбираете несколько товаров, затем идете к прилавку, чтобы оплатить счет. Общая сумма составляет (A). Вы забираете в свой кошелек, кошелек или карман и кладете немного денег (P), где P> = A, и кассир дает вам сдачу.

Учитывая набор монет и банкнот, находящихся в обращении, каковы наиболее вероятные значения для P?

Некоторые примеры, предполагающие, что доступные купюры составляют 5, 10, 20, 50 и 100 долларов, а доступные монеты 5с, 10с и 25с:

A = 151,24
P[1] = 160 (8x20) или (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

Многие из этих чисел кажутся интуитивно понятными, но у меня есть ощущение, что алгоритм сложно определить.

Answer 1

Есть и другие факторы, вы вряд ли заплатите 6 х 0,25, вы бы вместо этого использовали 1 х 1,00 и 2 х 0,25. Как правило, 0,25 будет не более 3, 0,10 будет не более 2, а 0,05 будет не более 1.

Также в реальном мире многие люди никогда не беспокоятся о значениях, меньших 1,00, они всегда расплачиваются счетами и «сохраняют изменения».

То же относится и к 5,00, 10,00 и 20,00, для покупок стоимостью более пары долларов люди вместо этого будут использовать 5,00 или 10,00. Конечно, 20,00 являются самыми распространенными в обращении благодаря банкоматам.

Для чего это программное обеспечение? Вы на самом деле пытаетесь смоделировать реальные покупки и нуждаетесь в точных результатах или в простой симуляции, которая не должна быть строгой?

Answer 2

Это на самом деле известная проблема, это вариант binpacking , если я не ошибаюсь ...

Иногда его называют алгоритмом кассира (или жадный алгоритм ). Вы можете найти реализацию в этой презентации: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf, см. Стр. 11/12/13 ..

(для пояснения, обычный алгоритм кассира возвращает только минимальное количество монет, необходимое для возврата покупателю. Но вы можете изменить решение динамического программирования для расчета всех возможных комбинаций)

Answer 3

«Скорее всего» делает это очень сложной проблемой. Вам необходимо знать относительную доступность и распределение каждого типа валюты. Например, 22% всех находящихся в обращении векселей составляют 20 долларов, что делает их гораздо более вероятными для использования, чем 10 или 50 долларов на суммы от 10 до 100 долларов.

Answer 4

На самом деле я был тем человеком, который в итоге реализовал этот, поэтому я решил, что лучше всего опубликовать конечный результат. Это не красиво, но быстро и не имеет циклов или массивов. Я не считаю это решением концептуального вопроса, но оно решает практическую проблему.

В большинстве случаев фактическое использование ограничено диапазоном от 5 до 200 долларов. Большинство людей обычно не вынимают 500 долларов наличными на регулярной основе:)

Я решил посмотреть на различные случаи от 0 до 5 долларов, от 5 до 10 долларов. , , От 45 до 50 долларов. У нас было 3 кнопки, поэтому в каждом случае первая кнопка (самая низкая) будет следующей ценой в 5 долларов выше цены. Таким образом, если это было 7,45 доллара, то первая кнопка была 8 долларов, 13,34 доллара -> 15 долларов, 21,01 доллара -> 25 долларов.

Это оставляет 2-ю и 3-ю кнопки. Каждый случай имеет очевидные ответы, учитывая стандартные значения 5, 10, 20, 50 долларов. Например: Глядя на $ 24,50, затем 1 -> 25 долларов, 2 -> 30 долларов, 3 -> 40 долларов. Их можно найти, используя таблицу и здравый смысл.

Я также обнаружил, что использование значений, превышающих 50 долларов, может просто соответствовать их аналогам ниже 50 долларов. то есть: $ 72,01 будет таким же ответом, как $ 22,01, и так далее. Единственное предостережение с числами больше 60 и меньше 70. В этом случае требуется возможность обработки 4 долларов 20 счетов.

Алгоритм также хорошо масштабируется в диапазоне от 100 до 200 долларов. Выше это редкий случай в рознице.

Answer 5

Это для системы торговых точек. Когда рассчитывается окончательная цена, кассир должен ввести сумму, указанную клиентом. Есть три кнопки быстрого доступа, которые должны быть установлены на «вероятные» суммы, чтобы облегчить жизнь кассира. Абсолютное совершенство не обязательно. - eJames (19 ноября в 22:28)

Я не думаю, что есть идеальный алгоритм для этого. Если бы я был вами, я бы нашел источник существующих данных POS для большого количества операций с наличными и оценил бы их по определенным диапазонам цен. Узнайте, как люди обычно платят за определенные диапазоны цен (точные изменения гораздо более вероятны), и разработайте оптимальную формулу для наиболее дифференцированных диапазонов.

Answer 6

ОН! @ # $% ^ & * () _, Теперь я действительно взволнован.

Я только что написал псевдокод и оценку сложности за 10 минут, и когда я отправляю сообщение, есть просто кнопка «Я человек» без какой-либо возможности ввести что-то, и мой полный пост пропал (и, конечно, на этот раз я не сделал копию окна редактирования, на всякий случай ...), хорошо, так вот короткая версия:

Количество монет обычно супер монотонное (т. Е. Каждое значение> суммы предыдущих значений), поэтому вы можете использовать жадные алгоритмы, чтобы получить точные монеты для A.

Теперь используйте этот множественный набор монет P, добавьте его в (до сих пор пустой) результирующий набор (набор мультимножеств) и в рабочий (до сих пор тоже пустой) набор.

Теперь повторяйте, пока рабочий набор не станет пустым:

Извлечь множество P из рабочего набора, P '= P, для каждой монеты c в P: P' = P.replace (c, nextBiggerCoin), removeSmallestCoin (пока P без самой маленькой монеты все еще> A)

Если P 'еще не находится в наборе результатов, поместите его в набор результатов и рабочий набор

Моя предполагаемая сложность была O (s * n ^ 2), с s количество решений.