The greedy choice

A greedy algorithm builds its answer one piece at a time. At each step it takes the piece that looks best right now, and it never goes back to change an earlier choice. This is fast and simple. It is also often wrong, so the real skill is knowing when it is right.

Build the answer one piece at a time

Many problems ask for the best answer out of a huge number of possible answers:

• the most meetings that fit in one room;
• the fewest coins that make an amount;
• the shortest code for each letter of a text.

Trying every possible answer is usually far too slow: there are 2ⁿ ways (n twos multiplied together) to choose some of n things. A greedy algorithm makes one choice, then the next, then the next, each time by a simple rule such as “the cheapest”, “the one that ends first” or “the largest that fits”. It never tries the other choices, and it never undoes one.

A bag that holds 8 kg

A bag holds 8 kg. There are four items, each with a weight and a value. Any part of an item may be taken, like rice from a sack: half of an item weighs half as much and is worth half as much. The goal is the most valuable bag. This is the fractional knapsack problem (a knapsack is a bag).

Three greedy rules come to mind: the most valuable item first, the lightest item first, or the most value per kg first. The figure tries each one. Only the third is always right.

Why value per kg? Think of the bag as 8 separate kilograms to fill. Each kilogram can hold some part of some item, and its worth is that item’s value per kg. To make the total as large as possible, fill every kilogram with the best value per kg still available. That is exactly what the rule does. Being able to cut items matters here: lesson 5 shows that the same rule fails when items must be taken whole.

The two things greedy needs

A greedy algorithm gives the best answer when two things are true.

1. The greedy choice is safe. There is a best answer that contains the first choice the rule makes. So taking it cannot shut out every best answer. (In the bag: some best bag contains as much as possible of the item with the most value per kg.)
2. What is left is the same kind of problem. After the choice, the rest of the answer must be a best answer to the smaller problem that remains. This is called optimal substructure. (In the bag: after taking that item, the best way to fill the remaining space is the same question with less room and one item fewer.)

Together they give a proof by induction (CORR-3): the first choice is safe, the rest is a smaller problem of the same kind, so the same rule handles it, and so on down to an empty problem. Dynamic programming (DYNP) needs the second property too; what greedy adds is the first one, which lets it try one choice instead of all of them.

The first property is the hard part, and it is where most wrong greedy ideas break. Lesson 2 shows the standard way to prove it: the exchange argument.

Cost

Most greedy algorithms have the same shape: sort the pieces by the rule, then walk through them once, taking each piece that still fits. Sorting costs O(n log n) and the walk costs O(n), so the whole thing is O(n log n).

When the rule changes as choices are made (the best piece depends on what was taken before), a heap gives the best piece in O(log n) each time (HEAP-4). Huffman coding in lesson 4 works that way. A union-find (DSUF) is the other common helper: Kruskal’s method for spanning trees takes the cheapest edge that does not close a loop.

In Python

def best_bag(capacity, items):         # items: (weight, value)
    order = sorted(items, key=lambda it: it[1] / it[0],
                   reverse=True)          # most value per kg first
    total = 0.0
    for weight, value in order:
        if capacity == 0:
            break
        take = min(weight, capacity)      # all of it, or what fits
        total += value * take / weight
        capacity -= take
    return total

sorted with a key sorts by the value the key function returns; reverse=True puts the largest first. Only the last item taken can be cut, because every item before it fitted whole.