В этом параграфе вы разберёте задачу о том, как с максимальной пользой заполнить ограниченное пространство или ограниченный бюджет. Это пример задачи с дробным выбором: можно взять часть объекта, чтобы извлечь максимум выгоды. Здесь используется жадный отбор по плотности, и важно уметь доказывать, что такая стратегия действительно оптимальна.

Ключевые вопросы параграфа

• Как работает жадный алгоритм в задаче выбора по критерию «прибыль за ресурс»?
• Почему важно доказывать корректность жадного подхода, а не полагаться только на интуицию?
• Как оформить решение, чтобы оно было корректным, понятным и быстрым?

Дробный выбор

Представим, что вы владелец популярной страницы в интернете, на которой есть рекламных мест. Вы хотите продать их рекламодателям, которые рассчитывают на , и кликов в день и при этом готовы платить , и за клик. Как подобрать пары рекламных мест и рекламодателей так, чтобы получить максимальную прибыль? Например, доход от отмеченных голубым цветом пар, приведённых выше, составит долларов; от отмеченных чёрным — .

• Входные данные: В первой строке приведено целое число , во второй — последовательность целых чисел , в третьей — последовательность целых чисел .
• Выходные данные: Максимальное значение , где — это перестановка .
• Ограничения: ; для всех .

Пример 1

.

Пример 2

.

Решение

Суть решения заключается в том, чтобы отдать самое популярное рекламное место самому дорогому объявлению. Вас вряд ли удивит, что жадный подход даст максимальную прибыль.

Предположим, что и — самые большие элементы: и для всех . Мы утверждаем, что существует оптимальное решение, объединяющее с .

Чтобы доказать это, возьмём оптимальное решение и предположим, что в нём объединены и для и и для . Покажем, что замена пар и на пары и только повысит прибыль.

Давайте оценим, как такая замена повлияет на общую прибыль. До замены рассматриваемые элементы давали следующую прибыль:

После замены:

Таким образом, замена увеличивает общую прибыль на

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

1Revenue(Click,Price):
2     revenue = 0
3     while clicks is not empty:
4        p = index with largest Click[p]
5        q = index with largest Price[q]
6        revenue = revenue+Clicks[p]⋅Price[q]
7        remove p-th element of Click
8        remove q-th element of Price
9     return revenue

Время выполнения.

Время выполнения этого алгоритма — . В каждой из итераций мы проводим линейное сканирование и находим два самых больших элемента. Также можно отсортировать эти два списка заранее, чтобы не искать самый большой элемент с нуля при каждой итерации. Это приводит нас к решению с временем выполнения .

Что дальше

Теперь вы знаете, как работать с задачами, где допускается дробный выбор, и почему жадный отбор по плотности гарантирует оптимальное решение. Вы также увидели, что при работе с вещественными числами важно следить за точностью вычислений и оформлением кода.

Далее — задача с другим типом постановки: нужно покрыть набор отрезков минимальным числом точек. Такой приём встречается, например, в планировании размещения рекламных щитов вдоль трассы или выборе минимального числа дат для встреч, чтобы все участники могли присутствовать. Это ещё один пример, где жадный алгоритм работает эффективно, — если правильно обосновать его корректность.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• В задачах с «дробным» выбором можно брать часть объекта, чтобы максимизировать результат — это принципиально отличается от дискретных задач.
• Жадная стратегия по убыванию плотности гарантирует оптимальное решение именно в дробном случае, но не всегда работает для целочисленных вариантов.
• Доказательство оптимальности помогает понять границы применения жадных алгоритмов и увидеть, где они перестают работать.
• Работа с вещественными числами требует особой аккуратности, чтобы избежать ошибок округления и потери точности.