Проблема внесения изменений - Change-making problem

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

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

это слабо NP-жесткий, но может быть решена оптимально в псевдополиномиальное время от динамическое программирование.[1][2]

Математическое определение

Стоимость монет может быть смоделирована набором п отчетливый положительный целое число значения (целые числа), расположенные в порядке возрастания как ш1 через шп. Проблема в том, что с учетом суммы W, также положительное целое число, чтобы найти набор неотрицательных (положительных или нулевых) целых чисел {Икс1, Икс2, ..., Иксп}, с каждым Иксj показывает, как часто монета с достоинством шj используется, что минимизирует общее количество монет ж(W)

при условии

Примеры без валюты

Приложение к проблеме внесения изменений можно найти в вычислении способов сделать девять дротиков в игре в дартс.

Другое приложение - вычисление возможного атомного (или изотопного) состава данного пика массы / заряда в масс-спектрометрии.

Методы решения

Простое динамическое программирование

Классический динамическое программирование стратегия работает вверх, находя комбинации всех меньших значений, которые суммируются с текущим порогом.[3] Таким образом, на каждом пороге потенциально считается, что все предыдущие пороги повышаются до целевой суммы. W. По этой причине этот подход динамического программирования требует количества шагов, равного O (nW), где п количество типов монет.

Реализация

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

def _get_change_making_matrix(set_of_coins, р: int):    м = [[0 для _ в ассортимент(р + 1)] для _ в ассортимент(len(set_of_coins) + 1)]    для я в ассортимент(1, р + 1):        м[0][я] = плавать('inf')  # По умолчанию нет возможности внести изменения    вернуть мdef change_making(монеты, п: int):    "" "Эта функция предполагает, что все монеты доступны бесконечно.    n - это число, которое нужно получить с наименьшим количеством монет.    монеты - это список или кортеж с доступными номиналами.    """    м = _get_change_making_matrix(монеты, п)    для c в ассортимент(1, len(монеты) + 1):        для р в ассортимент(1, п + 1):            # Просто используйте монеты монеты [c - 1].            если монеты[c - 1] == р:                м[c][р] = 1            # монеты [c - 1] не могут быть включены.            # Используйте предыдущее решение для создания r,            # без монет [c - 1].            Элиф монеты[c - 1] > р:                м[c][р] = м[c - 1][р]            Можно использовать # монеты [c - 1].            # Решите, какое из следующих решений является лучшим:            # 1. Использование предыдущего решения для создания r (без использования монет [c - 1]).            # 2. Использование предыдущего решения для создания r - монет [c - 1] (без            # используя монеты [c - 1]) плюс эта 1 дополнительная монета.            еще:                м[c][р] = мин(м[c - 1][р], 1 + м[c][р - монеты[c - 1]])    вернуть м[-1][-1]

Динамическое программирование с вероятностным деревом свертки

Вероятностное дерево свертки[4] также может использоваться как более эффективный подход к динамическому программированию. Вероятностное дерево свертки объединяет пары монет для получения всех сумм, которые могут быть созданы этой парой монет (при отсутствии ни одной монеты, только первой монеты, только второй монеты и наличия обеих монет), а затем последующее объединение пар из этих объединенных результатов таким же образом. Этот процесс повторяется до тех пор, пока два последних набора результатов не будут объединены в один, что приведет к сбалансированному двоичному дереву с Журнал W (Вт) такие операции слияния. Кроме того, путем дискретизации достоинств монеты каждая из этих операций слияния может выполняться посредством свертки, что часто может выполняться более эффективно с помощью быстрое преобразование Фурье (БПФ). Таким образом, вероятностное дерево свертки может использоваться для достижения решения за субквадратичное число шагов: каждая свертка может выполняться за п журнал (п), а начальные (более многочисленные) операции слияния используют меньшую п, а более поздние (менее многочисленные) операции требуют п в порядке W.

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

Жадный метод

Для так называемых канонических монетных систем, подобных тем, которые используются в США и многих других странах, жадный алгоритм Выбор монет самого большого достоинства, не превышающего оставшуюся сумму, даст оптимальный результат.[5] Однако это не относится к произвольным системам монет. Например, если номиналы монет были 1, 3 и 4, то для получения 6 жадный алгоритм выбрал бы три монеты (4,1,1), тогда как оптимальное решение - две монеты (3,3).

Связанные проблемы

"Оптимальный деноминация проблема "[6] это проблема для людей, которые разрабатывают совершенно новые валюты. Он спрашивает, какой номинал следует выбрать для монет, чтобы минимизировать среднюю стоимость внесения сдачи, то есть среднее количество монет, необходимое для внесения сдачи? Версия этой задачи предполагала, что люди, производящие сдачу, будут использовать минимальное количество монет (из доступных номиналов). Один из вариантов этой проблемы предполагает, что люди, вносящие изменения, будут использовать «жадный алгоритм» для внесения изменений, даже если для этого требуется больше, чем минимальное количество монет. В большинстве текущих валют используется 1-2-5 серии, но для некоторых других номиналов потребуется меньшее количество монет или меньшее среднее количество монет для сдачи или и то, и другое.

Смотрите также

использованная литература

  1. ^ Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л .; Стейн, Клиффорд (2009). Введение в алгоритмы. MIT Press. Задача 16-1, с. 446.
  2. ^ Гудрич, Майкл Т .; Тамассия, Роберто (2015). Разработка алгоритмов и приложения. Вайли. Упражнение A-12.1, с. 349.
  3. ^ Райт, Дж. У. (1975). «Проблема внесения изменений». Журнал Ассоциации вычислительной техники. 22 (1): 125–128. Дои:10.1145/321864.321874.
  4. ^ Серанг, О. (2012). «Вероятностное дерево свертки: эффективный точный байесовский вывод для более быстрого вывода белков с помощью ЖХ-МС / МС». PLOS ONE. 9 (3): e91507. Bibcode:2014PLoSO ... 991507S. Дои:10.1371 / journal.pone.0091507. ЧВК  3953406. PMID  24626234.CS1 maint: ref = harv (ссылка на сайт)
  5. ^ Сюань Цай (2009). «Канонические монетные системы для проблем, связанных с ИЗМЕНЕНИЯми». Труды Девятой Международной конференции по гибридным интеллектуальным системам. 1: 499–504. arXiv:0809.0400. Дои:10.1109 / HIS.2009.103.
  6. ^ Дж. Шаллит (2003). «Этой стране нужна монета 18 центов» (PDF). Математический интеллигент. 25 (2): 20–23. Дои:10.1007 / BF02984830.

дальнейшее чтение

  • М. Адамашек, А. Невяровска (2010). «Комбинаторика проблемы изменения». Европейский журнал комбинаторики. 31 (1): 47–63. arXiv:0801.0120. Дои:10.1016 / j.ejc.2009.05.002.