Рюкзак 0/1: взять или оставить
Максимизируйте ценность при ограничении веса
«Рюкзак 0/1: взять или оставить» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
История о рюкзаке
У Вас есть рюкзак с ограничением по весу и куча предметов. В задаче о рюкзаке 0/1 требуется выбрать предметы с максимальной ценностью, не превысив вместимость. 🎒
Взять или оставить
Обозначение 0/1 означает, что каждый предмет можно либо взять целиком, либо полностью пропустить. Нельзя взять только часть предмета, поэтому каждый выбор сводится к «да» или «нет».
Почему жадный подход не работает
Если сначала брать самый дешёвый или самый ценный предмет, можно нерационально потратить вместимость. Жадное упрощение здесь не работает, поэтому нужно рассматривать реальные сочетания предметов.
Два входных набора данных
Вам даны два параллельных списка: вес и ценность каждого предмета, а также одна вместимость. У предмета i вес wt[i] и ценность val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Определите состояние
Пусть dp[i][w] — максимальная ценность, которую можно получить, используя первые i предметов при вместимости w. Точное именование состояния — основа всего решения.
Выбор: пропустить
Если Вы пропускаете предмет i, ценность остаётся прежней: dp[i-1][w]. Оставшаяся вместимость не меняется.
Выбор: взять
Если Вы берёте предмет i, добавьте его ценность и уменьшите вместимость: val[i] + dp[i-1][w - wt[i]]. Это допустимо только когда w не меньше wt[i].
Выберите лучший вариант
Рекуррентное соотношение с помощью max просто оставляет больший из двух вариантов. Каждая ячейка использует уже вычисленные ответы из строки выше.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])Базовая строка
Если предметов нет, при любой вместимости можно перенести ценность, равную нулю. Этот базовый случай заполняет первую строку нулями, на которых строится дальнейшее решение.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Заполните таблицу
Во внешнем цикле перебирайте предметы, а во внутреннем — вместимость. Каждая ячейка читает данные только из строки выше, поэтому одного прохода достаточно, чтобы заполнить всё.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Прочитайте ответ
В правой нижней ячейке dp[n][cap] хранится максимальная ценность для всех предметов при полной вместимости. Эта ячейка и есть Ваш окончательный ответ.
Быстрая проверка
Проверьте основное рекуррентное соотношение для рюкзака 0/1.
Итоги
Вы изучили рюкзак 0/1: каждый предмет можно взять или оставить, dp[i][w] хранит лучший результат из вариантов «пропустить» и «взять», а dp[n][cap] является ответом. 🎉
Изучай Python с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 30
- Уроки
- 120
Часто задаваемые вопросы
Урок «Рюкзак 0/1: взять или оставить» бесплатный?
Да — полный текст урока «Рюкзак 0/1: взять или оставить» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Рюкзак 0/1: взять или оставить»?
Максимизируйте ценность при ограничении веса Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Рюкзак 0/1: взять или оставить»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рюкзак 0/1: взять или оставить
- Рюкзак с оптимизацией памяти
- Неограниченный рюкзак и DP для размена монет
- Сумма подмножества и разбиение