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

Question

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

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

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

A = $ 151,24
P[1] = $ 160 (8x $ 20) или (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 х 25с)
P[2] = $ 5

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

Answer 1

Есть и другие факторы, вы вряд ли заплатите 6 x 0,25, вместо этого вы должны использовать 1 x 1,00 и 2 x 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

OH! @ # $%^& *() _, теперь я действительно pi..ed.

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

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

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

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

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

Если Р»не в наборе результатов, поместите его в результирующий набор и рабочий набор

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

В большинстве случаев фактическое использование ограничено диапазоном от 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. Выше это редкий случай в розничной торговле.