Решите задачу по алгебре До 268
268
года до нашей эры в Древнем Риме было шесть основных монет:

Унция (монета номиналом 1
1
унция)
Секстанс (монета номиналом 2
2
унции)
Квадранс (монета номиналом 3
3
унции)
Триенс (монета номиналом 4
4
унции)
Семис (монета номиналом 6
6
унций)
Асс (монета номиналом 12
12
унций)
Однажды римлянин Луций взял с собой по две монеты каждого из шести номиналов (всего —
—
12
12
монет) и отправился на рынок. Сколькими способами он сможет без сдачи оплатить своими монетами покупку стоимостью 47
47
унций? Монеты одного номинала считайте одинаковыми.

Предыдущий
вопрос Следующий
вопрос

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

Создадим массив dp размером 48 (сумма покупки Луция плюс один) и заполним его нулями. dp[0] установим равным 1 (так как способ оплаты нулевой суммы - это не платить вообще).

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

После завершения всех итераций значение dp[47] будет содержать количество способов оплатить покупку на 47 унций без сдачи.

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

После запуска данной программы получим ответ: 34001 способ оплатить покупку на 47 унций без сдачи монетами Луция.