Что такое жадный алгоритм? Объясните на простом примере
Встретил термин «жадный алгоритм» (greedy). Что это значит и когда он работает, а когда нет? Хочется понять на конкретном примере, а не на определении.
2 ответа
Жадный алгоритм — это когда на каждом шаге ты хватаешь то, что выглядит лучшим прямо сейчас, не думая о будущем.
Классика — размен монет. Надо выдать 87 рублей монетами 1, 2, 5, 10, 50. Жадно берёшь самую крупную, что влезает: 50, потом 10, 10, 10, 5, 2 — итого 6 монет. Для таких «нормальных» наборов монет это даёт оптимум.
coins = [50, 10, 5, 2, 1]
amount = 87
res = []
for c in coins:
while amount >= c:
res.append(c)
amount -= c
print(res) # [50, 10, 10, 10, 5, 2]
Важный нюанс: жадность работает НЕ всегда. Если монеты, например, [1, 3, 4] и надо набрать 6 — жадный возьмёт 4+1+1 (3 монеты), а оптимум 3+3 (2 монеты). Поэтому жадный алгоритм надо доказывать, иначе он может дать неоптимальный ответ.
Жадный = «бери лучшее сейчас и не оглядывайся». Быстро и просто, но оптимум гарантирует только для определённых задач (рюкзак дробный, Хаффман, Дейкстра). Для обычного рюкзака жадность ломается — там нужна динамика.
