Что такое жадные алгоритмы?

Жадные алгоритмы — это разновидность алгоритмов, которые на каждом шаге принимают локально оптимальное решение в надежде, что это приведет к глобально оптимальному решению.

Ключевые особенности:

• Локальный оптимум: На каждом шаге выбирается решение, которое кажется наилучшим в данный момент, без учета будущих последствий.
• Отсутствие обратного хода: Принятые решения не могут быть пересмотрены на более поздних этапах.
• Эффективность: Часто просты в реализации и имеют較高的 эффективность по сравнению с более сложными методами.

Примеры задач, для которых подходят жадные алгоритмы:

• Задача о сдаче (размен монет)
• Задача о выборе заявок (Interval Scheduling)
• Некоторые задачи о минимальном остовном дереве (например, алгоритм Прима или Краскала)

Пример жадного подхода к задаче о сдаче (размен 100 рублей монетами 50, 10, 5, 1):

1. Взять максимально возможное количество монет 50 рублей (2 * 50 = 100).
2. Остаток: 0. Решение найдено.

Пример, когда жадный алгоритм не дает оптимального решения (размен 82 рублей монетами 50, 25, 10):

Жадный подход:

1. 1 * 50 = 50. Остаток: 32.
2. 1 * 25 = 25. Остаток: 7.
3. 0 * 10 = 0. Остаток: 7. Решение: 1 монета 50р, 1 монета 25р, 0 монет 10р (неполноценный размен)

Оптимальный подход:

1. 0 * 50 = 0. Остаток: 82.
2. 3 * 25 = 75. Остаток: 7.
3. 0 * 10 = 0. Остаток: 7. Решение: