Проблема внесения изменений

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

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

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

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

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

f(W)=\sum _{j=1}^{n}x_{j}

при условии

\sum _{j=1}^{n}w_{j}x_{j}=W.

Невалютные примеры

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

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

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

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

Классическая стратегия динамического программирования работает вверх, находя комбинации всех меньших значений, которые в сумме дают текущий порог. ^[3] что все предыдущие пороги работают вверх до целевой суммы 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.
    if coins are only to be used once, change m[c][r - coin] to m[c - 1][r - coin].
    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, coin in enumerate(coins, 1):
        for r in range(1, n + 1):
            # Just use the coin
            if coin == r:
                m[c][r] = 1
            # coin cannot be included.
            # Use the previous solution for making r,
            # excluding coin
            elif coin > r:
                m[c][r] = m[c - 1][r]
            # coin can be used.
            # Decide which one of the following solutions is the best:
            # 1. Using the previous solution for making r (without using coin).
            # 2. Using the previous solution for making r - coin (without
            #      using coin) plus this 1 extra coin.
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coin])
    return m[-1][-1]

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

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

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

Жадный метод

Для многих реальных систем монет, таких как те, которые используются в США и многих других странах, жадный алгоритм выбора монеты наибольшего номинала, который не превышает оставшуюся сумму, которую необходимо сделать, даст оптимальный результат. Однако это не относится к произвольным монетным системам или даже к некоторым системам реального мира. Например, если мы рассмотрим старые (ныне изъятые) индийские монеты номиналом 5, 10, 20 и 25 пайсов, то для получения 40 пайсов жадный алгоритм выберет три монеты (25, 10, 5), тогда как оптимальное решение две монеты (20, 20). Другой пример — попытка заработать 40 центов США без пятицентовых монет (номиналом 25, 10, 1) с аналогичным результатом — жадный выбирает семь монет (25, 10 и 5 × 1), но оптимально — четыре (4 × 10). Система монет называется «канонической», если жадный алгоритм всегда оптимально решает задачу внесения изменений. Проверить, является ли система монет канонической, можно за полиномиальное время . ^[5]

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

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

См. также

Ссылки

^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Стоун, Клиффорд (2009). Введение в алгоритмы . С Прессой. Выпуск 16-1, с. 446.
^ Гудрич, Майкл Т.; Тамассия, Роберто (2015). Разработка алгоритмов и их применение . Уайли. Упражнение А-12.1, с. 349.
^ Райт, JW (1975). «Проблема внесения изменений» . Журнал Ассоциации вычислительной техники . 22 (1): 125–128. дои : 10.1145/321864.321874 . S2CID 22568052 .
^ Серанг, О. (2012). «Дерево вероятностной свертки: эффективный точный байесовский вывод для более быстрого вывода белков с помощью ЖХ-МС/МС» . ПЛОС ОДИН . 9 (3): е91507. Бибкод : 2014PLoSO...991507S . дои : 10.1371/journal.pone.0091507 . ПМЦ 3953406 . ПМИД 24626234 .
^ Пирсон, Дэвид (2005). «Алгоритм с полиномиальным временем для задачи внесения изменений». Письма об исследованиях операций . 33 (3): 231–234. дои : 10.1016/j.orl.2004.06.001 . hdl : 1813/6219 . МР 2108270 .
^ Дж. Шалит (2003). «Что нужно этой стране, так это монета номиналом 18 центов» (PDF) . Математический интеллект . 25 (2): 20–23. дои : 10.1007/BF02984830 . S2CID 123286384 .

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

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

[1] Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Стоун, Клиффорд (2009). Введение в алгоритмы . С Прессой. Выпуск 16-1, с. 446.

[2] Гудрич, Майкл Т.; Тамассия, Роберто (2015). Разработка алгоритмов и их применение . Уайли. Упражнение А-12.1, с. 349.

[3] Райт, JW (1975). «Проблема внесения изменений» . Журнал Ассоциации вычислительной техники . 22 (1): 125–128. дои : 10.1145/321864.321874 . S2CID 22568052 .

[Serang-4] Серанг, О. (2012). «Дерево вероятностной свертки: эффективный точный байесовский вывод для более быстрого вывода белков с помощью ЖХ-МС/МС» . ПЛОС ОДИН . 9 (3): е91507. Бибкод : 2014PLoSO...991507S . дои : 10.1371/journal.pone.0091507 . ПМЦ 3953406 . ПМИД 24626234 .

[5] Пирсон, Дэвид (2005). «Алгоритм с полиномиальным временем для задачи внесения изменений». Письма об исследованиях операций . 33 (3): 231–234. дои : 10.1016/j.orl.2004.06.001 . hdl : 1813/6219 . МР 2108270 .

[6] Дж. Шалит (2003). «Что нужно этой стране, так это монета номиналом 18 центов» (PDF) . Математический интеллект . 25 (2): 20–23. дои : 10.1007/BF02984830 . S2CID 123286384 .

[1]

[2]

[3]

[4]

[5]

[6]