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

Максимальное количество чисел с суммой <= S

Даны N чисел. Выбрать максимальное количество чисел, сумма которых не превышает S. Альтернативный вариант — выбрать минимальное количество чисел с суммой >= S.

Сортируем числа по возрастанию (в альтернативном варианте — по убыванию), берём в этом порядке всё, что можем.

Непрерывный рюкзак

Даны N куч золотого песка, i-я куча содержит m[i] килограммов песка стоимостью p[i] рублей за килограмм. Из каждой кучи можно взять любое (не обязательно целое) количество песка. Заполнить рюкзак вместимостью M килограммов так, чтобы стоимость унесённого песка была максимальной.

Сортируем кучи по убыванию стоимости песка p[i], берём в этом порядке всё, что можем.

Выбор заявок

Даны N интервалов. Выбрать максимальное количество непересекающихся интервалов.

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

Покрытие отрезков точками

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

Сортируем по возрастанию правого конца, ставим точку в конце первого отрезка, пропускаем все покрытые ей, ставим точку в конце следующего отрезка, пропускаем все покрытые ей, и так далее.

Выбор заявок, минимизировать количество исполнителей

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

Сортируем по возрастанию левого конца. Проходим по интервалам, назначаем каждому любого свободного исполнителя (если свободных нет, нанимаем ещё одного).

Единичные работы и дедлайны, максимизировать количество

Есть N работ, i-я работа выполняется за время 1 и имеет дедлайн d[i]. Максимизировать количество работ, выполненных до дедлайна.

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

Единичные работы и дедлайны, максимизировать стоимость

Есть N работ, i-я работа выполняется за время 1, имеет дедлайн d[i] и стоимость p[i]. Максимизировать суммарную стоимость работ, выполненных до дедлайна.

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

Работы и дедлайны, минимизировать максимальную задержку

Есть N работ, i-я работа выполняется за время t[i] и имеет дедлайн d[i]. Требуется выполнить все работы. Если работа выполнена в день x, то задержка равна max(0, x - d[i]). Минимизировать максимальную задержку.

Сортируем по возрастанию дедлайнов, выполняем в этом порядке.

Работы и дедлайны со штрафами, максимизировать стоимость

Есть N работ, i-я работа выполняется за время t[i], имеет дедлайн d[i] и стоимость p[i]. Требуется выполнить все работы. Если работа выполнена в день x, за неё платят (d[i] - x) рублей (за просроченные работы отнимают деньги). Максимизировать суммарную стоимость работ с учётом штрафов.

Сортируем по возрастанию времён выполнения, выполняем в этом порядке.

Размен минимальным количеством монет

Даны N номиналов монет, монет каждого вида неограниченно много. Определить минимальное количество монет с заданной суммарной стоимостью.

Каждый раз добавляем монету максимального номинала, не превышающего стоимость (12345 р. = 5000 + 5000 + 2000 + 200 + 100 + 10 + 10 + 10 + 10 + 5 р.).

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

Ссылки

• algorithmica.org — Жадные алгоритмы
• algorithmica.org — Матроиды
• Codeforces — Пересечение матроидов простыми словами