Greedy algorithms

A greedy algorithm builds its answer step by step, and at each step takes the choice that looks best right now, without ever going back. It is usually simple and fast. The hard part is not writing it but knowing whether it is correct: for some problems the locally best choice always leads to the best overall answer, and for others it leads you astray.

You have already met three greedy algorithms: Dijkstra (always finalise the closest place), Prim and Kruskal (always take the cheapest safe edge). Each came with a reason why greedy works there.

Scheduling: which rule is right?

One tower crane, many booking requests, each with a start and end time. Accept as many as possible without overlaps. Three greedy rules sound reasonable: earliest start, shortest booking, earliest finish. Only one is always optimal. Try them:

Earliest finish wins, and we can prove it with an exchange argument: take any optimal schedule. Its first booking ends no earlier than the booking that finishes first overall, so swapping it for that one still leaves a valid schedule of the same size. Repeat for the rest. The greedy choice is never worse than what an optimal answer does.

1var bookings = new List<(string Id, int Start, int End)>2{3    ("A", 6, 9), ("B", 9, 12), ("C", 8, 10), ("D", 12, 15),4    ("E", 15, 18), ("F", 14, 16), ("G", 5, 18), ("H", 10, 11)5};6 7var chosen = new List<string>();8int freeFrom = int.MinValue;9foreach (var b in bookings.OrderBy(b => b.End))      // earliest finish first10{11    if (b.Start < freeFrom) continue;                 // clashes with the last one taken12    chosen.Add(b.Id);13    freeFrom = b.End;14}15Console.WriteLine($"{chosen.Count}: {string.Join(", ", chosen)}");

4: A, H, D, E

Sorting is O(n log n); the scan is O(n). Trying every subset of bookings would be O(2ⁿ).

Making change

To pay an amount with the fewest coins, the greedy rule is “always use the biggest coin that fits”. For normal currencies (1, 2, 5, 10, 20, …) this is optimal. For other coin systems it is not:

1Console.WriteLine(string.Join(" + ", GreedyChange(48, new[] { 20, 10, 5, 2, 1 })));2Console.WriteLine(string.Join(" + ", GreedyChange(6, new[] { 4, 3, 1 })));   // 3 + 3 is better3 4static List<int> GreedyChange(int amount, int[] coinsLargestFirst)5{6    var used = new List<int>();7    foreach (int c in coinsLargestFirst)8        while (amount >= c) { used.Add(c); amount -= c; }9    return used;10}

20 + 20 + 5 + 2 + 1
4 + 1 + 1

With coins 4, 3 and 1, greedy pays 6 as 4 + 1 + 1 (three coins), but 3 + 3 needs only two. Taking the 4 felt best but blocked the better answer. Problems like this need dynamic programming (later in this module), which considers every option without trying every combination.

Fractional knapsack

A truck can carry 50 kg. Materials have a value and a weight, and you may take part of any material. Greedy by value per kilogram is optimal: fill up with the most valuable material per kg first. (If items cannot be split, the “0/1 knapsack”, greedy fails and you need DP again.)

1var items = new[]2{3    (Name: "Steel", Value: 60, Weight: 10),4    (Name: "Copper", Value: 100, Weight: 20),5    (Name: "Timber", Value: 120, Weight: 30)6};7 8double capacity = 50, total = 0;9foreach (var it in items.OrderByDescending(i => (double)i.Value / i.Weight))   // best value per kg first10{11    double take = Math.Min(it.Weight, capacity);12    total += take * it.Value / it.Weight;13    capacity -= take;14    Console.WriteLine($"{it.Name}: {take} of {it.Weight} kg");15    if (capacity == 0) break;16}17Console.WriteLine($"Value: {total}");

Steel: 10 of 10 kg
Copper: 20 of 20 kg
Timber: 20 of 30 kg
Value: 240

How to approach a greedy idea

1. State the greedy rule precisely (“sort by end time, take whatever fits”).
2. Hunt for a counterexample with small inputs, as the widget does for earliest start and shortest first. Most wrong greedy rules fail on 3 or 4 items.
3. If you cannot break it, argue it: an exchange argument (“swapping an optimal choice for the greedy one never makes things worse”) is the usual proof.
4. If it does break, think about dynamic programming.

1Console.WriteLine(MinTrips(new[] { 3, 2, 2, 1 }, 3));2Console.WriteLine(MinTrips(new[] { 3, 5, 3, 4 }, 5));3 4static int MinTrips(int[] loads, int limit)5{6    var w = loads.OrderBy(x => x).ToArray();7    int light = 0, heavy = w.Length - 1, trips = 0;8    while (light <= heavy)9    {10        if (w[light] + w[heavy] <= limit) light++;   // the lightest rides along11        heavy--;                                      // the heaviest always goes now12        trips++;13    }14    return trips;15}

3
4