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

Question

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

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

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

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 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

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

Answer 3

На самом деле это известная проблема, это вариант упаковки пакетов , если я не ошибается ...

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

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

Answer 4

О! @ # $% ^ & amp; * () _, теперь я действительно обижен.

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

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

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

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

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

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

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

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-х долларовых купюр.

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