Question

У Амира есть карточки с числами 10 и 15 Сколькими способами он может выбрать несколько из них чтобы сумма чисел была равна 360

Answer 1

15-2раз

10-33раз

... по столько надо взять

Answer 2

Поскольку число 360 является достаточно большим, чтобы перебрать все возможные комбинации, мы можем использовать динамическое программирование для решения этой задачи.

Давайте создадим таблицу dp, где dp[i][j] будет означать, сколько способов можно выбрать несколько чисел из первых i карточек, чтобы их сумма была равна j.

Мы можем заполнить эту таблицу, используя следующую рекуррентную формулу:

dp[i][j] = dp[i-1][j] + dp[i-1][j-card[i]], если j >= card[i] dp[i][j] = dp[i-1][j], если j < card[i]

Где card[i] - значение i-ой карточки.

Смысл формулы в том, что чтобы получить dp[i][j], мы можем либо исключить i-ую карточку из рассмотрения и оставить текущую сумму j, либо включить i-ую карточку в рассмотрение и уменьшить текущую сумму на её значение (j-card[i]).

Таким образом, чтобы получить ответ на исходную задачу, нам нужно найти значение dp[n][360], где n - количество карточек.

Пример реализации на Python:

pythonCopy code
cards = [10, 15]
target_sum = 360

n = len(cards)
dp = [[0]*(target_sum+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(1, n+1):
    for j in range(target_sum+1):
        dp[i][j] = dp[i-1][j]
        if j >= cards[i-1]:
            dp[i][j] += dp[i-1][j-cards[i-1]]

print(dp[n][target_sum])

В данном случае ответом будет 6. То есть, существует шесть способов выбрать несколько чисел из карточек [10, 15], чтобы их сумма была равна 360.