Имеется X монет достоинствами N1, N2, N3, ... , Nm рублей. Мальчик хочет узнать K - количество способов выбрать из этих монет Y рублей. Монеты одинакового достоинства считаются одинаковыми.
Имеется X монет достоинствами N1, N2, N3, ... , Nm рублей. Мальчик хочет узнать K - количество способов выбрать из этих монет Y рублей. Монеты одинакового достоинства считаются одинаковыми.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно воспользоваться динамическим программированием.
Создадим массив dp[], где dp[i] будет содержать количество способов выбрать сумму i рублей с использованием заданных монет.
Изначально заполним массив dp[] нулями, кроме dp[0], который равен 1 (так как один способ выбрать 0 рублей - не выбирать ни одной монеты).
Далее пройдемся по всем монетам. Для каждой монеты пройдемся по всем рублям от этой монеты до требуемой суммы Y и прибавим к dp[j] количество способов выбрать сумму j-этой монетой.
После обработки всех монет в dp[Y] будет содержаться количество способов выбрать сумму Y рублей с использованием заданных монет. Количество способов Y рублей равно dp[Y].
Таким образом, мы можем найти количество способов выбрать Y рублей из данных монет методом динамического программирования.