Greedy Algorithms in Competitive Programming

What are Greedy Algorithms?

Greedy algorithms are a class of algorithms that make the locally optimal choice at each stage with the hope of finding the global optimum. In other words, they always choose the option that looks best *at the moment*. They don't look ahead or consider past choices. This "greed" for immediate gain can lead to efficient solutions for some problems, but it's crucial to understand that it doesn't guarantee an optimal solution for all problems. The key is to identify problems where the greedy strategy will consistently lead to the best overall result.

Introduction to Greedy Algorithms

When to Use Greedy Algorithms

Greedy algorithms are well-suited for optimization problems where the following conditions are met:

• Optimal Substructure: The optimal solution to the problem contains optimal solutions to subproblems. This means that if you make the optimal choice at each step, you'll eventually reach the overall optimal solution.
• Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice. This means that the locally optimal choice you make at each step should be part of some globally optimal solution.

However, it's important to note when *not* to use greedy algorithms:

• No Guarantee of Optimality: If the optimal substructure or greedy choice property doesn't hold, a greedy algorithm may produce a suboptimal solution. Dynamic programming or other more sophisticated techniques may be necessary.
• Negative Weights/Cycles (in some graph problems): Greedy algorithms like Dijkstra's algorithm don't work correctly with negative edge weights.

Proof of Correctness Techniques

Showing that a greedy algorithm is correct can be tricky. Here are some common proof techniques:

• Induction: Prove that after each step of the greedy algorithm, the partial solution constructed so far is a part of an optimal solution.
• Exchange Argument: Start with any arbitrary optimal solution and show that you can gradually transform it into the solution produced by the greedy algorithm *without* worsening the objective function value. This demonstrates that the greedy solution is at least as good as any other optimal solution.
• Greedy Stays Ahead: Show that at each step, the greedy algorithm's partial solution is "better" than any other possible partial solution. This might involve comparing the number of items selected, the total value achieved, etc.

Solving Classic Greedy Problems

1. Activity Selection Problem

Problem: Given a set of activities with start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can only work on one activity at a time. Activities are sorted by finish time.

Greedy Strategy: Always choose the activity with the earliest finish time that doesn't overlap with previously selected activities.

Java Solution:

 import java.util.Arrays;

class Activity {
    int start, finish;

    public Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {
    public static int activitySelection(Activity[] activities) {
        Arrays.sort(activities, (a, b) -> a.finish - b.finish); // Sort by finish time

        int count = 1;
        int lastFinishTime = activities[0].finish;

        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastFinishTime) {
                count++;
                lastFinishTime = activities[i].finish;
            }
        }
        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, 9)
        };

        int maxActivities = activitySelection(activities);
        System.out.println("Maximum number of activities that can be performed: " + maxActivities);
    }
} 

2. Fractional Knapsack Problem

Problem: Given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, determine the fraction of each item to put in the knapsack to maximize the total value without exceeding the knapsack's capacity. You can take fractions of items.

Greedy Strategy: Calculate the value-to-weight ratio for each item. Sort the items by this ratio in descending order. Take as much as possible of the item with the highest ratio, then move to the next item, and so on, until the knapsack is full.

Java Solution:

 import java.util.Arrays;

class Item {
    int weight, value;
    double ratio;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.ratio = (double) value / weight;
    }
}

public class FractionalKnapsack {
    public static double fractionalKnapsack(int capacity, Item[] items) {
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio, a.ratio)); // Sort by value-to-weight ratio descending

        double totalValue = 0;
        for (Item item : items) {
            if (capacity >= item.weight) {
                totalValue += item.value;
                capacity -= item.weight;
            } else {
                totalValue += item.ratio * capacity;
                capacity = 0;
                break;
            }
        }
        return totalValue;
    }

    public static void main(String[] args) {
        int capacity = 50;
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };

        double maxValue = fractionalKnapsack(capacity, items);
        System.out.println("Maximum value that can be obtained: " + maxValue);
    }
} 

3. Minimum Number of Coins

Problem: Given a set of coin denominations and a target amount, find the minimum number of coins required to make up that amount. Assume an infinite supply of each coin denomination.

Greedy Strategy: Start with the largest denomination coin and use as many as possible without exceeding the target amount. Then, move to the next largest denomination and repeat the process until the target amount is reached.

Java Solution:

 import java.util.Arrays;

public class MinimumCoins {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // Sort coins in ascending order
        int numCoins = 0;

        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                numCoins++;
            }
            if (amount == 0) break;
        }

        if (amount != 0) {
            return -1; // Indicate that the amount cannot be made with the given coins
        }

        return numCoins;
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
        int amount = 93;

        int minCoins = minCoins(coins, amount);

        if (minCoins != -1) {
            System.out.println("Minimum number of coins required: " + minCoins);
        } else {
            System.out.println("Cannot make the amount with the given coins.");
        }
    }
}