Проблема внесения изменений - Change-making problem
Проблема внесения сдачи связана с поиском минимального количества монет (определенных номиналов), которые в сумме составляют заданную сумму денег. Это частный случай задачи о целочисленном рюкзаке , и его применение шире, чем просто валюта.
Это также наиболее распространенный вариант проблемы размены монет , общий случай разделения, в котором, учитывая доступные номиналы бесконечного набора монет, цель состоит в том, чтобы выяснить количество возможных способов внесения размены для конкретного количество денег без учета порядка монет.
Это слабо NP-сложно , но может быть решено оптимально за псевдополиномиальное время с помощью динамического программирования .
Математическое определение
Стоимость монет может быть смоделирована набором из n различных положительных целых чисел (целых чисел), расположенных в порядке возрастания от w 1 до w n . Проблема заключается в следующем: для заданного количества W , которое также является положительным целым числом, найти набор неотрицательных (положительных или нулевых) целых чисел { x 1 , x 2 , ..., x n }, где каждый x j представляет, как часто используется монета номиналом w j , что минимизирует общее количество монет f ( W )
при условии
Примеры без валюты
Приложение к проблеме внесения изменений можно найти в вычислении способов, которыми можно добиться финиша из девяти дротиков в игре в дартс.
Другое приложение - вычисление возможного атомного (или изотопного) состава данного пика массы / заряда в масс-спектрометрии.
Методы решения
Простое динамическое программирование
Классическая стратегия динамического программирования работает вверх, находя комбинации всех меньших значений, которые в сумме дадут текущий порог. Таким образом, на каждом пороге, все предыдущие пороги потенциально считаются работать вверх к сумме цель W . По этой причине этот подход динамического программирования требует количества шагов, равного O ( nW), где n - количество типов монет.
Реализация
Ниже приводится реализация динамического программирования (с Python 3), которая использует матрицу для отслеживания оптимальных решений подзадач и возвращает минимальное количество монет или «Бесконечность», если нет возможности внести изменения с помощью монеты даны. Вторая матрица может использоваться для получения набора монет для оптимального решения.
def _get_change_making_matrix(set_of_coins, r: int):
m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
for i in range(1, r + 1):
m[0][i] = float('inf') # By default there is no way of making change
return m
def change_making(coins, n: int):
"""This function assumes that all coins are available infinitely.
n is the number to obtain with the fewest coins.
coins is a list or tuple with the available denominations.
"""
m = _get_change_making_matrix(coins, n)
for c in range(1, len(coins) + 1):
for r in range(1, n + 1):
# Just use the coin coins[c - 1].
if coins[c - 1] == r:
m[c][r] = 1
# coins[c - 1] cannot be included.
# Use the previous solution for making r,
# excluding coins[c - 1].
elif coins[c - 1] > r:
m[c][r] = m[c - 1][r]
# coins[c - 1] can be used.
# Decide which one of the following solutions is the best:
# 1. Using the previous solution for making r (without using coins[c - 1]).
# 2. Using the previous solution for making r - coins[c - 1] (without
# using coins[c - 1]) plus this 1 extra coin.
else:
m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
return m[-1][-1]
Динамическое программирование с вероятностным деревом свертки
Вероятностное дерево свертки также можно использовать как более эффективный подход к динамическому программированию. Дерево вероятностной свертки объединяет пары монет для получения всех сумм, которые могут быть созданы этой парой монет (при отсутствии ни одной монеты, только первой монеты, только второй монеты и наличия обеих монет), а затем последующее объединение пар из этих объединенных результатов таким же образом. Этот процесс повторяется до тех пор, пока два последних набора результатов не будут объединены в один, что приведет к сбалансированному двоичному дереву с W log (W) таких операций слияния. Кроме того, путем дискретизации достоинств монеты каждая из этих операций слияния может выполняться посредством свертки, что часто может быть выполнено более эффективно с помощью быстрого преобразования Фурье (БПФ). Таким образом, вероятностное дерево свертки может использоваться для достижения решения за субквадратичное количество шагов: каждая свертка может выполняться за n log (n) , а начальные (более многочисленные) операции слияния используют меньшее n , в то время как позже (менее многочисленные) операции требуют п о порядке W .
Метод динамического программирования на основе вероятностного дерева свертки также эффективно решает вероятностное обобщение проблемы внесения изменений, где неопределенность или нечеткость в целевой сумме W делает ее дискретным распределением, а не фиксированной величиной, где стоимость каждой монеты аналогичным образом разрешено быть нечетким (например, когда рассматривается обменный курс), и где разные монеты могут использоваться с определенной частотой.
Жадный метод
Для так называемых канонических монетных систем, таких как те, которые используются в США и многих других странах, жадный алгоритм выбора монет самого большого достоинства, не превышающего оставшуюся сумму, даст оптимальный результат. Однако это не относится к произвольным системам монет. Например, если номиналы монет были 1, 3 и 4, то для получения 6 жадный алгоритм выбрал бы три монеты (4,1,1), тогда как оптимальное решение - две монеты (3,3). Можно проверить, является ли система монет канонической (то есть всегда ли жадный алгоритм решает свою проблему внесения изменений оптимально) за полиномиальное время .
Связанные проблемы
« Проблема оптимального достоинства » - это проблема для людей, которые создают совершенно новые валюты. Он спрашивает, какой номинал следует выбрать для монет, чтобы минимизировать среднюю стоимость внесения сдачи, то есть среднее количество монет, необходимое для внесения сдачи. Версия этой задачи предполагала, что люди, вносящие сдачу, будут использовать минимальное количество монет (из доступных номиналов). Один из вариантов этой проблемы предполагает, что люди, вносящие изменения, будут использовать «жадный алгоритм» для внесения изменений, даже если для этого требуется больше, чем минимальное количество монет. Большинство текущих валют используют серии 1-2-5 , но для некоторых других наборов номиналов потребуется меньшее количество монет или меньшее среднее количество монет для внесения сдачи или и то, и другое.