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

Есть и другие факторы: вы вряд ли будете платить 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 являются наиболее распространенными в обращении благодаря банкоматам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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