Жадными называют класс алгоритмов, заключающихся в принятии локально оптимальных решений на каждом этапе. Так как локально оптимальное решение вычислить гораздо проще, чем глобально оптимальное, такие алгоритмы обычно имеют хорошую асимптотику.
В некоторых случаях жадные алгоритмы приводят к оптимальным конечным решениям, а в других — нет. Придумать и особенно доказать корректность жадных алгоритмов часто бывает очень сложно.
В этой статье мы разберем несколько классических примеров задач, решающихся жадным алгоритмом.
Монетки
Задача. Монетная система некоторого государства состоит из монет достоинством $a_1 = 1 < a_2 < a_3 < \ldots < a_n$, причём каждый следующий номинал делится на предыдущий. Требуется выдать сумму $S$ наименьшим возможным количеством монет.
Жадный алгоритм решения этой задачи заключается в том, что нужно сначала взять наибольшее количество монет достоинства $a_n$ (а именно, $\lfloor \frac{S}{a_n} \rfloor$), затем для набора остатка взять наибольшее количество монет достоинства $a_{n-1}$ и так далее. Так как $a_1 = 1$, в конце мы всегда наберем нужную сумму.
a = [1, 2, 5, 10, 50, 100, 500, 1000, 2000, 5000]
def solution(s):
coins = []
for x in reversed(a):
coins += [x] * (s // x)
s %= x
return coins
Заметим, что без предположения, что номиналы монет делятся друг на друга, алгоритм не всегда выводит оптимальное решение, и в этом случае задачу остается решать динамическим программированием. Например, сумму в 24 рубля монетами в 1, 5 и 7 рублей жадный алгоритм разменивает как $(7 \times 3 + 1 \times 3)$, в то время как оптимальным будет $(7 \times 2 + 5 \times 2)$.
Корректность. Докажем корректность жадного алгоритма от противного: пусть максимальная монета имеет достоинство $a_n < S$, но в оптимальном ответе её нет.
Пусть в оптимальном ответе монета с номиналом $a_i$ встретилась $b_i$ раз:
$$ S = \sum a_i \cdot b_i $$Если $b_i \geq \frac{a_{i+1}}{a_i}$, то $\frac{a_{i+1}}{a_i}$ монет можно заменить на одну монету достоинства $a_{i+1}$, а значит это не оптимальный ответ. Следовательно, $b_i \leq \frac{a_{i+1}}{a_i} - 1$.
Теперь посчитаем, какой может быть максимальная сумма всех достоинств всех монет в оптимальном ответе, если мы не брали максимальные монеты:
$$ \begin{aligned} S &= a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots + a_{n-1} \cdot b_{n-1} \\ &\leq a_1 \cdot (\frac{a_2}{a_1} - 1) + a_2 \cdot (\frac{a_3}{a_2} - 1) + \ldots + a_{n-1} \cdot (\frac{a_n}{a_{n-1}} - 1) \\ &= (a_2 - a_1) + (a_3 - a_2) + \ldots + (a_n - a_{n-1}) \\ &= a_n - a_1 < a_n \end{aligned} $$Отсюда делаем вывод, что если $S \geq a_n$, то в оптимальный ответ всегда придется взять максимальную монету размера $a_k$, потому что все меньшие монеты просто не смогут оптимальном ответе давать так много. Аналогичным размышлением про наборы из меньших монет получаем такой же результат для всех $S < a_n$, откуда следует корректность жадного алгоритма.
Также этот алгоритм работает не только для делящихся друг на друга номинациях, но и для некоторых других. Такие монетные системы, где жадный алгоритм работает, называют каноническими.
Упражнение. Верно ли, что алгоритм работает корректно для российской монетной системы (1, 2, 5…)?
Рюкзак с делимыми предметами
Задача. Пусть есть рюкзак с вместимостью не более, чем $W$ грамм и $n$ предметов весом $w_i$ грамм и стоимостью $c_i$ за грамм. Мы умеем отрезать от любого предмета целое количество грамм. Требуется набрать рюкзак максимальной стоимости.
Отсортируем предметы по убыванию «плотности ценности» $\frac{c_i}{w_i}$ и будем брать их жадно в таком порядке. От последнего предмета, который не влезет полностью, возьмем часть.
Корректность. Мысленно разделим все предметы на $w_i$ кусочков по 1 грамм, и при этом их ценность стала равна $\frac{c_i}{w_i}$. Понятно, что из кусочков одинакового веса 1 грамм всегда оптимально просто взять кусочки с максимальной ценностью, что мы фактически и делаем в нашем алгоритме.
Итоговая асимптотика $O(n \log n)$ на сортировку.
Выбор заявок
Задача. Даны заявки на проведение занятий в некоторой аудитории. В каждой заявке указаны начало $l_i$ и конец $r_i$ занятия. Нужно из всех заявок оставить как можно больше таким образом, чтобы они не пересекались.
Здесь жадность становится не такой уже очевидной, потому что неясно, в каком порядке рассматривать заявки и как их «жадно» набирать.
Посмотрим на первую по времени конца заявку. Заметим, что нам всегда выгодно включить её в оптимальный ответ — она заканчивается раньше всех остальных, а поэтому если в оптимальном ответе первая заявка какая-то другая, мы можем безболезненно заменить её на первую по времени конца, и при этом новых пересечений не появится, так как мы просто сдвинули самую первую заявку еще левее.
После того, как мы выбрали первую по времени конца, уберем из рассмотрения все, которые с ней пересекаются, и так же выберем из оставшихся первую по времени конца, снова уберем все пересекающиеся и так далее, пока заявки не кончатся.
При реализации удобно не удалять отрезки явно, а просто отсортировать отрезки по времени конца и поддерживать время, когда кончается последнее взятое занятие.
struct activity {
int l, r;
};
int solve(vector<activity> activities) {
sort(activities.begin(), activities.end(), [](activity a, activity b) {
return a.r < b.r;
});
int cnt = 0, last = 0;
for (activity a : activities)
if (a.l >= last)
last = a.r, cnt++;
return cnt;
}
Асимптотика $O(n \log n)$ на сортировку.