Комбинаторная задача. Имеется x монет... Имеется X монет достоинствами N1, N2, N3, ..Nm рублей. Мальчик хочет узнать K - количество способов выбрать из этих монет Y рублей. Монеты одинакового достоинства считаются одинаковыми.

23 Авг 2019 в 19:42
154 +1
0
Ответы
1

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

Представим Y рублей в виде суммы денежных единиц (N1, N2, N3, ..Nm) как сумму Yi, где i от 0 до Y. Таким образом, количество способов выбрать Y рублей будет равно сумме количеств способов выбрать Y-N1 рублей, Y-N2 рублей, ..., Y-Nm рублей.

Создадим массив dp длиной Y+1, в котором будем хранить количество способов выбрать каждую сумму от 0 до Y. Инициализируем dp[0] = 1, так как один способ выбрать 0 рублей - не выбирать ни одной монеты.

Далее заполним массив dp по следующему алгоритму:

for (int i = 0; i < m; i++) {
for (int j = coins[i]; j <= Y; j++) {
dp[j] += dp[j - coins[i]];
}
}

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

Таким образом, ответ на задачу будет равен dp[Y].

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