Question

У старого пирата Билли есть монеты достоинством 10 тугриков, 20 тугриков и 30 тугриков, по десять штук каждого вида. Сколькими способами он может набрать из них сумму в 60 тугриков?

Answer 1

Ответ:

6

У нас было такое заданиеи у меня Оценка5 за него

Answer 2

Можно использовать метод динамического программирования для решения этой задачи.

Пусть dp[i] - количество способов набрать сумму i тугриков с использованием только монет достоинством 10, 20 и 30 тугриков.

Изначально все значения dp[i] равны 0, кроме dp[0] = 1 (так как нулевую сумму можно набрать одним способом - не выбирая ни одной монеты).

Затем для каждого типа монеты (10, 20 и 30) и для каждого количества монет этого типа (от 0 до 10) мы обновляем соответствующие значения dp[i]. То есть, если мы рассматриваем монеты достоинством j и у нас уже есть k монет этого достоинства, то мы добавляем количество способов, которые можно получить, используя эти монеты: dp[i] += dp[i - j*k].

В конце, ответом на задачу будет значение dp[60].

Вот код на Python, который реализует этот алгоритм:

cssCopy code
dp = [0] * 61
dp[0] = 1

for coin in [10, 20, 30]:
    for count in range(1, 11):
        for i in range(60, coin*count-1, -1):
            dp[i] += dp[i - coin*count]

print(dp[60])

Ответ: Билли может набрать 46 способами 60 тугриков из монет достоинством 10, 20 и 30 тугриков, по 10 штук каждого вида.