Рекурсивный алгоритм размена монет

Question

Я пытаюсь unwind recursive функция в этом algorithm, Проблема смены монет: заданная сумма n и список array различных монет, какое наименьшее количество монет необходимо для внесения суммы изменения.

def rec_coin(target,coins):

    # Default to target value
    min_coins = target

    # Check to see if we have a single coin match (BASE CASE)
    if target in coins:
        return 1

    else:

        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:

            # Recursive Call (add a count coin and subtract from the target) 
            num_coins = 1 + rec_coin(target-i,coins)

            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:

                min_coins = num_coins

    return min_coins

# rec_coin(63,[1,5,10,25])
# 6

Это то, что я придумала после разрыва

1 + 63-1 coins + 62-1 + 61-1 and so on..

почему мы должны добавить 1? Каков был бы правильный способ раскручивания рекурсии?

Answer 1

Код, который вы представляете, очень неэффективен. Чтобы найти решение на сумму 63, представьте, что оно сначала вернется к целевому количеству с шагами наименьшей монеты (т.е. 1). Затем после большого количества возвратов и попыток с другими монетами, он, наконец, возвращается к внешнему уровню и пробует монету со значением 5. Теперь рекурсия запускается снова, как и раньше, добавляя монеты со значением 1. Но проблема в том, что это промежуточное значение (63-5) уже посещалось ранее (на 5 уровней после выбора монеты 1), и потребовалось много вызовов функции, чтобы получить результаты для этого значения 58. И все же алгоритм просто проигнорирует это и выполнит все эта работа снова.

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

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

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

Вот код для этого:

def rec_coin(target, coins):
    visited = set() # Amounts that we have already achieved with a minimal number of coins
    amounts = [0] # The latest series of amounts all using an equal number of coins
    for min_coins in range(1, target+1):
        next_amounts = []
        for amount in amounts:
            for coin in coins:
                added = amount + coin
                if added == target: 
                    return min_coins
                if not added in visited:
                    visited.add(added)
                    next_amounts.append(added)
        amounts = next_amounts

print (rec_coin(63,[1,5,10,25]))