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