Как найти перекрывающуюся подзадачу в задаче изменения монеты этого рекурсивного кода, я не могу ее найти - PullRequest
Новая
       31

Как найти перекрывающуюся подзадачу в задаче изменения монеты этого рекурсивного кода, я не могу ее найти

0 голосов
/ 10 июля 2019

Вы работаете у кассы на веселой ярмарке, и у вас есть различные типы монет, доступные вам в бесконечном количестве.Стоимость каждой монеты уже указана.Можете ли вы определить количество способов внесения изменений для определенного количества единиц, используя монеты данного типа? 

counter = 0
def helper(n,c):
    global counter
    if n == 0:
        counter += 1 
        return 
    if len(c) == 0:
        return

    else:
        if n >= c[0]:
            helper(n - c[0], c)
        helper(n,c[1:])

def getWays(n, c):
    helper(n,c)
    print(counter)
    return counter ```

#the helper function takes n and c 
#where 
#n is amount whose change is to be made 
#c is a list of available coins

1 Ответ

0 голосов
/ 10 июля 2019

Пусть n - количество денежных единиц, которые будут возвращены в качестве изменения.Вы хотите найти N(n), количество возможных способов возврата изменений.

Одним из простых решений было бы сначала выбрать «первую» монету, которую вы даете (скажем, она имеет значение c), затемобратите внимание, что N(n) является суммой всех значений N(n-c) для всех возможных c.Поскольку это кажется рекурсивной проблемой, нам нужны некоторые базовые случаи.Как правило, у нас будет N(1) = 1 (одна монета достоинством один).

Давайте сделаем пример: 3 можно вернуть как «1 плюс 1 плюс 1» или как «2 плюс 1» (при условии монетценностью один и два существуют).Следовательно, N(3)=2.

Однако, если мы применим предыдущий алгоритм, он вычислит N(3), чтобы быть 3. 

+------------+-------------+------------+
| First coin | Second coin | Third coin |
+------------+-------------+------------+
|      2     |      1      |            |
+------------+-------------+------------+
|            |      2      |            |
|      1     +-------------+------------+
|            |      1      |      1     |
+------------+-------------+------------+

Действительно, обратите внимание, что возвращая 3 единицы как "2плюс 1 "или как" 1 плюс 2 "считается нашим алгоритмом как два разных решения, в то время как они одинаковы.

Поэтому нам необходимо применить дополнительное ограничение, чтобы избежать таких дубликатов.Одним из возможных решений является заказ монет (например, путем уменьшения стоимости).Затем мы накладываем следующее ограничение: если на данном шаге мы вернули монету достоинством c0, то на следующем шаге мы можем вернуть только монеты достоинством c0 или меньше.

Это приводит кследующее индукционное отношение (отмечая c0 значение монеты, возвращенной на последнем шаге): N(n) - это сумма всех значений N(n-c) для всех возможных значений c, меньших или равных c0.

Удачного кодирования:)

...