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

Пример 1

def find_coin_change(coins, amount):
    """Жадный алгоритм для задачи о сдаче."""
    coins.sort(reverse=True)  # сортируем монеты от большей к меньшей
    change = []

    for coin in coins:
        while amount >= coin:   # пока монета "влезает" в остаток
            amount -= coin      # вычитаем её из суммы
            change.append(coin) # добавляем монету в ответ

    if amount == 0:
        return change
    else:
        return "Решение не найдено"

# Входные данные
coins = [1, 2, 5, 10, 25]
amount = 63

print(find_coin_change(coins, amount))
# Вывод: [25, 25, 10, 2, 1]

Пример 2

def activity_selection(activities):
    """
    activities: список кортежей (начало, конец)
    Возвращает максимальный набор непересекающихся мероприятий.
    """
    # Сортируем по времени окончания
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]  # берём первое (раньше всех заканчивается)
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:        # мероприятие начинается после конца предыдущего
            selected.append((start, end))
            last_end = end

    return selected

# Пример
activities = [(1, 4), (2, 6), (5, 8), (7, 9), (3, 5)]
print(activity_selection(activities))
# Вывод: [(1, 4), (5, 8)]

Пример 3

import heapq

def huffman_encoding(frequencies):
    """
    frequencies: словарь {символ: частота}
    Возвращает словарь {символ: код}
    """
    # Создаём кучу из пар (частота, символ)
    heap = [[freq, [symbol, ""]] for symbol, freq in frequencies.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        # Жадно берём два элемента с наименьшей частотой
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)

        # Левым детям добавляем "0", правым — "1"
        for pair in lo[1:]:
            pair[1] = "0" + pair[1]
        for pair in hi[1:]:
            pair[1] = "1" + pair[1]

        # Объединяем в новый узел
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return dict(heapq.heappop(heap)[1:])

# Пример
frequencies = {"a": 5, "b": 2, "c": 1}
codes = huffman_encoding(frequencies)
print(codes)
# Вывод (один из возможных вариантов): {'a': '0', 'b': '10', 'c': '11'}