Жадные алгоритмы

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

Сложность: часто O(n log n) из-за сортировки. Память: O(1)–O(n). Примеры: разбиение на монеты в каноничных системах, код Хаффмана, задача о покрытии интервалами.

# Минимум монет для канонической системы
def greedy_change(amount, coins=(50, 20, 10, 5, 1)):
    result = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            result.append(c)
    return result

print(greedy_change(83))  # [50, 20, 10, 1, 1, 1]