Жадные алгоритмы — когда «на сейчас» лучше, чем «на потом»

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

Они не откатываются, не пробуют другие ветки — просто берут то, что сейчас выгодно.
📌 Это как если бы ты всегда выбирал самый дешёвый товар, не задумываясь о возможных акциях в будущем.
---

🧠 Как работает жадный подход​

Алгоритм:
1. Выбирает из доступных наиболее выгодный по критерию элемент
2. Фиксирует это решение
3. Повторяет, пока не достигнет конца задачи

📌 Главное — локальный выбор + необходимое условие: жадность должна вести к глобальному оптимуму
---

✅ Классический пример: сдача монетами​


У тебя есть монеты номиналом 1, 3, 4. Нужно выдать сумму 6, используя минимум монет.
Нажмите, чтобы раскрыть...
Жадный алгоритм:
  • берёт по максимуму из крупных: 4
  • остаётся 2 → берёт два по 1
⛔ Получилось: 4 + 1 + 1 = 3 монеты
Но оптимально: 3 + 3 = 2 монеты
→ жадность здесь не сработала

---

🧮 Где жадность работает отлично​


✅ Задача о рюкзаке (дробная версия): выбираем по максимальной ценности/весу
✅ Задача о покрытии множества (Set Cover): всегда берём подмножество, покрывающее больше всего новых элементов
✅ Выбор совместимых отрезков по времени (интервалы): сортируем по окончанию, выбираем без пересечений

---

🐍 Пример: выбор непересекающихся отрезков на Python​


Python: 
intervals = [(1, 3), (2, 5), (4, 6), (7, 9)]
intervals.sort(key=lambda x: x[1])  # сортировка по правому краю

res = []
end = 0

for start, finish in intervals:
    if start >= end:
        res.append((start, finish))
        end = finish

print("Выбранные интервалы:", res)

🟢 Вывод:
Код: 
Выбранные интервалы: [(1, 3), (4, 6), (7, 9)]

---

💻 То же самое на C​


C: 
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start, end;
} Interval;

int cmp(const void* a, const void* b) {
    return ((Interval*)a)->end - ((Interval*)b)->end;
}

int main() {
    Interval intervals[] = {{1,3},{2,5},{4,6},{7,9}};
    int n = sizeof(intervals)/sizeof(intervals[0]);
    qsort(intervals, n, sizeof(Interval), cmp);

    int end = 0;
    for (int i = 0; i < n; i++) {
        if (intervals[i].start >= end) {
            printf("(%d, %d)\n", intervals[i].start, intervals[i].end);
            end = intervals[i].end;
        }
    }
    return 0;
}
---

📎 Вывод​

Жадные алгоритмы — это "алгоритмический инстинкт".
Они хороши, когда каждое локальное решение приближает к глобальной цели.
Но они не всегда универсальны — будь внимателен: там, где жадность не гарантирует оптимум, лучше использовать динамику или полный перебор.

💬 А ты сталкивался с задачами, где жадный подход подводил? Пиши ниже!