Методы разработки алгоритмов. Жадные алгоритмы - ABCD42.RU

Методы разработки алгоритмов. Жадные алгоритмы

Жадные алгоритмы

Доброго времени суток, хабр! Сегодня я бы хотел рассказать про жадные алгоритмы.

Есть много методов решения тех или иных задач: динамическое программирование, перебор. Не менее известными и довольно распространенными являются жадные алгоритмы.

Думаю, каждый программист в своей жизни хотя бы раз написал жадину, может быть, даже не задумываясь об этом. Что же это такое? Добро пожаловать под кат.

Жадность не порок

Итак, жадный алгоритм (greedy algorithm) — это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным.
К примеру, алгоритм Дейкстры нахождения кратчайшего пути в графе вполне себе жадный, потому что мы на каждом шагу ищем вершину с наименьшим весом, в которой мы еще не бывали, после чего обновляем значения других вершин. При этом можно доказать, что кратчайшие пути, найденные в вершинах, являются оптимальными.

К слову, алгоритм Флойда, который тоже ищет кратчайшие пути в графе (правда, между всеми вершинами), не является примером жадного алгоритма. Флойд демонстрирует другой метод — метод динамического программирования.

Использование жадного алгоритма довольно стандартное. Рассмотрим его на примере следующей задачи:

Задача о расписании

Пусть программисту-фрилансеру Васе Пупкину дано n заданий. У каждого задания известен свой дедлайн, а также его стоимость(то есть если он не выполняет это задание, то он теряет столько-то денег). Вася настолько крут, что за один день может сделать одно задание. Выполнение задания можно начать с момента 0. Нужно максимизировать прибыль.

Классический пример применения жадины: Васе выгодно делать самые «дорогие задания», а наименее дорогие можно и не выполнять — тогда прибыль будет максимальна. Возникает вопрос: каким образом распределить задания? Будем перебирать задания в порядке убывания стоимости и заполнять расписание следующим образом: если для заказа есть еще хотя бы одно свободное место в расписании раньше его дедлайна, то поставим его на самое последнее из таких мест, в противном случае в срок мы его не можем выполнить, значит поставим в конец из свободных мест.

Получается следующий код:

//tasks — массив заданий
Arrays.sort(tasks); //сортируем по убыванию стоимости
TreeSet time = new TreeSet ();
for ( int i = 1; i int ans = 0;
for ( int i = 0; i if (tmp == null ) < // если нет свободного места в расписании, то в конец
time.remove(time.last());
> else < //иначе можно выполнить задание, добавляем в расписание
time.remove(tmp);
ans += tasks[i].cost;
>
>

Когда можно быть жадным?

Всегда Иногда может возникнуть искушение использовать жадину везде, где только это возможно, но на некоторых задачах это неприемлимо. К примеру, задача о рюкзаке: вор пробрался на склад, в котором хранятся три вещи весом 10 кг, 20 кг и 30 кг и стоимостью 60, 100 и 120 деревянных вечнозеленых нанорублей соответственно. Вор максимум может унести 50 кг. Нужно максимизировать прибыль вора. Если поступать здесь жадно и выбирать самую ценную вещь(то есть, 6 нанорублей за кг первой штуки, 5 нанорублей за кг второй и 4 нанорубля за кг третьей), то вор по-любому должен взять первую вещь, потом останется место для второй вещи, однако оптимальное решение составляет вторая и третья вещь.

Вывод: если собрались что-то грабить, то берите с собой грузовик. есть область применимости жадных алгоритмов. Общих рецептов тут нет, но есть довольно мощный инструмент, с помощью которого в большинстве случаев можно определить, даст ли жадина оптимальное решение. Называется матроид.

Жизнь не матроид, жизнь — конечный автомат!

Как подсказывает википедия, матроид — это пара (X, I), где X — конечное множество, называемое носителем матроида, а I — некоторое множество подмножеств X, называемое семейством независимых множеств. При этом должны выполняться следующие условия:


  1. Множество I непусто. Даже если исходное множество X было пусто — X = Ø, то I будет состоять из одного элемента — множества, содержащего пустое. I = <<Ø>>

  2. Любое подмножество любого элемента множества I также будет элементом этого множества.

  3. Если множества A и B принадлежат множеству I, а также известно, что размер А меньше B, то существует какой-нибудь элемент x из B, не принадлежащий А, такое что объединение x и A будет принадлежать множеству I. Это свойство является не совсем тривиальным, но чаще всего наиважшейшим из всех остальных.

Матроид называется взвешенным, если на множестве X существует аддитивная весовая функция w. Вес множества будет определяться как сумма весов его элементов.

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

  1. первое свойство, очевидно, выполняется. Пустое множество выполненных заданий входит в наше множество. Ну и пофиг, что Вася не хочет зарабатывать деньги.
  2. второе множество тоже выполняется. Почему это так: давайте отсортируем успешно выполненные задания в порядке увеличения дедлайна. В таком порядке они все равно будут успешно выполненными. В таком порядке очевидно, что любое подмножество успешно выполненных заданий будет успешно выполнено.
  3. третье свойство, хоть и не очевидно, но выполняется. Пусть у нас есть два множества успешно выполненных заданий A и B, при чем известно, что |A|

Основные методы разработки алгоритмов

Общие методы разработки алгоритмов – это наиболее общие подходы к разработке алгоритмов, которые можно применить к самым разнообразным задачам.

Основные методы разработки алгоритмов :

· метод грубой силы (с исчерпывающим перебором в качестве

· поиск с возвратом

· уменьшение размера задачи

· метод ветвей и границ

Замечание: решение некоторых задач требует применения более одного метода.

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

Примеры из информатики:

сортировка выбором и пузырьковая сортировка;

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

не могут привести к правильному решению задачи.

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

· может быть применен либо сверху вниз, то есть рекурсивно, либо снизу вверх, то есть итеративно

· также известен под именем «индуктивный подход»

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

Метод преобразования

· в более простой случай той же задачи

· в другую форму той же задачи

· в другую задачу с известным решением

Жадный метод – это подход к решению задач оптимизации, в которых на каждом шагу делается выбор, который

· удовлетворяет всем ограничениям задачи;

Жадный подход приводит к корректному решению некоторых задач оптимизации, но не работает для других.

Динамическое программирование

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

В информатике ДП интерпретируется как подход к решению задач с пересекающимися подзадачами, не обязательно оптимизационного характера:

− решите все меньшие подзадачи, но один раз;

− занесите решения в таблицу;

− возьмите решение для нужного случая из этой таблицы.

Метод ветвей и границ

1) Улучшение поиска с возвратом для оптимизационных

2) Для каждого узла (частично построенного решения) в

дереве пространства состояний метод вычисляет оценку

величины оптимизируемой функции во всех потомках

этого узла (расширений этого частичного решения)

3) Оценка используется для

· отбрасывания бесперспективных вершин

· определения порядка построения дерева (узел с лучшей оценкой обычно исследуется раньше остальных)

Вопрос 29

Исполнитель алгоритма — это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный набор действий.
Исполнителя характеризуют:
• среда;
• элементарные действия;
• система команд;
• отказы.
Исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов «почему» и «зачем».
Про компьютер говорят, что он универсальный исполнитель алгоритмов, созданных для обработки информации. Компьютер может исполнять алгоритм, если он написан на одном из языков программирования. Такой алгоритм называют компьютерной программой. Программу можно ввести в память компьютера и запустить её. Тогда она может быть автоматически исполнена компьютером. В этом случае исполнителем алгоритма является компьютер.

Методы разработки алгоритмов

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

Метод декомпозиции (или метод разбиения, или метод «разделяй и властвуй») является одним из самых распространенных методов проектирования алгоритмов. Он предполагает такую декомпозицию (разбиение) задачи размера n на более мелкие подзадачи, так что на основе решения этих более мелких подзадач можно легко получить решение исходной задачи. Как правило, алгоритмы, разработанные этим методом отличаются легкостью разработки и высокой эффективностью.

Проиллюстрируем этот метод на известной головоломке «Ханойские башни». Имеются три стержня А, B и С. На стержень А вначале одеты несколько дисков разного размера, причем диск меньшего размера должен лежать только на диске большего размера. Цель головоломки – перемещать диски по одному со стержня на стержень так, чтобы диск большего размера никогда не оказывался выше диска меньшего размера. Требуется переместить все диски на стержень B. Стержень С является вспомогательным и используется для временного хранения дисков.

Применяя метод декомпозиции, представим задачу перемещения n дисков состоящей из двух подзадач размера n-1. Сначала переместим n-1 наименьших дисков со стержня А на стержень C, затем оставшийся наибольший диск переместим на стержень B. Далее аналогично поступаем к задаче перемещения n-1 дисков, но со стержня С на стержень B, выполняя подзадачи перемещения n-2 дисков. Это перемещение выполняется путем рекурсивного применения описанного метода.

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

«Жадный алгоритм» на каждой отдельной стадии решения задачи выбирает тот вариант, который на данном этапе является локально оптимальным. Для примера рассмотрим задачу составления заданной суммы, например 63 коп., из имеющихся монет достоинством 25, 10, 5 коп. и 1 коп.. «Жадный» алгоритм заключается в выборе каждый раз монеты наибольшего достоинства, не превышающей по стоимости оставшейся суммы, добавление ее в список монет и вычитании ее стоимости из оставшейся суммы. Алгоритм быстро приведет к решению: 2 монеты по 25 коп., 1 монета в 10 коп., 3 монеты по 1 коп.. «жадные» алгоритмы позволяют получать хорошие решения, однако не всегда эти решения являются оптимальными при различных условиях задачи. Так, если надо набрать сумму в 15 коп. из монет достоинством 11, 5 коп. и 1 коп., то «жадный» алгоритм даст результат: 1 монета в 11 коп. и 4 монеты по 1 коп. ( всего 5 монет). В то же время, можно было бы обойтись 3 монетами достоинством в 5 коп..

Метод поиска с возвратом ( или метод полного перебора) применяется в задачах поиска оптимального решения, когда не удается применить ни один из описанных выше алгоритмов. Обычно это последнее средство для решения задачи, когда рассматриваются все возможные варианты, среди которых и отыскивается оптимальное решение.

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

1. Начнем с произвольного решения.

2. Для улучшения текущего решения применим к нему какое-либо преобразо-

вание на некоторой заданной совокупности преобразований. Это улучшенное решение становится новым «текущим» решением.

3. Повторяем указанную процедуру до тех пор, пока ни одно из преобразова-

ний из заданной совокупности не позволяет улучшить текущее решение.

1) Жадный алгоритм

Что такое жадный алгоритм?

В GREEDY ALGORITHM набор ресурсов рекурсивно разделяется на основе максимальной, немедленной доступности этого ресурса на любом этапе выполнения.

Чтобы решить проблему, основанную на жадном подходе, есть два этапа

  1. сканирование списка предметов
  2. оптимизация.

Эти этапы выполняются параллельно по ходу деления массива.

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

Два условия определяют жадную парадигму.

  • Каждое поэтапное решение должно структурировать проблему в направлении ее наиболее приемлемого решения.
  • Достаточно, если структурирование проблемы может остановиться за конечное число жадных шагов.

Продолжив теоретизирование, давайте опишем историю, связанную с жадным подходом.

В этом уроке Greedy вы узнаете:

  • История жадных алгоритмов
  • Жадные стратегии и решения
  • Характеристики жадного подхода
  • Зачем использовать жадный подход?
  • Как решить проблему выбора активности
  • Архитектура Жадного подхода
  • Недостатки жадных алгоритмов

История жадных алгоритмов

Вот важный ориентир жадных алгоритмов:

  • Жадные алгоритмы были концептуализированы для многих алгоритмов обхода графов в 1950-х годах.
  • Эсдгер Джикстра концептуализировал алгоритм для генерации минимальных остовных деревьев. Он стремился сократить количество маршрутов в столице Нидерландов Амстердаме.
  • В том же десятилетии Prim и Kruskal разработали стратегии оптимизации, основанные на минимизации затрат на пути по взвешенным маршрутам.
  • В 70-х годах американские исследователи, Cormen, Rivest и Stein, предложили рекурсивную подструктуризацию жадных решений в своем классическом введении в книгу алгоритмов.
  • Жадная парадигма была зарегистрирована как стратегия оптимизации другого типа в записях NIST в 2005 году.
  • До сегодняшнего дня протоколы, которые работают в сети, такие как OSPF и многие другие сетевые протоколы коммутации пакетов, используют жадную стратегию, чтобы минимизировать время, затрачиваемое в сети.

Жадные стратегии и решения

Логика в ее самой простой форме сводилась к «жадному» или «не жадному». Эти утверждения были определены подходом, принятым для продвижения на каждой стадии алгоритма.

Например, алгоритм Джикстра использовал пошаговую жадную стратегию, идентифицирующую хосты в Интернете путем вычисления функции стоимости. Значение, возвращаемое функцией стоимости, определяет, является ли следующий путь «жадным» или «не жадным».

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

Характеристики жадного подхода

Важными характеристиками жадного метода являются:

  • Существует упорядоченный список ресурсов с указанием стоимости или стоимости. Эти количественные ограничения на систему.
  • Вы возьмете максимальное количество ресурсов за время применения ограничения.
  • Например, в задаче планирования операций стоимость ресурсов указывается в часах, и действия должны выполняться в последовательном порядке.

Зачем использовать жадный подход?

Вот причины использования жадного подхода:

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

Как решить проблему выбора активности

В примере планирования действий есть время «начала» и «окончания» для каждого действия. Каждое мероприятие индексируется номером для справки. Есть две категории деятельности.

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

Общая продолжительность дает стоимость выполнения действия. То есть (финиш — старт) дает нам длительность как стоимость деятельности.

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

Архитектура Жадного подхода

ШАГ 1)

Сканирование списка затрат на деятельность, начиная с индекса 0 в качестве рассматриваемого индекса.

ШАГ 2)

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

ШАГ 3)

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

Жадные алгоритмы

Жадный алгоритм (англ. Greedy algorithm ) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

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

Содержание

Применимость жадных алгоритмов

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

Принцип жадного выбора

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

Свойство оптимальности для подзадач

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если A — оптимальный набор заявок, содержащий заявку номер 1, то — оптимальный набор заявок для меньшего множества заявок , состоящего из тех заявок, для которых .

Примеры

Размен монет

Задача. Монетная система некоторого государства состоит из монет достоинством a1 = 1 . Требуется выдать сумму S наименьшим возможным количеством монет.

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства an : . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 10 копеек монетами в 1, 5 и 6 коп. жадный алгоритм разменивает так: 6 коп. — 1 шт., 1 коп. — 4 шт., в то время как правильное решение — 2 монеты по 5 копеек. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.

Выбор заявок

Задача. Даны n заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ( si и fi для i -й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами i и j совместны, если интервалы [si,fi) и [sj,fj) не пересекаются (то есть или ). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Формулировка № 2. На конференции, чтобы отвести больше времени на неформальное общение, различные секции разнесли по разным аудиториям. Учёный с чрезвычайно широкими интересами хочет посетить несколько докладов, проходящих в разных секциях. Известно начало si и конец fi каждого доклада. Определить, какое максимальное количество докладов можно посетить.

Приведем жадный алгоритм, решающий данную задачу. При этом полагаем, что заявки упорядочены в порядке возрастания времени окончания. Если это не так, то можно отсортировать их за время O(nlogn + n) ; заявки с одинаковым временем конца располагаем в произвольном порядке.

  1. length[s]
  2. for to n
    • do if
      • then
  3. return A

На вход данному алгоритму подаются массивы начала и окончания занятий. Множество A состоит из номеров выбранных заявок, а j — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания j-той, затем найденную заявку включает в A, а j присваивает ее номер.

Алгоритм работает за O(nlogn + n) , то есть сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.

Доказательство. Заметим, что все заявки отсортированы по неубыванию времени окончания. Заявка номер 1, очевидно, входит в оптимум (если нет, то заменим самую раннюю заявку в оптимуме на нее, от этого хуже не станет). Выкинув все заявки, противоречащие первой, получим исходную задачу с меньшим количеством заявок. Рассуждая по индукции, аналогичным образом приходим к оптимальному решению.

Другие жадные алгоритмы

  • Алгоритм Хаффмана (адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью)
  • Алгоритм Краскала (поиск остовного леса минимального веса в графе)
  • Алгоритм Прима (поиск остовного дерева минимального веса в связном графе)

Обобщением жадных алгоритмов является алгоритм Радо — Эдмондса.

Жадный алгоритм

Это не какой-то алгоритм, а скорее простая идея о том, как решаются многие задачи.

Пример задачи: Размен монет

Условие

Есть купюры и монеты номиналами: (1, 5, 10, 50, 100, 1000, 5000) рублей. В банкомате неограниченное количество купюр каждого номинала. Константин хочет снять со счёта (n) рублей. Нужно определить минимальное суммарное количество купюр и монет, которое может выдать банкомат, чтобы сумма получилась ровно (n) .

Решение

Выпишем первые несколько ответов на задачу:

Хочется сказать, что оптимальным алгоритмом будет следующее: взять максимум купюр номинала (1000) , из остатка взять максимум купюр номинала (500) и т.д. Причем это будет верным решением! Такой подход в решении называются “жадностью”. А алгоритмы, работающие таким образом, “жадными”.

Общая идея жадного алгоритма

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

Чем-то это похоже на математический “принцип крайнего” — всегда будет полезно посмотреть на самый крайний (максимальный или минимальный элемент), очень часто решение начинается именно с него.

Доказательство решения

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

Вместо того, чтобы доказывать утверждение про жадность для конкретной задачи про числа (1, 5, 10, 50, 100, 1000, 5000) , давайте сформулируем и докажем более сильное:

Если каждый следующий номинал делится на предыдущий, то жадный алгоритм работает.

Доказательство утверждения:

Пусть купюры имели номинал (a_1, ldots, a_k) . Пусть максимальная купюра имеет достоинство (a_k) и (a_k , но в оптимальном ответе ее нет. Давайте рассмотрим такой оптимальный ответ и найдем противоречие.

Пусть в оптимальном ответе купюра с номиналом (a_i) встретилась (b_i) раз. Если (b geq frac>) раз, то (frac>) купюр можно легко заменить на одну купюру достоинства (a_) , а значит это не оптимальный ответ. Следовательно, (b leq frac> — 1)

Давайте посчитаем, какого достоинства может быть сумма всех достоинств всех купюр в оптимальном ответе, если не считать максимальные купюры. Это будет [a_1 b_1 + a_2 b_2 + ldots + a_ b_ leq a_1 (frac — 1) + a_2 (frac — 1) + ldots + a_ (frac> — 1) =] [= (a_2 — a_1) + (a_3 — a_2) + ldots + (a_k — a_) = a_k — a_1

Из этого делаем вывод, что если (n geq a_k) , то в оптимальный ответ всегда придется взять максмальную купюру размера (a_k) , потому что меньшие купюры просто не смогут оптимальном ответе давать так много. Отсюда и следует корректность жадного алгоритма.

Теперь, когда жадность доказана, можно предъявить алгоритм:

Пример задачи: Задача о рюкзаке с делимыми предметами

Условие

Пусть есть рюкзак с вместимостью не более, чем (W) грамм ( (W) — целое) и (n) предметов весом (w_i) грамм и стоимостью (c_i) за грамм. Мы умеем отрезать от любого предмета целое количество грамм. Требуется набрать рюкзак максимальной стоимости.

Решение

Также будем решать эту задачу жадно. Отсортируем предметы по убыванию “плотности ценности” (frac) и будем брать их жадно. От последнего предмета, который не влезет полностью, возьмем часть.

Доказательство

Давайте представим, что мы уже поделили все предметы на кусочки веса 1 грамм, при этом их ценность стала равна (frac) . Понятно, что из кусочков одинакого веса 1 грамм всегда оптимально просто взять кусочки с максимальной ценностью.

Заметим, что в жадном алгоритме мы как раз и набираем максимальные по (frac) кусочки веса 1.

Итоговая асимптотика: (O(n + nlog n) = O(nlog n)) .

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

Пример задачи: Выбор заявок

Условие

Даны заявки на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия ((s_i) и (f_i) для (i) -ой заявки). Нужно из всех заявок оставить как можно больше так, чтобы они не пересекались. При этом если одна заявка закончилась во время (t) , а следующая началась во время (t) , то их можно ставить подряд.

Решение

Здесь жадность становится не такой уже очевидной, потому что неясно в каком порядке рассматривать заявки, те непонятно как “жадно” их набирать.

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

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

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

Задание

Вам нужно решить как можно больше задач из этого контеста:

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: