Нужно отображать монеты, используемые в функции makeChange?

Question

Я создаю функцию makeChange, используя рекурсивный вызов useIt или loseIt. Я смог определить наименьшее количество монет, необходимых для создания суммы; однако я не уверен, как отображать фактические используемые монеты.

def change(amount,coins): 
    '''takes the amount and makes it out of the given coins in the list in order to return the least number of coins that's needed to create the value and the coins used''' 
    if amount==0: 
     return 0 
    if coins== [] or amount < 0: 
     return float('inf') 
    else: 
     useIt= change(amount,coins[1:]) 
     loseIt= change(amount-coins[0],coins) + 1 

    return min(useIt,loseIt) 

Answer 1

Прежде всего семантика ваших имен для стратегии use-it-or-lose-it обратная. «Использовать это» означает, что данный элемент учитывается в вашем общем результате. «Lose it» означает, что вы просто перечитываете оставшуюся часть списка без учета текущего элемента. Поэтому я бы начал с переключения этих имен. А также вы должны быть отбрасывая текущий элемент в рекурсивном вызове, используете ли вы его:

loseIt = change(amount,coins[1:]) 
useIt = change(amount-coins[0], coins[1:]) + 1 

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

>>> min([2, [1,2]], [3, [0,2]]) 
[2, [1, 2]] 

Вы также можете комбинировать любое количество элементов в этой форме с выражением, как это:

>>> [x+y for x,y in zip([2, [1,2]], [3, [0,2]])] 
[5, [1, 2, 0, 2]] 

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

[useIt[0] + 1, useIt[1] + [coins[0]]] 

Обратите внимание, что первый элемент представляет собой целое число, а второй список.

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

def change(amount,coins): 
    if amount==0: 
     return [0, []] 
    if coins== [] or amount < 0: 
     return [float('inf'), []] 
    else: 
     loseIt = change(amount, coins[1:]) 
     useIt = change(amount - coins[0], coins[1:]) 
    # Here we add the current stuff indicating that we "use" it 
    useIt = [useIt[0] + 1, useIt[1] + [coins[0]]] 
    return min(useIt,loseIt) 

Answer 2

Вы хотите что-то вроде:

def change(amount, coins): 
    ''' 
    >>> change(10, [1, 5, 25]) 
    [5, 5] 
    ''' 
    if not coins or amount <= 0: 
     return [] 
    else: 
     return min((change(amount - coin, coins) + [coin] 
        for coin in coins if amount >= coin), key=len) 

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