Комбинаторная задача. Имеется x монет... Имеется X монет достоинствами N1, N2, N3, ..Nm рублей. Мальчик хочет узнать K - количество способов выбрать из этих монет Y рублей. Монеты одинакового достоинства считаются одинаковыми.
Комбинаторная задача. Имеется x монет... Имеется X монет достоинствами N1, N2, N3, ..Nm рублей. Мальчик хочет узнать K - количество способов выбрать из этих монет Y рублей. Монеты одинакового достоинства считаются одинаковыми.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения данной комбинаторной задачи можно воспользоваться динамическим программированием.
Представим 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].