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

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

• Задача о сдаче: Выдать минимальное количество монет для определенной суммы. Жадный алгоритм выбирает самую крупную монету, которая не превышает оставшуюся сумму.
• Алгоритм Дейкстры: Находит кратчайшие пути от одной вершины графа до всех остальных с неотрицательными весами ребер. На каждом шаге выбирает вершину с наименьшим текущим расстоянием.

Жадные алгоритмы не всегда дают оптимальное решение для всех задач, но во многих случаях они просты в реализации и эффективны по времени. Для доказательства оптимальности жадного алгоритма обычно используются два свойства:

1. Свойство жадного выбора: Локально оптимальный выбор, сделанный жадным алгоритмом, может быть частью оптимального решения.
2. Свойство оптимальной подструктуры: Оптимальное решение задачи содержит оптимальные решения подзадач.

# Пример жадного алгоритма для задачи о сдаче
def find_change(amount, coins):
    # assumes coins are sorted in descending order
    change = []
    for coin in coins:
        while amount >= coin:
            change.append(coin)
            amount -= coin
    return change

# Пример использования
# print(find_change(67, [25, 10, 5, 1])) # [25, 25, 10, 5, 1, 1]