Жадный алгоритм делает локально оптимальный выбор на каждом шаге, надеясь, что это приведёт к глобальному оптимуму. Он прост и быстр, но корректен только когда задача имеет свойство жадного выбора и оптимальную подструктуру.
Никогда не пересматривайте прошлые выборы — придерживайтесь лучшего немедленного варианта и двигайтесь дальше.
def greedy_coins(amount, coins=(25, 10, 5, 1)):
result = []
for coin in coins: # largest first
while amount >= coin:
amount -= coin # take as many as possible
result.append(coin)
return result
greedy_coins(36) # -> [25, 10, 1]
Это оптимально для американских монет, но не работает для наборов типа {1, 3, 4}, где жадный алгоритм дает 4+1+1 для 6 вместо 3+3.
Примеры, которые работают: Dijkstra, Kruskal/Prim (MST), кодирование Хаффмана, планирование интервалов.
Обычно быстро — часто O(n log n) после сортировки.
Жадный алгоритм не всегда корректен. Докажите свойство жадного выбора или протестируйте против baseline'а brute-force/DP перед использованием.
Когда жадный алгоритм применим, он намного проще и быстрее, чем DP или перебор.
Знание когда он верен — и когда он молча даёт неправильные ответы — это признак алгоритмической зрелости.
Много фундаментальных графовых алгоритмов основаны на жадности.