Greedy Algorithms Explained: Logic, Pitfalls & Real-World Patterns

import java.util.Arrays;

/**
 * Greedy coin change — works perfectly for canonical coin systems
 * (e.g., US coins: 25, 10, 5, 1) where larger denominations evenly
 * divide smaller ones. We'll also show WHY it breaks for non-canonical sets.
 */
public class CoinChangeGreedy {

    /**
     * Returns the minimum number of coins needed to make the target amount.
     * Uses the greedy approach: always pick the largest coin that fits.
     *
     * @param availableCoins  array of coin denominations (need not be sorted)
     * @param targetAmount    the amount we want to make change for
     * @return                minimum coin count, or -1 if exact change is impossible
     */
    public static int makeChange(int[] availableCoins, int targetAmount) {
        // Sort coins in descending order so we always try the largest first
        Integer[] coins = Arrays.stream(availableCoins)
                                .boxed()
                                .toArray(Integer[]::new);
        Arrays.sort(coins, (a, b) -> b - a); // largest denomination first

        int remainingAmount = targetAmount;
        int totalCoinsUsed  = 0;

        System.out.println("Making change for: " + targetAmount + " cents");
        System.out.println("--------------------------------------------");

        for (int denomination : coins) {
            if (remainingAmount == 0) break; // we're done early

            // How many of this coin can we fit into the remaining amount?
            int coinsOfThisDenomination = remainingAmount / denomination;

            if (coinsOfThisDenomination > 0) {
                System.out.printf("  Using %d x %d-cent coin(s)%n",
                                  coinsOfThisDenomination, denomination);
                totalCoinsUsed  += coinsOfThisDenomination;
                remainingAmount -= coinsOfThisDenomination * denomination;
            }
        }

        if (remainingAmount != 0) {
            // Greedy failed — exact change is impossible with these coins
            System.out.println("  Cannot make exact change!");
            return -1;
        }

        System.out.println("--------------------------------------------");
        System.out.println("Total coins used: " + totalCoinsUsed);
        return totalCoinsUsed;
    }

    public static void main(String[] args) {
        // --- Case 1: Standard US coins — greedy is CORRECT here ---
        int[] usCoins = {25, 10, 5, 1};
        makeChange(usCoins, 41); // optimal: 25+10+5+1 = 4 coins

        System.out.println();

        // --- Case 2: Non-canonical coins — greedy FAILS here ---
        // Coins: {4, 3, 1}. Target: 6
        // Greedy picks: 4 + 1 + 1 = 3 coins
        // Optimal is:   3 + 3   = 2 coins  <-- greedy missed this!
        int[] trickCoins = {4, 3, 1};
        System.out.println("=== Greedy FAILS for non-canonical coins ===");
        makeChange(trickCoins, 6);
        System.out.println("(Optimal answer is actually 2 coins: 3+3)");
    }
}

import java.util.*;

/**
 * Greedy Activity Selection — selects the maximum number of
 * non-overlapping activities from a given list.
 *
 * Greedy rule: always pick the activity with the EARLIEST finish time
 * that doesn't overlap with the previously selected activity.
 */
public class ActivityScheduler {

    // Simple record to hold an activity with a name, start, and end time
    static class Activity {
        String name;
        int    startTime;
        int    finishTime;

        Activity(String name, int startTime, int finishTime) {
            this.name       = name;
            this.startTime  = startTime;
            this.finishTime = finishTime;
        }

        @Override
        public String toString() {
            return String.format("%s [%d-%d]", name, startTime, finishTime);
        }
    }

    /**
     * Selects the maximum set of non-overlapping activities.
     *
     * Time Complexity:  O(n log n) — dominated by the sort step
     * Space Complexity: O(n) — for the result list
     */
    public static List<Activity> selectActivities(List<Activity> activities) {
        // Step 1: Sort by finish time — this is THE greedy decision
        activities.sort(Comparator.comparingInt(a -> a.finishTime));

        List<Activity> selectedActivities = new ArrayList<>();

        // Step 2: Always pick the first activity (it finishes earliest of all)
        Activity lastSelected = activities.get(0);
        selectedActivities.add(lastSelected);

        // Step 3: Scan remaining activities; pick if it starts after last one ends
        for (int i = 1; i < activities.size(); i++) {
            Activity current = activities.get(i);

            // An activity is compatible if it starts at or after the last one finishes
            boolean isCompatible = current.startTime >= lastSelected.finishTime;

            if (isCompatible) {
                selectedActivities.add(current);
                lastSelected = current; // update our reference point
            }
        }

        return selectedActivities;
    }

    public static void main(String[] args) {
        List<Activity> schedule = new ArrayList<>(Arrays.asList(
            new Activity("Math",      1,  4),
            new Activity("English",   3,  5),
            new Activity("Science",   0,  6),
            new Activity("History",   5,  7),
            new Activity("Art",       3,  9),
            new Activity("Music",     5, 10),
            new Activity("PE",        6,  8),
            new Activity("Computing", 8, 11),
            new Activity("Drama",     8, 12)
        ));

        System.out.println("All activities:");
        schedule.forEach(a -> System.out.println("  " + a));

        List<Activity> chosen = selectActivities(schedule);

        System.out.println("\nSelected (max non-overlapping) activities:");
        chosen.forEach(a -> System.out.println("  ✓ " + a));
        System.out.println("\nTotal activities scheduled: " + chosen.size()
                         + " out of " + schedule.size());
    }
}

import java.util.*;

/**
 * Fractional Knapsack using Greedy.
 *
 * Key insight: sort by value-per-unit-weight (value density) descending.
 * Take as much of each item as the remaining capacity allows.
 *
 * This gives the PROVABLY OPTIMAL solution for the fractional variant.
 * For 0/1 knapsack (no fractions), you'd need dynamic programming instead.
 */
public class FractionalKnapsack {

    static class Item {
        String name;
        double weightKg;
        double valueDollars;
        double valueDensity; // dollars per kg — the greedy sorting key

        Item(String name, double weightKg, double valueDollars) {
            this.name          = name;
            this.weightKg      = weightKg;
            this.valueDollars  = valueDollars;
            this.valueDensity  = valueDollars / weightKg; // precompute once
        }

        @Override
        public String toString() {
            return String.format("%-12s | %5.1f kg | $%6.0f | $%.1f/kg",
                                 name, weightKg, valueDollars, valueDensity);
        }
    }

    /**
     * Fills the knapsack to maximise total value using fractional greedy.
     *
     * @param items           list of available items
     * @param capacityKg      maximum weight the knapsack can hold
     * @return                maximum value achievable
     */
    public static double fillKnapsack(List<Item> items, double capacityKg) {
        // Sort by value density, highest first — this is the greedy criterion
        items.sort((a, b) -> Double.compare(b.valueDensity, a.valueDensity));

        System.out.printf("Knapsack capacity: %.1f kg%n%n", capacityKg);
        System.out.println("Items sorted by value density (best first):");
        System.out.println("Item         | Weight  | Value  | Density");
        System.out.println("-------------|---------|--------|--------");
        items.forEach(item -> System.out.println(item));
        System.out.println();

        double remainingCapacity = capacityKg;
        double totalValue        = 0.0;

        System.out.println("Packing decisions:");

        for (Item item : items) {
            if (remainingCapacity <= 0) break; // bag is full

            if (item.weightKg <= remainingCapacity) {
                // Take the WHOLE item — it fits entirely
                double fractionTaken = 1.0;
                totalValue        += item.valueDollars;
                remainingCapacity -= item.weightKg;
                System.out.printf("  Take 100%% of %-12s -> +$%.0f (%.1f kg remaining)%n",
                                  item.name, item.valueDollars, remainingCapacity);
            } else {
                // Take a FRACTION — only as much as fits
                double fractionTaken  = remainingCapacity / item.weightKg;
                double partialValue   = fractionTaken * item.valueDollars;
                totalValue           += partialValue;
                System.out.printf("  Take %.0f%% of %-12s -> +$%.2f (bag full)%n",
                                  fractionTaken * 100, item.name, partialValue);
                remainingCapacity = 0; // bag is now exactly full
            }
        }

        return totalValue;
    }

    public static void main(String[] args) {
        List<Item> hikerItems = new ArrayList<>(Arrays.asList(
            new Item("Gold Dust",    10, 600),   // $60/kg — best density
            new Item("Silver Bars",  20, 500),   // $25/kg
            new Item("Bronze Coins", 30, 450),   // $15/kg
            new Item("Copper Wire",  15, 100)    // $6.67/kg — worst density
        ));

        double maxValue = fillKnapsack(hikerItems, 50.0);
        System.out.printf("%nMaximum value packed: $%.2f%n", maxValue);
    }
}