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

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

20 Окт 2023 в 19:40
25 +1
0
Ответы
1

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

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

Для каждого типа монет j от 1 до 6 и для каждой суммы i от 1 до 46 будем пересчитывать значение dp[i] следующим образом: dp[i] += dp[i - j * номинал монеты].

После заполнения массива dp ответом на задачу будет значение dp[46]. Таким образом, ответ на задачу - 32 способа оплатить сумму 46 унций без сдачи.

16 Апр 2024 в 15:53
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир