Где применяется
1. Задача
Шаг 107 брал встречи целиком и сортировал их по раннему концу. Здесь ты снова выбираешь жадно по ключу сортировки, но ключ другой. И есть новое условие, которое меняет решение: предмет можно взять частично.
У тебя есть мешок, который выдерживает ограниченный общий вес, и много товаров. У каждого товара есть вес и ценность. Это золотой песок, зерно, масло: товары, которые можно отсыпать или отлить частями, а не только взять или оставить целиком. Нужна наибольшая суммарная ценность, которую унесёт мешок.
Пример: грузовик на 50 кг и три мешка. Первый весит 10 кг и стоит 60, второй 20 кг и стоит 100, третий 30 кг и стоит 120. Все 60 кг не поместятся, но из мешка можно отсыпать часть. Нужно решить, что брать и сколько, чтобы груз стоил как можно больше.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
На LeetCode нет задачи, где можно взять часть предмета. Зато там проверяют то, что из урока переносится, сортировку по ценности на единицу и выбор сверху, в задачах, где у всех предметов одинаковый размер или порядок решает отношение.
Каждая коробка занимает одно место в грузовике, так что отсортируй типы по числу единиц в коробке и бери сверху, пока грузовик не заполнится.
Отсортируй мешки по тому, сколько камней каждому не хватает, и заполняй сначала самые дешёвые. Это жадный выбор урока, где цена это недостача.
Отсортируй работников по оплате за единицу качества, это сортировка по отношению из урока, а потом держи k наименьших качеств в макс-куче, пока отношение растёт.