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

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

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

python-3.x coin-change
person Akash Dubey    schedule 10.07.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Пусть 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.

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

person Aimery    schedule 10.07.2019
comment
Спасибо за помощь :) - person Akash Dubey; 10.07.2019