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

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

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

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

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

• Задача о сдаче (размен монет)
• Задача о выборе заявок (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. Решение: 3 монеты 25р (неполноценный размен)

В данном случае最优解可能存在, но жадный алгоритм его не находит.

Жадные алгоритмы работают корректно только для жадных задач, обладающих свойствами:

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

# Пример жадного подхода к задаче о сдаче
def greedy_change(amount, coins):
    result = {}
    sorted_coins = sorted(coins, reverse=True) # Сортируем монеты по убыванию
    remaining_amount = amount

    for coin in sorted_coins:
        count = remaining_amount // coin # Сколько монет данного номинала можно взять
        if count > 0:
            result[coin] = count
            remaining_amount -= count * coin # Уменьшаем остаток

    return result, remaining_amount

# Пример использования
amount = 100
coins = [50, 10, 5, 1]
change, remaining = greedy_change(amount, coins)
print(f"Для суммы {amount} с монетами {coins}: Сдача = {change}, Остаток = {remaining}")

amount_bad = 82
coins_bad = [50, 25, 10] # Пример, где жадный алгоритм может не сработать
change_bad, remaining_bad = greedy_change(amount_bad, coins_bad)
print(f"Для суммы {amount_bad} с монетами {coins_bad}: Сдача = {change_bad}, Остаток = {remaining_bad}")