Рекурсия: внести изменения с наименьшими монетами

-1

Я изучаю структуру данных и алгоритм в python. Вот классическая проблема рекурсии, включающая изменение с наименьшими монетами. Вот коды. То, что я не понимаю, это строка 2. зачем нам нужно minCoins = change? что означает линия 8-9? может ли кто-нибудь объяснить это? большое спасибо за помощь!Рекурсия: внести изменения с наименьшими монетами

def recMC(coinValueList,change): 
    minCoins = change 
    if change in coinValueList: 
    return 1 
    else: 
     for i in [c for c in coinValueList if c <= change]: 
     numCoins = 1 + recMC(coinValueList,change-i) 
     if numCoins < minCoins: 
      minCoins = numCoins 
    return minCoins 

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

источник

2016-10-17 zesla

Какое необходимо разрешение? Количество монет или словарь с суммой каждого типа монет. Кроме того, этот код дает мне бесконечный цикл. Я не могу объяснить работу кода, который не работает. Вы хотите, чтобы я написал новое решение и объяснил это? –

Это не бесконечный цикл, а просто суперэффективный алгоритм –

minCoins = change: minCoins инициализируется со значением change который представляет собой максимальное значение, которое может возвращать recMC как минимальное значение монеты равно 1, при условии, целые значения монет.

if change in coinValueList: return 1: базовый вариант 1 - если какая-то монета имеет значение, что в change нам просто нужно, чтобы захватить этот 1 монету, тем самым возвращая 1

for i in [c for c in coinValueList if c <= change]:: Функция затем перебирает все возможные значения 1 одна монета

numCoins = 1 + recMC(coinValueList,change-i): вычесть значение монеты i из change, добавьте 1 монету количество монет, необходимых, который рекурсивно вычисленных для остаточному изменения (change-i). Это работает с индуктивно из базовых случаев

if numCoins < minCoins: minCoins = numCoins внутри этого цикла эффективно присваивает наименьшее количество монет, возможных для minCoins

Если change все еще имели инициализированный значение minCoins (не подразумевая никакой ценности c в coinValueList удовлетворяет c <= change), это означает, что количество необходимых монет также равно change, то есть change 1 единица монет. Это базовый случай 2, основанный на предварительном условии, что монета со значением 1 всегда доступна.

источник

2016-10-17 14:34:45

Большое спасибо за подробное объяснение – zesla

Рекурсия: внести изменения с наименьшими монетами

ответ

Смежные вопросы