Жадный алгоритм строит решение шаг за шагом: на каждом шаге берёт лучший на вид вариант и больше его не меняет. Нет ни поиска, ни возвратов, поэтому время обычно O(n log n) (сортировка) или O(n). Цена за это: алгоритм верен только для некоторых задач.

Когда жадность работает

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

Размен монет

Жадный алгоритм набирает 6 как 4+1+1, оптимум — 3+3
Жадный алгоритм набирает 6 как 4+1+1, оптимум — 3+3
python
from itertools import combinations_with_replacement

def greedy_coins(coins, amount):
    result = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

def optimal_coins(coins, amount):
    for k in range(1, amount + 1):
        for combo in combinations_with_replacement(coins, k):
            if sum(combo) == amount:
                return list(combo)

print(greedy_coins([1, 5, 10, 25], 63))
print(greedy_coins([1, 3, 4], 6), optimal_coins([1, 3, 4], 6))

С монетами 1, 5, 10, 25 жадность всегда оптимальна. С монетами 1, 3, 4 и суммой 6 она берёт 4 + 1 + 1 (3 монеты), а оптимум 3 + 3 (2 монеты). Ответ допустимый, но не оптимальный.

Выбор заявок