Разделяй и властвуй рекурсивное решение для внесения изменений - PullRequest
Новая
       34

Разделяй и властвуй рекурсивное решение для внесения изменений

1 голос
/ 09 мая 2019

Я пытаюсь реализовать программу «разделяй и властвуй», чтобы при получении набора монет c = {c0, c1, ..., cn} и суммы A он находил, сколько разных способов A можно заплатить, кака также сколько раз функция повторялась.

Я думаю сделать что-то вроде этого: 

callsMade = 0
coins = [1,5,10,25]

def makeChange(A, c):
    global callsMade
    callsMade += 1
    if(A == 0):
        return 1
    if(A < 0):
        return 0
    combos = 0
    for i in range(len(coins)):
        combos += makeChange(A - coins[i], i)
    return combos

Где A - сумма, которую передают, а c = len (монеты)-1.Однако этот фрагмент кода не ведет себя так, как я ожидаю.Мой мыслительный процесс состоит в том, чтобы перебрать массив монет, вычитая текущую сумму из монеты в этой позиции массива, и рекурсивно вызывать функцию makeChange с меньшим количеством и следующей монетой в массиве, а затем увеличивать глобальные callMade на 1 каждыйвремя.

При использовании набора монет = [1,5,10,25] и суммы А = 200 количество комбинаций должно составлять 1463, при этом будет сделано около 1500 вызовов.

Ответы [ 2 ]

1 голос
/ 09 мая 2019

Отношение повторения выглядит примерно так (для краткости я убрал счетчик вызовов): 

def makeChange(A, coins, k=0):
    if A == 0: return 1
    if A <  0: return 0
    return sum(makeChange(A - coins[i], coins, i) for i in range(k, len(coins)))

Т.е., вы не учитываете монеты, которые меньше тех, которые вы уже взяли, в противном случае вы получите комбинацию, такую ​​как [1, 1, 5] и [1, 5, 1] и так далее. С этим я получаю 1463 комбинации для makeChange(200, (1,5,10,25)) с общим количеством звонков 111491 - немного больше, чем вы ожидали.

Обратите внимание, что эта функция будет рассчитывать множество комбинаций более одного раза. Например, вы можете достичь A=194 на [1,5] или [1,1,1,1,1,1] и т. Д., Но результат для makeChange(194, coins, k=1) одинаков для обоих способов. Вы можете использовать functools.lru_cache для автоматического запоминания этих значений. Таким образом, вы получите тот же результат после 801 звонка. 

@functools.lru_cache(None)
def makeChange(A, coins, k=0):
    # same as above

(Для запоминания вы должны включить coins в качестве параметра (как tuple, а не list, чтобы его можно было хэшировать), иначе он будет повторно использовать результат для другого набора монет .)

0 голосов
/ 09 мая 2019

Основная идея верна, но вам нужно рассмотреть некоторые проблемы с рекурсией и то, что вы хотите считать правильным ответом.

Если вы начнете просто, вы можете спросить, сколько комбинаций [1,5,10,25] должно равняться 6:

Должно быть 3:
[1, 1, 1, 1, 1, 1], [5, 1], [1, 5]?
или 2:
[1, 1, 1, 1, 1, 1], [1, 5]?

Два имеет для меня самый смысл.Для этого вам нужно передать подмножество вашего массива монет обратно в рекурсию, поэтому, когда вы находитесь в цикле for, смотрящем на 5, вы больше не учитываете [5, 1] - возможно, вы уже подсчитали [1, 5] на данный момент,Вместо передачи неиспользуемого параметра c, передайте список coins.Затем управляйте этим списком в цикле.Здесь я добавил дополнительный параметр cur, чтобы собирать комбинации только для проверки работы.Вам это не нужно, если вы просто хотите считать. 

def makeChange(A, coins, cur = None):
    ''' This will also collect the combinations to check the work'''
    if cur is None:
        cur = []
    global callsMade
    callsMade += 1
    if(A == 0):
        print(cur)
        return 1
    if(A < 0):
        return 0
    combos = 0
    for i, coin in enumerate(coins):
        if coin > A: # don't bother if coin is too big
            continue
        # pass a subset of the list into recursion
        combos += makeChange(A - coin, coins[i:], cur + [coin])
    return combos

coinset = [1,5,10,25]
A = 10
makeChange(A, coinset)

Результат: 

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 5]
[5, 5]
[10]
Out[456]:
4

Установка A на 200 показывает 1463 комбинаций.

...