Неограниченный рюкзак и DP для размена монет
Используйте элементы любое число раз
«Неограниченный рюкзак и DP для размена монет» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Неограниченное количество предметов
В неограниченном рюкзаке каждый предмет можно брать сколько угодно раз. Представьте монеты в торговом автомате, а не фиксированную стопку предметов.
Одно небольшое изменение
По сравнению с рюкзаком 0/1 меняется только направление цикла. Для неограниченного количества предметов вместимость перебирается в прямом порядке, от меньшего значения к большему.
Повторное использование в прямом порядке — это главное
При движении вперёд dp[w - coin] может уже учитывать этот же предмет. Такое намеренное повторное использование и позволяет брать его снова.
Знакомство с задачей о размене монет
Классическая задача о размене монет просит найти минимальное количество монет, составляющих заданную сумму. Это неограниченное DP с минимумом вместо максимума.
Определите состояние
Пусть dp[a] — минимальное количество монет, необходимое для получения суммы a. Начните с dp[0] = 0, поскольку для нулевой суммы монеты не нужны.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Используйте бесконечность для недостижимых сумм
Недостижимые суммы изначально получают значение бесконечность. Если в конце значение суммы остаётся бесконечным, её невозможно получить никакой комбинацией монет.
Переход
Для каждой монеты попробуйте улучшить все суммы, которых она может достичь. Используйте на одну монету больше, чем требуется для меньшей оставшейся суммы.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Почему нужен прямой порядок
Перебор сумм по возрастанию позволяет dp[a - coin] уже учитывать эту монету. Так одна монета может участвовать многократно.
Вместо этого считайте способы
Замените min+1 суммированием, чтобы посчитать количество способов получить каждую сумму. Внешний цикл по монетам не позволяет дважды считать разные порядки.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Прочитайте результат
Ответ находится в dp[amount]. В варианте с минимумом бесконечное значение означает, что целевую сумму невозможно получить.
0/1 и неограниченный рюкзак
Запомните единственное переключение: перебор вместимости назад означает, что каждый предмет используется один раз, а перебор вперёд — неограниченное количество раз. Таблица та же, меняется только направление прохода.
Быстрая проверка
Проверьте, что делает рюкзак неограниченным.
Итоги
Вы изменили направление цикла на прямое для неограниченного повторного использования и построили задачу о размене монет: с минимумом для поиска наименьшего количества монет или с суммой для подсчёта общего числа способов. 💰
Часто задаваемые вопросы
Урок «Неограниченный рюкзак и DP для размена монет» бесплатный?
Да — полный текст урока «Неограниченный рюкзак и DP для размена монет» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Неограниченный рюкзак и DP для размена монет»?
Используйте элементы любое число раз Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Неограниченный рюкзак и DP для размена монет»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рюкзак 0/1: взять или оставить
- Рюкзак с оптимизацией памяти
- Неограниченный рюкзак и DP для размена монет
- Сумма подмножества и разбиение