Где применяется
1. Задача
Многие задачи планирования и задачи на графах решаются так: на каждом шаге берёшь вариант, который сейчас выглядит лучше всех. Это и есть жадный подход. Ему всегда нужно обоснование: почему выбор, лучший на одном шаге, не испортит весь ответ.
Кассир в американском магазине должен тебе 40 центов сдачи. Монеты там бывают по 25, 10, 5 и 1 центу. Кассир не отсчитывает сорок монеток по одному центу. Он берёт 25, потом 10, потом 5, и готово: три монеты. Никто не учил его алгоритму. Он раз за разом берёт самую крупную монету, которая ещё не превышает остаток, пока сдача не набрана.
Тебе нужно то же самое в коде. Есть номиналы монет, которые лежат в автомате, и сумма к выдаче. Выдай её наименьшим числом монет. Банкомат решает эту задачу каждый раз, когда отсчитывает купюры. Торговый автомат решает её, когда выдаёт сдачу.
Правило «бери самую крупную» почти всегда даёт лучший ответ. В этом уроке ты узнаешь, на каких наборах монет оно работает и на каких ошибается.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитminCoinsGreedy([1, 5, 2, 10], 18)Нужно набрать 18 как можно меньшим числом монет. Жадное правило: всегда брать самую крупную монету, которая ещё помещается.
Столбики: когда заканчивается каждая встреча, в порядке их начала.
Одна операция: одна проверка встречи или одно сравнение при сортировке. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(2ⁿ·n)O(n log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- наименьшее число монет или частей на сумму
- берём самую крупную, что ещё помещается
- выдать сдачу номиналами
- доказать оптимальность обменным аргументом
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
- Бэктрекинг (Backtracking)
Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
- Бинарный поиск по ответу (Binary search on the answer)
Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.
O(n log n), если вход сначала нужно отсортировать. Проход после сортировки это один цикл, O(n).
На LeetCode
Задачи, где одно простое правило, например сначала самое большое или сначала самое маленькое, даёт лучший ответ. Прежде чем доверять правилу, проверь аргумент обмена и покажи, что замена его выбора на любой другой никогда не улучшает ответ. Сама Coin Change эту проверку не проходит, она будет в уроке 112.
Сдачу с 20 давай десяткой и пятёркой раньше, чем тремя пятёрками, как в уроке, сначала крупная монета, ведь сдать с 10 можно только пятёрками.
Отсортируй оба списка и давай каждому ребёнку самое маленькое подходящее печенье. Печенье побольше на его месте только помешает следующему ребёнку.
Отсортируй цены по убыванию и бери каждую третью конфету бесплатно, тогда каждая бесплатная настолько дорогая, насколько позволяют правила.
Отсортируй людей, сажай самого тяжёлого с самым лёгким, если они помещаются, а если нет, отправляй самого тяжёлого одного.