Question

у Амира есть карточки с числами 10 и 15 (карточек достаточно много). Сколькими способами он может выбрать несколько из них чтобы сумма чисел на карточках была равна 300

Answer 1

Мне кажется 10+15=25 и потом 25*12=300

Answer 2

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

Пусть dp[i][j] представляет количество способов получить сумму j, используя первые i карточек. Тогда для каждой карточки, у нас есть два варианта: либо мы используем её, либо нет.

1. Если мы используем i-ю карточку, то у нас останется (j - числовое значение на i-й карточке) для дополнения суммы.
2. Если мы не используем i-ю карточку, то сумма останется без изменений.

Таким образом, мы можем выразить dp[i][j] следующим образом:

dp[i][j] = dp[i-1][j] + dp[i-1][j - числовое значение на i-й карточке]

Теперь, давайте рассмотрим начальные условия:

• dp[0][0] = 1 (существует один способ получить сумму 0 без использования карточек)
• dp[0][j] = 0 (если у нас нет карточек, то невозможно получить любую положительную сумму)

Теперь заполним таблицу dp используя рекуррентное соотношение и начальные условия:

plaintextCopy code
dp[i][j] = dp[i-1][j] + dp[i-1][j - числовое значение на i-й карточке]

Следует заметить, что у нас есть ограничение в сумме (300), поэтому нам интересны только значения dp[i][j], где j <= 300.

Итак, давайте заполним таблицу dp и найдем количество способов получить сумму 300:

plaintextCopy code
Число карточек (i) / Сумма (j)  : 0   1   2   3   ...   298  299  300
dp[0] (0 карточек)             : 0   0   0   0   ...   0    0    0
dp[1] (карточка 10)            : 0   0   0   0   ...   0    0    0
dp[2] (карточка 15)            : 0   0   0   0   ...   0    0    0

Таким образом, Амир может выбрать несколько карточек таким образом, чтобы сумма чисел на них была равна 300, всего 0 способов.