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

Я пытаюсь реализовать программу «разделяй и властвуй», которая при наличии набора монет 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(coins)-1. Однако этот фрагмент кода ведет себя не так, как я ожидал. Мой мыслительный процесс состоит в том, чтобы перебрать массив монет, вычитая текущую сумму на монету в этой позиции массива и рекурсивно вызывать функцию makeChange с меньшей суммой и следующей монетой в массиве, а затем увеличивать глобальные вызовы, сделанные на 1 каждый время.

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


python divide-and-conquer
person pweave    schedule 09.05.2019    source источник
comment
Я не понимаю, что вы спрашиваете. В середине вы говорите, что это не работает, как ожидалось. Что просходит? В чем вы хотите помочь? (Разве вам также не нужно проверять, что coins[I] меньше A?   -  person doctorlove    schedule 09.05.2019
comment
Какой смысл переходить на c? Он не используется.   -  person MisterMiyagi    schedule 09.05.2019
comment
В настоящее время он дает мне неправильное количество комбинаций, и я даже не могу вызвать его со значением более 50, потому что программа замедляется. Итак, во-первых, я хотел бы помочь понять, правилен ли мой мыслительный процесс в отношении проблемы «разделяй и властвуй», а затем, надеюсь, найти свою ошибку в этом фрагменте.   -  person pweave    schedule 09.05.2019
comment
@MisterMiyagi правильно. моя мысль заключалась в том, чтобы использовать его для перебора списка монет и увеличения его перед выполнением другого рекурсивного вызова. Я смущен тем, как мне собрать все это вместе, чтобы работать должным образом.   -  person pweave    schedule 09.05.2019

Ответы (2)


arrow_upward
1
arrow_downward

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

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, чтобы его можно было хешировать), иначе он будет повторно использовать результат для другого набора монет.)

person tobias_k    schedule 09.05.2019

arrow_upward
0
arrow_downward

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

Если вы начнете просто, вы можете спросить, сколько комбинаций [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 комбинаций.

person Mark    schedule 09.05.2019
comment
Спасибо за это описание, передача подмножества имеет смысл и сокращает обычные рекурсивные вызовы примерно вдвое. Но эта реализация по-прежнему выполняет 78 903 рекурсивных вызова, что наводит меня на мысль, что помимо полной мемоизации существует еще более эффективный способ. Звонки должны быть около 1570. - person pweave; 09.05.2019
comment
@pweave комбинаций намного больше, чем 1570. Чтобы получать меньше вызовов, вы можете запомнить функцию. На самом деле вы можете уменьшить количество звонков на 764, используя lru_cache или написать свое. - person Mark; 09.05.2019