Дробный рюкзак по соотношению

У вас есть предметы с определённой ценностью и весом, а также рюкзак с ограниченной вместимостью. Цель — перенести как можно большую суммарную ценность. 🎒

В дробном варианте можно взять часть предмета, например половину мешка зерна. Именно эта свобода позволяет жадному алгоритму победить.

Главный показатель — это отношение ценности предмета к его весу. Высокое отношение означает, что в небольшом объёме помещается большая ценность.

Отсортируйте предметы по ценности на единицу веса, начиная с наибольшей. Жадный план состоит в том, чтобы всегда брать самый плотный по ценности доступный предмет.

Пройдите отсортированный список и берите каждый предмет полностью, если он помещается в оставшуюся вместимость. Добавляйте всю его ценность к общей сумме.

Когда предмет слишком велик, возьмите долю, которая точно заполнит оставшееся место. После этого рюкзак заполнен, и можно остановиться.

Каждая единица вместимости должна содержать как можно большую ценность, поэтому первым нужно помещать предмет с самой высокой плотностью. Замена его предметом с меньшей плотностью только уменьшит ценность.

Если предметы нельзя разделять, жадный выбор по отношению не работает. Для варианта 0/1 нужно динамическое программирование, а не такая простая сортировка.

Сортировка по отношению требует O(n log n), а цикл заполнения работает за линейное время. Для обычных ограничений на соревнованиях этого более чем достаточно.

Для части предмета используйте числа с плавающей точкой или точные рациональные числа. Раннее усечение может уменьшить ценность и привести к неправильному ответу.

Представьте погрузку груза, смешивание топлива или разделение ресурсов. Если предметы можно делить, жадный алгоритм по отношению — Ваш инструмент.

Отсортируйте предметы по ценности на единицу веса, берите целые предметы, пока они помещаются, а затем добавьте дробную часть, чтобы заполнить сумку. Этот жадный алгоритм оптимален только тогда, когда предметы можно разделять. 🚀