Динамическое программирование - решение изменения Монеты

Эта статья очень актуальна: http: // ecommons. library.cornell.edu/handle/1813/6219

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

В общем случае, когда номиналы монет могут быть произвольными, проблема, которую вы представляете, называется Проблема рюкзака и известна принадлежать к NP-полному ( Pearson, D. 2004 ), поэтому не разрешимо за полиномиальное время, такое как динамическое программирование.

Возьмем патологический пример: x [2] = 51, x [1] = 50, x [0] = 1, X = 100. Затем требуется, чтобы алгоритм «рассмотрел» возможности внесения сдачи с помощью монеты. x [2], альтернативно внесение изменений, начиная с x [1]. Первый шаг, используемый с национальной монетой, иначе известный как Жадный алгоритм - , то есть , «использовать самую большую монету меньше, чем рабочая сумма», не будет работать с патологическими монетами. . Вместо этого такие алгоритмы испытывают комбинаторный взрыв, который квалифицирует их как NP-полные.

Для некоторых специальных схем номинала монет, таких как практически все те, что используются в действительности, и включая фиктивную систему X [i + 1] == 2 * X [i], существуют очень быстрые алгоритмы, даже O (1) в данном фиктивном случае для определения наилучшего результата. Эти алгоритмы используют свойства достоинств монет.

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

В качестве примера динамического программирования обычно приводят приложение для умножения нескольких матриц.В зависимости от размера матриц выбор оценивать A · B · C как любую из двух эквивалентных форм: (( A · B ) · C ) или ( A · ( B · C )) приводит к вычисления различных количеств умножений и сложений. То есть один метод более оптимален (быстрее), чем другой. Динамическое программирование - это мотив, который сводит в таблицу вычислительные затраты различных методов и выполняет фактические вычисления в соответствии с расписанием (или программой ), вычисляемым динамически во время выполнения.

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

Термин «динамическое программирование» можно сравнить с «линейным программированием», в котором «программа» также используется в значении «планировать».

Чтобы узнать больше о динамическом программировании, обратитесь к величайшей книге по алгоритмам. еще известный мне «Введение в алгоритмы» Кормена, Лейзерсона, Ривеста и Стейна. «Rivest» - это буква «R» в «RSA», а динамическое программирование - это всего лишь одна глава.

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

int memory[#(coins)]; //initialize it to be -1, which means hasn't been calculated
MakeChange(X, x[1..n this is the coins], i){
    if(memory[i]!=-1) return memory[i];
    for (int i = 1; i < n; i++)
    {
        if ( (X - x[i] ==0) || MakeChange(X - x[i], i) ){
            memory[i]=true;
            return true;
        }
    }
    return false;
}

Просто добавьте шаг мемоизации к рекурсивному решению, и динамический алгоритм выпадает прямо из него. Следующий пример на Python:

cache = {}
def makeChange(amount, coins):
    if (amount,coins) in cache:
        return cache[amount, coins]
    if amount == 0:
        ret = True
    elif not coins:
        ret = False
    elif amount < 0:
        ret = False 
    else:
        ret = makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])
    cache[amount, coins] = ret
    return ret

Конечно, вы могли бы использовать декоратор для автоматической мемоизации, что привело бы к более естественному коду:

def memoize(f):
    cache = {}
    def ret(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return ret
@memoize
def makeChange(amount, coins):
    if amount == 0:
        return True
    elif not coins:
        return False
    elif amount < 0:
        return False
    return makeChange(amount-coins[0], coins) or makeChange(amount, coins[1:])

Примечание: даже в версии без динамического программирования, которую вы выложили, были всевозможные ошибки в краевых случаях, поэтому приведенный выше makeChange немного длиннее вашего.