алгоритмы · справочникжадные алгоритмы
SilverTests.ru · УчебникЖадность с выбором варианта
Жадность: выбери вариант
Когда у каждого объекта есть несколько «форм» — сначала выбери выгодную, потом сортируй
🎯 Чему научимся
На прошлом занятии была жадность с сортировкой по правому концу. Теперь — другой паттерн: каждый объект можно «повернуть» или выбрать из нескольких вариантов, и первым шагом нужно решить, какой вариант взять. Разберём задачу про книги на полке и задачу про размен купюр.
1Напоминание: что такое жадность
На каждом шаге делаем локально-оптимальный выбор: что лучше прямо сейчас. Работает не всегда, но когда работает — решение простое и быстрое. Главный вопрос всегда один: каков правильный критерий «лучше»?
Сегодняшний паттерн: прежде чем сортировать объекты, надо их «подготовить» — для каждого выбрать наиболее выгодную форму. Только после подготовки начинается собственно жадный проход.
2Задача: книги на полке
На полке длины W нужно разместить как можно больше книг. Каждая книга — прямоугольник a×b. Книгу можно ставить двумя способами: либо одной стороной к соседней книге, либо другой. То есть она занимает вдоль полки либо a см, либо b см — на выбор.
Сколько максимум книг поместится?
У нас есть два независимых решения для каждой книги: какой стороной её ставить. И одно глобальное: какие книги вообще брать. Казалось бы, вариантов огромное количество — 2n способов выбрать ориентации умножить на 2n способов выбрать подмножество книг. Но жадность решает задачу за O(n log n).
Поиграй с алгоритмом
Полка длиной —. Книги ниже — случайные, у каждой две стороны.
Нажми кнопку, чтобы запустить алгоритм. Три варианта жадности — видно, какой находит больше книг.
Зелёным — взятые книги на полке. Красным — не уместилась. Жёлтым внизу — «на руках», ещё не рассмотренные. У каждой книги две цифры — её стороны, подчёркнута та, которой она ставится.
3Разбор трёх вариантов
В визуализаторе три кнопки — это три всё более умные стратегии. Давай поймём, что делает каждая.
Брать первой стороной. Простейшее: каждую книгу кладём так, как она записана, в том порядке, как дана. Если не помещается — выбрасываем. Ясно, что это не оптимально: мы игнорируем и возможность повернуть, и возможность взять сначала другую книгу.
Брать меньшую сторону. Уже лучше: для каждой книги выбираем, какой стороной ставить — min(a, b). Книга занимает минимум места. Но порядок такой же, как во входе. Если сначала пришла большая книга — она займёт всю полку, а маленькие не влезут.
Меньшую сторону + сортировать. Берём min(a, b), потом сортируем по возрастанию, потом жадно укладываем. Это и есть полный алгоритм. Он всегда находит максимум.
4Два шага алгоритма
Шаг 1. Выбор ориентации
Для каждой книги с размерами a и b берём w = min(a, b). Идея: нам нужно максимум количество книг. Значит, каждую хотим занять меньше места. «На ребро» всегда выгоднее, чем «плашмя».
Шаг 2. Жадная укладка
Сортируем ширины по возрастанию. Проходим и добавляем каждую книгу, пока суммарная ширина не превысит W. Добавили — +1 к ответу. Не смогли — можно прерваться, дальше все книги больше и тем более не влезут.
Показать код (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); // шаг 1: меньшая сторона
8}
9
10sort(w.begin(), w.end()); // шаг 2: сортировка
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;
стр 7 — min(a, b) — сразу меньшая из двух сторон.
стр 10 — sort без компаратора — по возрастанию.
стр 18 — после сортировки следующая книга ≥ текущей, так что можно остановиться, не проверяя остальные.
1n, W = map(int, input().split())
2w = []
3for _ in range(n):
4 a, b = map(int, input().split())
5 w.append(min(a, b)) # шаг 1: меньшая сторона
6
7w.sort() # шаг 2: сортировка
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)
5Почему оба шага нужны
Легко подумать: «ну возьмём min, поставим книги по возрастанию — очевидно же». Но на муниципале эту задачу пропускают именно потому, что один из двух шагов кажется лишним. Разбираем, почему нельзя без каждого.
Без шага 1 (без выбора ориентации). Представь книгу 2×100. Если поставить её стороной 100 — она займёт всю полку. Если стороной 2 — только 2 см. Разница огромная. Если не выбирать, просто брать первую сторону — ответ будет гораздо хуже.
Без шага 2 (без сортировки). Пусть книги 10, 1, 1, 1, 1 и полка 10. Если брать в таком порядке, влезет только первая (10=10). Ответ 1. А если отсортировать по возрастанию: 1, 1, 1, 1, 10 — поместится 1+1+1+1=4, ответ 4. В четыре раза лучше!
Ни один из шагов нельзя убрать. Они работают вместе.
6Доказательство: почему сортировка по возрастанию
Та же техника обмена, что и на прошлом занятии. Предположим, что в оптимальном решении мы взяли книгу ширины X, но не взяли какую-то книгу ширины Y, где Y < X. Тогда можно заменить X на Y: количество книг не изменилось (-1 +1 = 0), а занятое место уменьшилось на X - Y > 0. Точно не хуже.
Значит, если есть возможность заменить большую на меньшую — всегда имеет смысл это сделать. Это и оправдывает стратегию «сначала самые маленькие».
Заметь разницу с прошлым занятием. Там сортировали по правому концу — потому что нужно было поскорее «освободить» ось для следующих. Здесь сортируем по возрастанию ширины — потому что нужно каждую книгу занять меньше места. Ключ сортировки всегда зависит от того, что мы хотим максимизировать.
7Вторая задача: размен купюр
Другая задача того же класса. Нужно выдать сумму N рублей минимальным количеством купюр. Номиналы: 1, 5, 10, 20, 100. Какое минимальное число купюр нужно?
Здесь «объект» — это шаг выдачи. На каждом шаге выбираем номинал. Жадная стратегия: всегда выдавать максимальную купюру, которая не превышает остаток. Сначала пытаемся 100, потом 20, 10, 5 и только в конце 1.
Например, для N = 125: берём 100 (осталось 25), берём 20 (осталось 5), берём 5 (осталось 0). Итого 3 купюры.
Но внимание! Такая жадность работает не для любого набора номиналов. Для 1, 5, 10, 20, 100 работает. А вот для номиналов 1, 3, 4 и суммы 6: жадный возьмёт 4 + 1 + 1 = 3 купюры, а оптимально 3 + 3 = 2 купюры. Жадность ломается. Для «произвольных» номиналов задача решается только через динамическое программирование.
Показать код (C++ / Python)
1long long n;
2cin >> n;
3
4int bills[] = {100, 20, 10, 5, 1};
5long long ans = 0;
6
7for (int b : bills) {
8 ans += n / b; // сколько купюр номинала b можно взять
9 n %= b; // остаток
10}
11
12cout << ans;
стр 4 — номиналы по убыванию — начинаем с самой большой купюры.
стр 8 — n / b — это и есть «сколько раз подряд можно взять номинал b».
стр 9 — n %= b — оставляем то, что не разменялось; дальше пытаемся меньшим номиналом.
1n = int(input())
2
3bills = [100, 20, 10, 5, 1]
4ans = 0
5
6for b in bills:
7 ans += n // b # сколько купюр номинала b
8 n %= b # остаток
9
10print(ans)
стр 7 — в Python // — целочисленное деление. Обычное / дало бы дробь.
8Как узнать этот паттерн в условии
Признаки задачи на «жадность с выбором варианта»:
- «Можно поворачивать / выбирать сторону / ориентацию» — прямой намёк на шаг 1.
- «Есть ограничение по одной оси» (длина полки, вес, время) — и надо максимизировать число объектов.
- «Набор дискретных вариантов» — номиналы купюр, уровни, скорости. Всегда выбираем самый выгодный из доступных.
- «Максимум количества / минимум операций» при явно неупорядоченном входе — намёк, что нужна сортировка.
Если увидел «можно повернуть» — почти наверняка первый шаг это min(a, b). Если увидел «номиналы» или «шаги» — думай про выбор максимального варианта на каждом шаге (но проверь на контрпримере, что жадность для этих номиналов работает!).
Что запомнить
Второй паттерн жадности — выбор варианта + сортировка + жадный проход. Применяется, когда у каждого объекта есть несколько «форм» и нужно выбрать выгодную до того, как сортировать. В задаче про книги: для каждой книги w = min(a, b), потом сортируем по возрастанию, потом укладываем. В задаче про размен: на каждом шаге берём максимальный номинал, влезающий в остаток. Оба шага важны: без выбора варианта книги займут слишком много места, без сортировки первые большие книги забьют полку. Доказывается всё тем же обменом: если взяли что-то большое, а что-то маленькое не взяли — замена только улучшит ответ. Жадность с номиналами — аккуратно: работает не для любого набора, надо проверять на контрпримерах.
На следующем занятии: бинарный поиск и бинпоиск по ответу.