Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Математическое определение [ править ]

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

при условии

Примеры без валюты [ править ]

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

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

Методы решения [ править ]

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

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

Реализация [ править ]

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

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

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

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

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

Жадный метод [ править ]

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

Связанные проблемы [ править ]

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л .; Стейн, Клиффорд (2009). Введение в алгоритмы . MIT Press. Задача 16-1, с. 446.
  2. ^ Гудрич, Майкл Т .; Тамассия, Роберто (2015). Разработка алгоритмов и приложения . Вайли. Упражнение A-12.1, с. 349.
  3. ^ Райт, JW (1975). «Проблема внесения изменений». Журнал Ассоциации вычислительной техники . 22 (1): 125–128. DOI : 10.1145 / 321864.321874 .
  4. ^ Serang, О. (2012). «Вероятностное дерево свертки: эффективный точный байесовский вывод для более быстрого вывода белков с помощью ЖХ-МС / МС» . PLOS ONE . 9 (3): e91507. Bibcode : 2014PLoSO ... 991507S . DOI : 10.1371 / journal.pone.0091507 . PMC 3953406 . PMID 24626234 .  CS1 maint: ref = harv ( ссылка )
  5. ^ Пирсон, Дэвид (2005). «Алгоритм с полиномиальным временем решения проблемы внесения изменений». Письма об исследованиях операций . 33 (3): 231–234. DOI : 10.1016 / j.orl.2004.06.001 . ЛВП : 1813/6219 . Руководство по ремонту 2108270 . 
  6. ^ J. Shallit (2003). «Этой стране нужна монета 18 центов» (PDF) . Математический интеллигент . 25 (2): 20–23. DOI : 10.1007 / BF02984830 .

Дальнейшее чтение [ править ]

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