алгоритмы · справочникжадные алгоритмы
SilverTests.ru · УчебникЖадные алгоритмы — введение
Жадные алгоритмы
На каждом шаге — самый «выгодный» выбор, и он оказывается правильным
кратко
Узнаем, что такое жадный алгоритм. Разберём классическую задачу про отрезки. Научимся замечать жадность в условии.
1Идея: выбирай по одному, лучшее
Представь: тебя пустили на склад, где лежат золотые слитки разного размера. Разрешили унести столько, сколько сам поднимешь — но общий вес не больше 20 кг. Как выбирать?
Большинство людей сразу скажет: «Беру самые тяжёлые, пока могу». Это и есть жадный алгоритм — на каждом шаге выбираем самый выгодный вариант из доступных, не заглядывая вперёд.
Такой подход работает не всегда, но когда работает — это самое быстрое и простое решение. Весь фокус — понять, когда он работает, и какой именно критерий «выгодности» брать.
Жадный алгоритм — это стратегия, где на каждом шаге мы делаем локально-оптимальный выбор (что лучше прямо сейчас?) и надеемся получить глобально-оптимальный ответ (что лучше в итоге?).
2Задача: максимум встреч
У тебя один кабинет и 8 заявок на встречи. Каждая встреча — это отрезок времени [начало; конец]. Две встречи нельзя провести одновременно — они должны не пересекаться. Сколько встреч максимум можно провести?
Первое что приходит в голову — брать самые короткие. Мол, короткая встреча оставляет больше времени другим. Давай проверим.
Поиграй с алгоритмом
Нажми кнопку, чтобы запустить жадный выбор. «Новый набор» — сгенерировать другие встречи.
Зелёным — выбранные встречи. Красным — отклонённые (пересекаются с уже выбранной). Обрати внимание, сколько встреч выбирается в каждом режиме.
3Почему «самые короткие» не работает
Возьми такой пример — три встречи:
| Встреча |
Начало |
Конец |
Длина |
| A |
1 |
4 |
3 |
| B |
3 |
6 |
3 |
| C |
5 |
8 |
3 |
Все одинаковой длины — жадность «по длине» не сработает. А вот если взять по правому концу: сначала A (кончается в 4), потом пропускаем B (3 ≤ 4), берём C (5 > 4). Ответ 2.
Классический контрпример, где «самые короткие» явно проигрывает — встречи A[1;10], B[9;11], C[10;20]. «Самая короткая» B[9;11] пересекается с обеими другими — получаем 1. А по правому концу: A (до 10), C (начинается в 10 — это край, не пересекается) — получаем 2.
4Правильный жадный критерий
Алгоритм
1. Отсортировать встречи по правому концу (по времени окончания), от меньшего к большему.
2. Идти по списку слева направо. Брать встречу, если её начало больше правого конца последней взятой.
3. Считать взятые.
Показать код (C++ / Python)
1// n встреч, каждая задана парой (l, r)
2int n;
3cin >> n;
4vector<pair<
int,
int>> v(n);
5for (int i = 0; i < n; i++)
6 cin >> v[i].first >> v[i].second;
7
8// сортируем по правому концу
9sort(v.begin(), v.end(), [](auto a, auto b) {
10 return a.second < b.second;
11});
12
13int ans = 0, last = -1;
14for (auto [l, r] : v) {
15 if (l > last) {
16 ans++;
17 last = r;
18 }
19}
20cout << ans;
стр 9–11 — сортировка с лямбдой. [](auto a, auto b){...} — анонимная функция-компаратор.
стр 13 — last = -1 потому что любое начало l ≥ 0 будет больше -1.
стр 14 — auto [l, r] — распаковка пары сразу в две переменные (C++17).
1# n встреч, каждая задана парой (l, r)
2n = int(input())
3v = []
4for _ in range(n):
5 l, r = map(int, input().split())
6 v.append((l, r))
7
8# сортируем по правому концу
9v.sort(key=lambda x: x[1])
10
11ans = 0
12last = -1
13for l, r in v:
14 if l > last:
15 ans += 1
16 last = r
17
18print(ans)
стр 9 — key=lambda x: x[1] говорит sort'у, что сравнивать пары надо по второму элементу (правому концу).
стр 13 — for l, r in v — распаковка пары прямо в цикле.
стр 14 — last = -1 работает так же как в C++: любое начало больше -1, поэтому первая встреча возьмётся.
5Доказательство: почему это правильно
Мало уметь написать жадный алгоритм — надо понимать, почему он даёт ответ не хуже оптимального. Доказываем через обмен.
Пусть есть какое-то оптимальное решение (с максимумом встреч). Обозначим в нём первую встречу как X (самую раннюю по времени начала). А в нашем жадном — первую встречу G.
По нашему правилу G — это встреча с самым ранним правым концом во всём списке. Значит, правый конец G не позже правого конца X.
Если заменить в оптимальном решении X на G — количество встреч не уменьшится (мы же ничего не удалили, только заменили одну встречу на другую). А все встречи после X начинаются позже правого конца X — значит, они тем более позже правого конца G, и не пересекаются с G. Замена законна.
Дальше рассуждаем так же для второй выбранной встречи, третьей и так далее. В итоге получаем, что жадный выбор всегда можно сделать частью какого-то оптимального решения. Значит, жадный даёт оптимум.
Этот приём называется «аргумент обмена». Его идея всегда одна: показать, что жадный выбор можно подставить в оптимальное решение без ухудшения. Если можно — жадный работает.
6Вторая задача: книги на полке
Другой тип жадности. На полке длины W хотим разместить как можно больше книг. Каждая книга — прямоугольник a×b, её можно поставить либо стороной a, либо стороной b вдоль полки.
Стратегия в двух шагах:
Шаг 1. Выбор ориентации
Для каждой книги смотрим обе её стороны — и берём меньшую. Чем меньше книга занимает места, тем больше книг поместится. Значит, всегда выгодно поставить книгу «на ребро».
Шаг 2. Жадная укладка
Сортируем получившиеся ширины по возрастанию. Берём книги по одной, пока суммарная ширина не превысит W. Каждая добавленная книга — +1 к ответу.
Почему берём самые маленькие первыми? Пусть в нашем решении есть книга шириной 5, а какую-то книгу шириной 3 мы не взяли. Заменим 5 на 3 — общая длина уменьшится на 2 см, количество книг не изменилось. Значит, взять маленькую вместо большой никогда не хуже. Тот самый обмен.
Показать код (C++ / Python)
1int n, W;
2cin >> n >> W;
3vector<int> w(n);
4for (int i = 0; i < n; i++) {
5 int a, b;
6 cin >> a >> b;
7 w[i] = min(a, b); // берём меньшую сторону
8}
9
10sort(w.begin(), w.end()); // по возрастанию
11
12int ans = 0, sum = 0;
13for (int x : w) {
14 if (sum + x <= W) {
15 sum += x;
16 ans++;
17 } else {
18 break; // дальше только хуже
19 }
20}
21cout << ans;
1n, W = map(int, input().split())
2w = []
3for _ in range(n):
4 a, b = map(int, input().split())
5 w.append(min(a, b)) # берём меньшую сторону
6
7w.sort() # по возрастанию
8
9ans = 0
10s = 0
11for x in w:
12 if s + x <= W:
13 s += x
14 ans += 1
15 else:
16 break # дальше только хуже
17
18print(ans)
7Как узнать «жадную» задачу в условии
Опытный взгляд распознаёт жадность по признакам. Вот типовые:
- «Максимум / минимум X» — количество встреч, объектов, операций.
- «Нельзя одновременно / нельзя пересекаться» — намёк на сортировку по концу.
- «Можно повернуть / выбрать вариант» — намёк на выбор лучшей стороны до сортировки.
- «Порядок не важен» — можно сортировать, как удобно.
Если заметил хотя бы один из признаков — первой гипотезой пробуй жадность. Если быстро нашёл контрпример — переходи к другим идеям (перебор, dp).
Что запомнить
Жадный алгоритм — это выбор лучшего локально на каждом шаге в надежде получить лучшее глобально. Работает не всегда, но когда работает — решение пишется за 15 минут. Типовой рецепт: отсортировать по правильному ключу, пройти один раз, делать «очевидный» выбор на каждом шаге. Правильность доказывается через обмен: если в оптимальном решении заменить «не-жадный» выбор на наш — ответ не ухудшится. Два паттерна этого занятия: сортировка отрезков по правому концу (задача про встречи) и выбор меньшей стороны + сортировка по возрастанию (задача про книги).
На следующем занятии: жадность с выбором варианта — разбираем задачу про книги более подробно, плюс задачи с Codeforces.