Жадный алгоритм (обменный аргумент)

Жадный алгоритм (обменный аргумент): как это работает?

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

Отсортируйте вход так, чтобы этот вариант был впереди. Сортировка и есть основная работа.

Пройдите список один раз и берите всё, что подходит. Не оглядывайтесь на уже сделанный выбор.

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

Доказывают это обменом: возьмите любой оптимальный ответ и подставьте свой выбор. Если он остался оптимальным, жадность безопасна.

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

Источники: Википедия: Жадный алгоритм

1. по концу: [1,3], [2,4], [3,5]Бронируем встречи. Впереди та, что кончается раньше.
2. берём [1, 3]Она кончается раньше всех и оставляет больше места.
3. пропускаем [2, 4]Она начинается в 2, до конца предыдущей.
4. берём [3, 5]Она начинается ровно тогда, когда комната освободилась.
5. ответ = 2Помещаются две встречи. Сортировка по длине могла бы потерять одну.

function minCoinsGreedy(coins, amount) {
    const sorted = [...coins].sort((a, b) => b - a);
    const used = [];
    for (const coin of sorted) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
        }
    }
    return amount === 0 ? used : null;
}

function minCoinsGreedy(coins: number[], amount: number): number[] | null {
    const sorted = [...coins].sort((a, b) => b - a);
    const used: number[] = [];
    for (const coin of sorted) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
        }
    }
    return amount === 0 ? used : null;
}

def min_coins_greedy(coins, amount):
    used = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            used.append(coin)
    return used if amount == 0 else None

function minCoinsGreedy(array $coins, int $amount): ?array {
    rsort($coins);
    $used = [];
    foreach ($coins as $coin) {
        while ($amount >= $coin) {
            $amount -= $coin;
            $used[] = $coin;
        }
    }
    return $amount === 0 ? $used : null;
}

    public static List<Integer> minCoinsGreedy(int[] coins, int amount) {
        int[] sorted = coins.clone();
        Arrays.sort(sorted); // ascending, so walk it backwards for the biggest first
        List<Integer> used = new ArrayList<>();
        for (int i = sorted.length - 1; i >= 0; i--) {
            int coin = sorted[i];
            while (amount >= coin) {
                amount -= coin;
                used.add(coin);
            }
        }
        return amount == 0 ? used : null;
    }

    public static List<int> MinCoinsGreedy(int[] coins, int amount) {
        var sorted = (int[]) coins.Clone();
        Array.Sort(sorted);
        Array.Reverse(sorted); // biggest coin first
        var used = new List<int>();
        foreach (int coin in sorted) {
            while (amount >= coin) {
                amount -= coin;
                used.Add(coin);
            }
        }
        return amount == 0 ? used : null;
    }

Жадный алгоритм (обменный аргумент): разбор примера

Наименьшее число стрел для шаров

Шары занимают горизонтальные отрезки. Стрела, выпущенная в точке x, лопает все шары, накрывающие x.

Верните наименьшее число стрел, лопающих все шары.

Отсортируйте шары по правому краю.

Стреляйте в первый правый край и пропускайте все накрытые шары. Потом стреляйте в следующий не накрытый край.

function findMinArrowShots(points) {
    points.sort((a, b) => a[1] - b[1]); // by right edge, never by left

    let arrows = 1;
    let shot = points[0][1]; // the earliest right edge

    for (const [start, end] of points) {
        if (start > shot) {
            arrows++;
            shot = end; // this balloon is out of reach of the last arrow
        }
    }

    return arrows;
}

Жадный алгоритм (обменный аргумент): когда применять?

Паттерн «Жадный алгоритм (обменный аргумент)» нужен, когда в условии есть слова «наименьшее число монет или частей на сумму», «берём самую крупную, что ещё помещается» или «выдать сдачу номиналами». Решение на нём обычно укладывается в O(n log n).

• •наименьшее число монет или частей на сумму
• •берём самую крупную, что ещё помещается
• •выдать сдачу номиналами
• •доказать оптимальность обменным аргументом

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Жадный алгоритм (обменный аргумент): с чем путают?

Паттерн «Жадный алгоритм (обменный аргумент)» чаще всего путают с этими паттернами: Динамическое программирование (1-D), Бэктрекинг, Сортировка с пользовательским компаратором и Бинарный поиск по ответу.

• Динамическое программирование (1-D) (Dynamic programming (1-D)): Динамика держит все варианты открытыми до конца. Жадность выбирает сразу и не может откатиться.
• Бэктрекинг (Backtracking): Бэктрекинг пробует все варианты и оставляет лучший. Жадность пробует один и ему верит.
• Сортировка с пользовательским компаратором (Sort with a custom comparator): Большинство жадных решений начинается с сортировки. В компараторе и записан сам выбор.
• Бинарный поиск по ответу (Binary search on the answer): Там сама проверка часто жадная. Поиск лишь выбирает значение для проверки.

Жадный алгоритм (обменный аргумент): частые ошибки

• Пропускают доказательство

  Жадное правило, звучащее верно, очень часто неверно. Сначала поищите контрпример.

• Сортируют не по тому ключу

  Ранний старт и ранний конец дают разные ответы. Ключ выбирает доказательство, а не интуиция.

• Берут жадность там, где выборы связаны

  Размен монет со странными номиналами её ломает. Там безопасен только динамический подход.

• Пытаются отменить выбор

  Как только жадность что-то забирает назад, это уже перебор. Пишите бэктрекинг или динамику.

Жадный алгоритм (обменный аргумент): задачи с собеседований

Паттерн «Жадный алгоритм (обменный аргумент)» решает такие задачи с собеседований: Непересекающиеся интервалы, Наименьшее число стрел, Прыжки по массиву, Заправки по кругу, Планировщик задач, Разбиение строки на части и Раздача печенья.

• Непересекающиеся интервалы: Оставляйте тот интервал, что кончается раньше.
• Наименьшее число стрел: По одной стреле на группу пересечений.
• Прыжки по массиву: Следите за самым дальним достижимым индексом.
• Заправки по кругу: Начинайте заново там, где бак ушёл в минус.
• Планировщик задач: В каждом раунде ставьте самую частую задачу.
• Разбиение строки на части: Режьте, как только все встреченные буквы закончились.
• Раздача печенья: Давайте ребёнку наименьшее подходящее печенье.

Жадный алгоритм (обменный аргумент): сложность по времени и памяти

У паттерна «Жадный алгоритм (обменный аргумент)» целевая сложность O(n log n).

O(n log n), если вход сначала нужно отсортировать. Проход после сортировки это один цикл, O(n).