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

Question

Я пытаюсь решить проблему смены монет. Вы получаете сумму денег (например, 55 центов) и должны отдать как можно меньше монет.

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

Сначала я попытался сделать это с фиксированными монетами, которые жестко закодированы, и это прекрасно работало

money = 55

def findMinCoins(money):
    nq = int(money/25)
    nd = int(money/10)
    nc = int(money/1)
    smallest = nq + nd + nc
    for q in range(nq+1):
        for d in range(nd+1):
            for c in range(nc+1):
                if q*25 + d*10 + c == money:
                    if q + d + c < smallest:
                        smallest = q + d + c
                        print(q, d, c)
    return smallest

После этого я попытался сделать это с монетамимассив, такой как coins = [25, 10, 1], и вот мой вопрос.

coins = [25, 10, 1]

def findMinCoins(money, coins):
    n_coins = [(int(money/coin) for coin in coins)]
    smallest = sum(n_coins)

Я не знаю, как мне делать циклы for с массивами. Может ли кто-нибудь помочь мне найти решение?

Answer 1

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

def findMinCoins(money, coins):
    if money < 0:
        return float('inf')
    return money and min(findMinCoins(money - coin, coins) for coin in coins) + 1

, поэтому:

findMinCoins(55, [25, 10, 1])

возвращает:

4

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

def findMinCoins(money, coins, cache={}):
    key = money, tuple(coins)
    if key in cache:
        return cache[key]
    if money < 0:
        number = float('inf')
    else:
        number = money and min(findMinCoins(money - coin, coins) for coin in coins) + 1
    cache[key] = number
    return number

Answer 2

Возможно, существует более питонский способ сделать это, но общий рекурсивный подход заключается в следующем:

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

def findMinCoins(money, coins):
    if money <= 0:
       return 0
    results = []
    for c in coins:
        if money >= c:
           results.append(1 + findMinCoins(money-c, coins))
    results.sort()
    return results[0] #return the smallest result

. Теперь единственная проблема, связанная с вышеизложенным, заключается в том, что он ОЧЕНЬ МЕДЛЕН, поскольку он будет выполнять множество избыточных вызовов для значений, которые были ранее вычислены. Поэтому мы исправим это, чтобы иметь таблицу поиска для каждого конечного результата и также проходить рекурсивно.

def findMinCoins(money, coins, lookup):
    if money <= 0:
       return 0
    if money in lookup:
       return lookup[money]
    results = []
    for c in coins:
        if money >= c:
           results.append(1 + findMinCoins(money-c, coins, lookup))
    results.sort()
    best = results[0]
    lookup[money] = best
    return best

Тестирование некоторых примеров:

>>> findMinCoins(95,[25,10,5,1], {})
5
>>> findMinCoins(4,[25,10,5,1], {})
4
>>> findMinCoins(44,[25,10,5,1], {})
7

Answer 3

Буквально переписав свои for петли:

>>> money=55
>>> lst=[(q+d+c, [q,d,c]) for q in range(int(money/25)+1) for d in range(int(money/10)+1) for c in range(int(money/1)+1) if q*25 + d*10 + c == money]
>>> lst
[(55, [0, 0, 55]), (46, [0, 1, 45]), (37, [0, 2, 35]), (28, [0, 3, 25]), (19, [0, 4, 15]), (10, [0, 5, 5]), (31, [1, 0, 30]), (22, [1, 1, 20]), (13, [1, 2, 10]), (4, [1, 3, 0]), (7, [2, 0, 5])]

Затем, чтобы найти наилучшее соответствие:

>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(4, [1, 3, 0])]

------------- РЕДАКТИРОВАТЬ

Чтобы обобщить решение:

>>> import itertools
>>> money=55
>>> coins=[25,10,1]
>>> lst=[(len(el), el) for num in range(1, money//min(coins)+1) for el in itertools.combinations_with_replacement(coins, num) if sum(el) == money]
>>> lst
[(4, (25, 10, 10, 10)), (7, (25, 25, 1, 1, 1, 1, 1)), (10, (10, 10, 10, 10, 10, 1, 1, 1, 1, 1)), (13, (25, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (19, (10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (22, (25, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (28, (10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (31, (25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (37, (10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (46, (10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (55, (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1))]
>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(4, (25, 10, 10, 10))]

Вышеприведенное является очень общим, и для вашей проблемы, особенно если у вас есть 1 cent среди ваших монет - выВозможно, вы захотите значительно уменьшить количество вычислений, заменив ограничение на потенциальное количество монет с money//min(coins)+1 на любое другое положительное целое число.

Например:

>>> coins=[1,2,5,25,50]
>>> money=100
>>> lst=[(len(el), el) for num in range(1, 5) for el in itertools.combinations_with_replacement(coins, num) if sum(el) == money]
>>> lst
[(2, (50, 50)), (3, (25, 25, 50)), (4, (25, 25, 25, 25))]
>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(2, (50, 50))]