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

Жадный алгоритм (Greedy Algorithm)

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

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

Основные характеристики жадных алгоритмов

Локальная оптимизация — на каждом шаге выбирается лучший вариант из доступных:

// На каждом шаге берём максимальное значение, которое можно взять
public int greedyMaxSum(int[] arr) {
    int sum = 0;
    for (int num : arr) {
        sum += num; // Берём всё, что есть
    }
    return sum;
}

Отсутствие пересмотра — выбранное решение не изменяется на следующих шагах.

Быстрота — обычно O(n log n) или O(n), в отличие от динамического программирования.

Классический пример: Задача о разборе монет

Дано количество денег и номиналы монет. Нужно набрать сумму, использовав минимальное количество монет.

public class CoinChangeGreedy {
    
    // Жадный подход: берём максимальные номиналы первыми
    public static int minCoinsGreedy(int amount, int[] coins) {
        // Предполагаем, что coins отсортированы по убыванию
        int count = 0;
        
        for (int coin : coins) {
            count += amount / coin; // Берём столько монет этого номинала, сколько можем
            amount = amount % coin; // Остаток
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        int[] coins = {50, 25, 10, 5, 1}; // Номиналы в убывающем порядке
        
        System.out.println(minCoinsGreedy(41, coins)); // Выведет 3
        // 41 = 25 + 10 + 5 + 1 (но жадный даст 4, не 3!)
    }
}

Проблема: жадный алгоритм не всегда даёт оптимальное решение. Для 41 с номиналами [50, 25, 10, 5, 1] жадный алгоритм даст 4 монеты (25 + 10 + 5 + 1), но оптимально — 3 монеты (25 + 10 + 5 + 1).

Для некоторых систем монет жадный алгоритм работает (например, европейские деньги), а для других — нет.

Задача о рюкзаке (0/1 Knapsack)

У вас есть рюкзак с ограничением по весу и предметы с весом и стоимостью. Нужно максимизировать стоимость.

public class KnapsackGreedy {
    
    static class Item implements Comparable<Item> {
        int weight;
        int value;
        double ratio; // Соотношение стоимость/вес
        
        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
            this.ratio = (double) value / weight;
        }
        
        @Override
        public int compareTo(Item other) {
            // Сортируем по ratio в убывающем порядке
            return Double.compare(other.ratio, this.ratio);
        }
    }
    
    // Жадный подход: берём предметы с максимальным соотношением стоимость/вес
    public static double fractionalKnapsack(Item[] items, int capacity) {
        java.util.Arrays.sort(items);
        
        double totalValue = 0;
        int remainingCapacity = capacity;
        
        for (Item item : items) {
            if (remainingCapacity >= item.weight) {
                // Берём весь предмет
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
                // Берём часть предмета (допускается для дробного рюкзака)
                totalValue += item.ratio * remainingCapacity;
                remainingCapacity = 0;
                break;
            }
        }
        
        return totalValue;
    }
    
    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        
        System.out.println(fractionalKnapsack(items, 50)); // Неоптимально для 0/1
    }
}

Замечание: для задачи о дробном рюкзаке жадный алгоритм оптимален, но для 0/1 рюкзака — нет. Для 0/1 нужно динамическое программирование.

Задача об активностях (Activity Selection)

Дано множество активностей с началом и концом. Выбрать максимальное количество неперекрывающихся активностей.

import java.util.Arrays;

public class ActivitySelection {
    
    static class Activity implements Comparable<Activity> {
        int start;
        int end;
        
        Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
        
        @Override
        public int compareTo(Activity other) {
            // Сортируем по времени окончания
            return Integer.compare(this.end, other.end);
        }
    }
    
    // Жадный подход: выбираем активности, заканчивающиеся раньше всего
    public static int maxActivities(Activity[] activities) {
        Arrays.sort(activities);
        
        int count = 1;
        int lastEnd = activities[0].end;
        
        for (int i = 1; i < activities.length; i++) {
            // Если текущая активность начинается после предыдущей
            if (activities[i].start >= lastEnd) {
                count++;
                lastEnd = activities[i].end;
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 2),
            new Activity(3, 4),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(8, 9),
            new Activity(5, 8)
        };
        
        System.out.println(maxActivities(activities)); // Выведет 4
    }
}

Это работает оптимально потому что выбор активности, которая заканчивается раньше, оставляет больше времени для других.

Задача о расписании (Job Sequencing)

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

import java.util.Arrays;

public class JobSequencing {
    
    static class Job implements Comparable<Job> {
        String id;
        int deadline;
        int profit;
        
        Job(String id, int deadline, int profit) {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
        
        @Override
        public int compareTo(Job other) {
            // Сортируем по прибыли в убывающем порядке
            return Integer.compare(other.profit, this.profit);
        }
    }
    
    // Жадный подход: выбираем работы с максимальной прибылью
    public static int maxProfit(Job[] jobs) {
        Arrays.sort(jobs);
        
        // Находим максимальный дедлайн
        int maxDeadline = 0;
        for (Job job : jobs) {
            maxDeadline = Math.max(maxDeadline, job.deadline);
        }
        
        // Массив для отслеживания, какие слоты заняты
        boolean[] slots = new boolean[maxDeadline + 1];
        int totalProfit = 0;
        
        for (Job job : jobs) {
            // Пытаемся найти слот до дедлайна
            for (int i = job.deadline; i > 0; i--) {
                if (!slots[i]) {
                    slots[i] = true;
                    totalProfit += job.profit;
                    break;
                }
            }
        }
        
        return totalProfit;
    }
    
    public static void main(String[] args) {
        Job[] jobs = {
            new Job("a", 2, 100),
            new Job("b", 1, 50),
            new Job("c", 2, 10),
            new Job("d", 1, 20),
            new Job("e", 3, 30)
        };
        
        System.out.println(maxProfit(jobs)); // Оптимальная прибыль
    }
}

Когда использовать жадные алгоритмы

Хорошо подходят:

• Задача об активностях
• Задача о монетах (для некоторых систем)
• Задача о расписании
• Дерево Хаффмана (кодирование)
• Алгоритм Крускала (минимальное остовное дерево)
• Задача о дробном рюкзаке

Не подходят:

• 0/1 Knapsack (нужно динамическое программирование)
• Поиск кратчайшего пути во взвешенном графе (используй Dijkstra)
• Раскраска графа

Преимущества и недостатки

Преимущества:

• Быстрые и эффективные (O(n log n) обычно)
• Простые в реализации
• Требуют мало памяти

Недостатки:

• Не всегда дают оптимальное решение
• Требуют доказательства оптимальности для каждой задачи
• Выбор правильного "жадного критерия" критичен

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