Максим берет кредит на подарки. Ему предодобрен кредит в размере m бурлей, значит он может взять любое целое количество бурлей от 0 до m включительно. У Максима есть список из n подарков. Он планирует идти по порядку вдоль списка и каждый раз, когда он видит подарок, на который у него хватает денег, он обязательно моментально его покупает. Помогите ему посчитать, какое максимальное количество денег у него может остаться после закупки подарков, если он возьмет оптимальный кредит.

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

Шаги решения:

1. Создать массив dp размером (m+1), где каждый элемент будет хранить максимальное количество денег, которое можно сохранить, если имеется кредит в размере i бурлей.
2. Инициализировать dp[0] равным m, так как по умолчанию у нас есть все деньги до m.
3. Пройти циклом по списку подарков.
4. Внутри этого цикла пройти циклом от m до cost[i], где cost[i] – стоимость текущего подарка.
5. Внутри вложенного цикла обновить значения dp[j] следующим образом:
– Если dp[j – cost[i]] > 0, то у нас есть достаточно денег для покупки подарка i. Поэтому мы можем использовать текущий кредит и оставить у себя только dp[j – cost[i]] денег, то есть dp[j] = dp[j – cost[i]].
– В противном случае, если dp[j – cost[i]] = 0, то у нас недостаточно денег для покупки подарка i. Поэтому в этом случае мы оставляем текущую сумму кредита без изменений, то есть dp[j] остается равным dp[j].
6. После завершения внутреннего цикла, проверить, было ли обновление значения dp[m]. Если значение dp[m] изменилось, значит мы нашли более оптимальный кредит, и его нужно сохранить.
7. Вернуть полученное максимальное количество денег, которое может остаться у Максима после закупки подарков.

Таким образом, данный алгоритм будет работать со сложностью O(n*m), где n – количество подарков, m – размер кредита.

Примечание: Во время решения предполагается, что стоимость каждого подарка целочисленная. Если стоимость подарков может быть дробной, то алгоритм требует некоторых модификаций.