Дробный рюкзак по соотношению
Сначала берите элементы с наибольшей ценностью на единицу веса
«Дробный рюкзак по соотношению» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Постановка задачи о рюкзаке
У вас есть предметы с определённой ценностью и весом, а также рюкзак с ограниченной вместимостью. Цель — перенести как можно большую суммарную ценность. 🎒
Дробный вариант допускает деление
В дробном варианте можно взять часть предмета, например половину мешка зерна. Именно эта свобода позволяет жадному алгоритму победить.
Ценность на единицу веса
Главный показатель — это отношение ценности предмета к его весу. Высокое отношение означает, что в небольшом объёме помещается большая ценность.
ratio = value / weightСортировка по лучшему отношению
Отсортируйте предметы по ценности на единицу веса, начиная с наибольшей. Жадный план состоит в том, чтобы всегда брать самый плотный по ценности доступный предмет.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Берите целиком, пока помещается
Пройдите отсортированный список и берите каждый предмет полностью, если он помещается в оставшуюся вместимость. Добавляйте всю его ценность к общей сумме.
if weight <= cap:
total += value
cap -= weightЗаполните последний промежуток
Когда предмет слишком велик, возьмите долю, которая точно заполнит оставшееся место. После этого рюкзак заполнен, и можно остановиться.
total += value * (cap / weight)Почему порядок по отношению работает
Каждая единица вместимости должна содержать как можно большую ценность, поэтому первым нужно помещать предмет с самой высокой плотностью. Замена его предметом с меньшей плотностью только уменьшит ценность.
Задача о рюкзаке 0/1 устроена иначе
Если предметы нельзя разделять, жадный выбор по отношению не работает. Для варианта 0/1 нужно динамическое программирование, а не такая простая сортировка.
Время выполнения
Сортировка по отношению требует O(n log n), а цикл заполнения работает за линейное время. Для обычных ограничений на соревнованиях этого более чем достаточно.
Следите за последней дробью
Для части предмета используйте числа с плавающей точкой или точные рациональные числа. Раннее усечение может уменьшить ценность и привести к неправильному ответу.
Где это встречается
Представьте погрузку груза, смешивание топлива или разделение ресурсов. Если предметы можно делить, жадный алгоритм по отношению — Ваш инструмент.
Быстрая проверка
Вы заполняете сумку в задаче о рюкзаке с дробными предметами.
Итоги
Отсортируйте предметы по ценности на единицу веса, берите целые предметы, пока они помещаются, а затем добавьте дробную часть, чтобы заполнить сумку. Этот жадный алгоритм оптимален только тогда, когда предметы можно разделять. 🚀
Часто задаваемые вопросы
Урок «Дробный рюкзак по соотношению» бесплатный?
Да — полный текст урока «Дробный рюкзак по соотношению» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Дробный рюкзак по соотношению»?
Сначала берите элементы с наибольшей ценностью на единицу веса Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Дробный рюкзак по соотношению»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Жадный подход
- Выбор активностей по самому раннему завершению
- Дробный рюкзак по соотношению
- Как заметить, что жадный подход не работает