Динамическое программирование, минимальное количество монет - PullRequest
Новая
       43

Динамическое программирование, минимальное количество монет

0 голосов
/ 06 ноября 2018

Я изучал алгоритмы и структуры данных с https://runestone.academy/runestone/static/pythonds/index.html,, и я подошел к части о динамическом программировании и классической проблеме минимального количества монет. Учитывая сумму, мы должны выяснить, каково минимальное количество монет, необходимое для превращения ее в монеты различных номиналов.

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

Код здесь: 

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))

и я не понимаю, зачем нам эта часть: 

         if numCoins < minCoins:
            minCoins = numCoins
   return minCoins

Я попытался заменить все 3 строки одним оператором 

   return numCoins

И, кажется, работает нормально, за исключением случаев, когда change == 0. Я не думаю, что способ, которым они написали это в книге, предназначен для «защиты» от ввода 0, поскольку это может быть обработано еще более тривиально.

Почему они написали так, как написали?

ps: я запускаю его на python3.5, если это имеет значение ...

ура

1 Ответ

0 голосов
/ 08 ноября 2018

Как объяснено в главе ,

Если сумма не совпадает, у нас есть несколько вариантов. Мы хотим получить минимум копейки плюс количество монет, необходимое для внесения изменений в исходную сумму за вычетом пенни, или никель плюс количество монет, необходимых для внесения изменений в исходную сумму, минус пять центов или десять центов плюс количество монет, необходимое для внесения изменений в исходную сумму, минус десять центов и т. д. Таким образом, количество монет, необходимых для внесения изменений в исходную сумму, можно рассчитать по следующей формуле: 

numCoins=min(1+numCoins(originalamount−1),
             1+numCoins(originalamount−5),
             1+numCoins(originalamount−10),
             1+numCoins(originalamount−25))

В приведенной ниже строке для цикла вычисляется каждый из параметров для numCoins. 

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

Следующие две строки в цикле отслеживают минимальное значение numCoins: 

if numCoins < minCoins:
        minCoins = numCoins

Чтобы упростить отслеживание, вы можете переписать функцию следующим образом: 

def recMC(coinValueList,change):
    if change in coinValueList:
        return 1
    else:
        return min([1 + recMC(coinValueList,change-c) for c in coinValueList if c < change])
...