Skip to content
wannacode

When a greedy algorithm fails

In short: A greedy algorithm fails when the best choice now blocks a better answer later; one counterexample is enough, and the fix is often dynamic programming.

Problem

One voucher too many

The shop pays out loyalty points as vouchers of 4, 3 and 1 points. Every voucher is a separate code the customer types in at the till. So the program gives as few vouchers as it can: every time the largest one that fits, like the change in euro coins in the previous lesson.

static List<Integer> greedy(int[] vouchers, int points) {
    List<Integer> used = new ArrayList<>();
    for (int v : vouchers) {
        while (points >= v) {
            used.add(v);
            points -= v;
        }
    }
    return used;
}
int[] vouchers = {4, 3, 1};
System.out.println("6 points: " + greedy(vouchers, 6));
Output
6 points: [4, 1, 1]

Three codes for 6 points. Yet 3 + 3 is two. The program has no bug in its code: the rule "the largest that fits" is simply not true for these vouchers. With euro coins it is true, here it is not.

The idea

Greedy does not go back

A greedy algorithm makes, at every step, the choice that looks best right now, and never reconsiders it. Once it has taken 4, there are only 1-point vouchers left for the remaining 2 points. That 3 + 3 is better, greedy cannot see: it tries nothing else.

So a greedy idea is accepted only with a proof that the local choice never hurts. And it is rejected with a single input on which it gives a worse answer. Such an input is called a counterexample. 6 points is a counterexample for greedy with vouchers 4, 3 and 1.

The same kind of vouchers can be safe or unsafe depending on their values. 4, 2 and 1 are safe: every larger one is a multiple of the smaller. 4, 3 and 1 are not.

See it

Greedy and DP side by side

The fix is not to decide in one go, but to compute the fewest vouchers for every amount from 0 to 6. For p points you try every voucher v as the last one: p − v points remain, and the fewest for them has already been computed. This is dynamic programming for coins, with a table best. last keeps which voucher came last, so you can walk back to the vouchers themselves.

static List<Integer> fewest(int[] vouchers, int points) {
    int[] best = new int[points + 1];
    int[] last = new int[points + 1];
    for (int p = 1; p <= points; p++) {
        best[p] = points + 1;
        for (int v : vouchers) {
            if (v <= p && best[p - v] + 1 < best[p]) {
                best[p] = best[p - v] + 1;
                last[p] = v;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int p = points; p > 0; p -= last[p]) {
        used.add(last[p]);
    }
    return used;
}
int[] vouchers = {4, 3, 1};
System.out.println("6 points: greedy " + greedy(vouchers, 6) + ", fewest " + fewest(vouchers, 6));
System.out.println("10 points: greedy " + greedy(vouchers, 10) + ", fewest " + fewest(vouchers, 10));
Output
6 points: greedy [4, 1, 1], fewest [3, 3]
10 points: greedy [4, 4, 1, 1], fewest [4, 3, 3]

static List<Integer> fewest(int[] vouchers, int points) {
    int[] best = new int[points + 1];
    int[] last = new int[points + 1];
    for (int p = 1; p <= points; p++) {
        best[p] = points + 1;
        for (int v : vouchers) {
            if (v <= p && best[p - v] + 1 < best[p]) {
                best[p] = best[p - v] + 1;
                last[p] = v;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int p = points; p > 0; p -= last[p]) {
        used.add(last[p]);
    }
    return used;
}
Step by step, in words
  1. Greedy, 6 points. The largest voucher that fits is 4: it takes it. 2 points left.
  2. 2 points left: 4 and 3 do not fit. It takes 1. 1 point left.
  3. Another 1. Done: 4 + 1 + 1, 3 vouchers. Taking 4 was final, and it closed the way to 3 + 3.
  4. DP computes the fewest vouchers for every amount from 0 to 6. best[0] = 0: 0 points need no voucher.
  5. best[1]: 1 → 1 + best[0] = 1. The fewest is 1, last voucher 1.
  6. best[2]: 1 → 1 + best[1] = 2. The fewest is 2, last voucher 1.
  7. best[3]: 3 → 1 + best[0] = 1; 1 → 1 + best[2] = 3. The fewest is 1, last voucher 3.
  8. best[4]: 4 → 1 + best[0] = 1; 3 → 1 + best[1] = 2; 1 → 1 + best[3] = 2. The fewest is 1, last voucher 4.
  9. best[5]: 4 → 1 + best[1] = 2; 3 → 1 + best[2] = 3; 1 → 1 + best[4] = 2. The fewest is 2, last voucher 4.
  10. best[6]: 4 → 1 + best[2] = 3; 3 → 1 + best[3] = 2; 1 → 1 + best[5] = 3. The fewest is 2, last voucher 3.
  11. Back along last: 6 → 3 → 0. The vouchers are 3 and 3: 2 of them.
  12. The same amount, two answers: greedy gives 3 vouchers, DP gives 2. Greedy never goes back on a choice; DP tries every last voucher for every amount.

DP does more work: amounts × vouchers, that is O(n·k), while greedy is as long as the vouchers it takes. But DP is right for any vouchers, and greedy only for some.

"Infinity" in best is points + 1: more than any real answer, because with a 1-point voucher the answer is at most points. Integer.MAX_VALUE looks more natural, but best[p - v] + 1 would overflow into -2,147,483,648 and win the comparison.

Try it

Predict

The same vouchers, 10 points. What does greedy give?

static List<Integer> greedy(int[] vouchers, int points) {
    List<Integer> used = new ArrayList<>();
    for (int v : vouchers) {
        while (points >= v) {
            used.add(v);
            points -= v;
        }
    }
    return used;
}


int[] vouchers = {4, 3, 1};
System.out.println(greedy(vouchers, 10));
Answer

Try it

Fill in

For p points with v as the last voucher: which amount does the rest come from?

static List<Integer> fewest(int[] vouchers, int points) {
    int[] best = new int[points + 1];
    int[] last = new int[points + 1];
    for (int p = 1; p <= points; p++) {
        best[p] = points + 1;
        for (int v : vouchers) {
            if (v <= p && best[p - v] + 1 < best[p]) {
                best[p] = best[] + 1;
                last[p] = v;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int p = points; p > 0; p -= last[p]) {
        used.add(last[p]);
    }
    return used;
}

See it

The knapsack by fee per kilogram

The courier has room for 10 kg. Three parcels are waiting: 6 kg with a fee of €30, and two of 5 kg with a fee of €20 each. The greedy idea: sort the parcels by fee per kilogram and take them while they fit.

static int byRatio(int[][] parcels, int capacity) {
    int[][] sorted = parcels.clone();
    Arrays.sort(sorted, (a, b) -> Double.compare((double) b[1] / b[0], (double) a[1] / a[0]));
    int total = 0;
    for (int[] p : sorted) {
        if (p[0] <= capacity) {
            capacity -= p[0];
            total += p[1];
        }
    }
    return total;
}


static int bestFee(int[][] parcels, int i, int capacity) {
    if (i == parcels.length) {
        return 0;
    }
    int skip = bestFee(parcels, i + 1, capacity);
    if (parcels[i][0] > capacity) {
        return skip;
    }
    int take = parcels[i][1] + bestFee(parcels, i + 1, capacity - parcels[i][0]);
    return Math.max(skip, take);
}
int[][] parcels = {{6, 30}, {5, 20}, {5, 20}};
System.out.println("By fee per kilogram: " + "€" + byRatio(parcels, 10));
System.out.println("Best: " + "€" + bestFee(parcels, 0, 10));
Output
By fee per kilogram: €30
Best: €40

The 6 kg parcel is €5 per kg, the others are €4 per kg. Greedy takes it first, and the remaining 4 kg are not enough for anything. The two 5 kg parcels fill the van exactly and bring €40. bestFee tries every subset: for every parcel "take" or "skip". That is 2ⁿ, and for a real number of parcels you need DP for the knapsack.

(double) b[1] / b[0]: without the conversion to double the division is integer division, and €7 for 2 kg becomes €3 per kg instead of 3.5. Then the order is wrong before greedy has even started.
More precisely, if you are curious

If the parcels can be split, greedy by fee per kilogram is right. That is how it works with goods in bulk: coffee beans, flour, fuel. You take as much as fits of the most expensive per kilogram, then of the next, and you cut the last one. This is the fractional knapsack, and there no local choice closes off a better path.

A whole parcel cannot be cut. That is exactly what makes greedy dangerous: the 6 kg take up room that the two 5 kg parcels would use better.

The idea

How to test a greedy idea

A greedy idea sounds right almost every time. How do you find out whether it is? You look for a counterexample, not by hand, but with a program:

  1. Write a slow but surely correct solution: a brute force that tries every possibility.
  2. Run greedy and the brute force on all small inputs: every amount from 1 to 100.
  3. The first place where they disagree is a counterexample. If they agree everywhere, you have proven nothing, but you have a reason to look for a proof.

The brute force here tries how many of each coin to take: from 0 to as many as fit, recursively for the next one. The last coin is 1, and it covers whatever is left.

static int tryAll(int[] coins, int i, int amount) {
    if (i == coins.length - 1) {
        return amount;
    }
    int best = Integer.MAX_VALUE;
    for (int k = 0; k * coins[i] <= amount; k++) {
        int rest = tryAll(coins, i + 1, amount - k * coins[i]);
        best = Math.min(best, k + rest);
    }
    return best;
}


static void check(String name, int[] coins, int upTo) {
    for (int a = 1; a <= upTo; a++) {
        int g = greedy(coins, a).size();
        int b = tryAll(coins, 0, a);
        if (g != b) {
            System.out.println(name + ": " + a + " → greedy " + g + ", fewest " + b);
            return;
        }
    }
    System.out.println(name + ": no counterexample up to " + upTo);
}
check("Vouchers 4, 3, 1", new int[] {4, 3, 1}, 20);
check("Euro coins", new int[] {200, 100, 50, 20, 10, 5, 2, 1}, 100);
check("Old British", new int[] {30, 24, 12, 6, 3, 1}, 100);
Output
Vouchers 4, 3, 1: 6 → greedy 3, fewest 2
Euro coins: no counterexample up to 100
Old British: 48 → greedy 3, fewest 2

Three systems in a second:

  • the vouchers 4, 3 and 1 fall at 6;
  • the euro coins in cents (1, 2, 5, 10, 20, 50 cents, €1 and €2) do not fall up to 100 cents;
  • the old British coins in pence (1, 3, 6, 12, 24 and 30, part of the system before 1971) fall at 48: greedy gives 30 + 12 + 6, while 24 + 24 is two.

The brute force is exponential, and for large inputs it is hopeless. But counterexamples are almost always small, and it goes through small inputs in no time.

Try it

Find the bug

A colleague ran the check for the vouchers and announced that greedy is right. You know that 6 is a counterexample. Where is the bug?

check("Vouchers 4, 3, 1", new int[] {4, 3, 1}, 5);
check("Euro coins", new int[] {200, 100, 50, 20, 10, 5, 2, 1}, 100);
check("Old British", new int[] {30, 24, 12, 6, 3, 1}, 100);
Output
Vouchers 4, 3, 1: no counterexample up to 5
Euro coins: no counterexample up to 100
Old British: 48 → greedy 3, fewest 2

Pick the line with the bug.

More precisely, if you are curious

How far to check. For coins and vouchers there is an exact answer (Kozen and Zaks, 1994): if greedy is wrong somewhere, the smallest counterexample is less than the sum of the two largest values. So a full check up to there is a proof:

  • the vouchers 4, 3 and 1: up to 7;
  • the euro coins: up to 300 cents (€2 + €1). Run up to 300, the check finds no counterexample, so greedy is right for euro coins for every amount;
  • the old British coins: up to 54 (30 + 24), and 48 is below that bound.
Euro coins up to 300 cents
Euro coins: no counterexample up to 300

Up to 300 the brute force makes about 26 million calls and still finishes in seconds. For a larger range the better check is DP instead of the brute force: it is just as surely correct, and it is O(amount × coins).

For other problems there is usually no such bound. Then checking small inputs does not prove, it only searches. The proof is an argument: most often, that any optimal solution can be changed step by step into the greedy one without getting worse.

Exercise

Marketing's new vouchers

Solve the task in your editor.

The new vouchers. Marketing wants vouchers of 9, 6, 5 and 1 points and asks whether the till can stay greedy. Use the check from the lesson (greedy, the brute force and check) for amounts up to 30 points and find the smallest counterexample.

Output
Vouchers 9, 6, 5, 1: 11 → greedy 3, fewest 2

More tasks

  • Fix the system. Which voucher do you add to 4, 3 and 1 so that greedy becomes right up to 7? Try it with the check.
  • The knapsack with a check. Write a check for the knapsack: greedy by fee per kilogram against bestFee for all combinations of three parcels with weights from 1 to 6 kg and fees from €1 to €9. How many counterexamples does it find?
  • Deadlines. The tasks have a duration and a deadline. Does greedy "shortest first" meet the most deadlines? Find a counterexample by trying every order of 4 tasks.

Test

Check yourself

1. The vouchers are 4, 3 and 1 points. How many vouchers does greedy give for 6 points, and what is the fewest?
2. A greedy idea passed 50 tests. What does that prove?
3. The courier has room for 10 kg. Parcels: 6 kg for €30, 5 kg for €20 and 5 kg for €20. What does greedy by fee per kilogram take?
4. Why is "infinity" in the voucher DP points + 1, and not Integer.MAX_VALUE in Java?
5. The check looks for a counterexample for vouchers 4, 3 and 1 only up to 5 points and finds none. Why?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·