Greedy algorithms: activity selection, fractional knapsack, coin change

A greedy algorithm makes the choice that looks best right now at each step and never questions that choice again. No going back, no trying all possibilities. That is why it is fast and its code is short. The problem: it does not give the right answer for every problem. Two kinds of questions come in the exam. One is “run the greedy, write the result” (an activity list, a knapsack value, coins). The other is “this greedy rule is wrong, give a counterexample”.

Golden rules:

1. Greedy = the locally best choice, no going back.
2. To be correct it needs two properties: the greedy-choice property and optimal substructure.
3. To show it is wrong, a single counterexample is enough. Build a small example with 2-3 elements.
4. In activity selection the criterion is the finish time, not the start or the duration.
5. On something divisible (fractional) greedy works; on indivisible 0/1 it does not.

When is greedy correct?

If both properties hold together, greedy gives the optimum:

• Greedy-choice property: There is always an optimal solution that contains the first choice that looks best. That is, making the greedy choice in the first step does not take you away from the optimum.
• Optimal substructure: After the first choice, what remains is a smaller problem of the same kind, and its optimal solution, combined with the first choice, gives the optimum of the whole.

The standard way to prove this is the exchange argument: take any optimal solution, replace its first element with the greedy choice, and show that the solution is still valid and equally good.

The difference from dynamic programming (DP): DP tries all options of each subproblem and writes them to a table. Greedy picks only one. DP is safer, greedy is faster.

Activity selection

There is one hall, and each activity has a start and a finish time. Select the largest number of non-overlapping activities. An activity can start at the moment the previous one ends.

The greedy rule: Sort the activities by finish time. Take the one that finishes earliest. Then take the first activity whose start is not before the finish of the last selected one. Continue like this.

Example: a(1,3), b(2,5), c(4,6), d(6,8), e(5,9), f(7,10), g(9,11), h(10,12), i(11,13).

time   0123456789012345
a  1-3  ==
b  2-5   ===
c  4-6     ==
d  6-8       ==
e  5-9      ====
f  7-10       ===
g  9-11         ==
h 10-12          ==
i 11-13           ==

activity  start   lastFinish  decision
a(1,3)    1 >= -∞     -∞      TAKE, last=3
b(2,5)    2 <  3      3       skip
c(4,6)    4 >= 3      3       TAKE, last=6
d(6,8)    6 >= 6      6       TAKE, last=8
e(5,9)    5 <  8      8       skip
f(7,10)   7 <  8      8       skip
g(9,11)   9 >= 8      8       TAKE, last=11
h(10,12)  10 < 11     11      skip
i(11,13)  11 >= 11    11      TAKE, last=13

earliest finish: [a(1,3), c(4,6), d(6,8), g(9,11), i(11,13)]
optimum count (brute force): 5

Why is it correct? The activity that finishes earliest frees the hall earliest. If you replace the first activity of an optimal solution with it, no conflict arises (it finishes earlier or at the same time). What remains is the subproblem “those that start after the last finish”.

Wrong rules and their counterexamples

earliest start picks [p] vs finish [q(1,4), r(5,8)]
shortest picks [y] vs finish [x(0,5), z(6,11)]

PITFALL · the “boundary” condition. If the question says “an activity may start when the previous one finishes”, the comparison is >=; if it does not say so, >. That is why d(6,8) could be taken after c(4,6).

The knapsack problem

There is a knapsack with capacity W, and items each with a weight ($w_i$) and a value ($v_i$). Make the total value as large as possible.

Example items: A(6 kg, 30), B(10 kg, 40), C(4 kg, 28), D(8 kg, 24). Capacity 15.

Fractional: greedy is optimal

If you can split the item (like flour or gold dust), start with the one that has the highest value per kilo, take as much as fits, and split the last item.

  take 4/4 of C (ratio 7.0) total=28.0
  take 6/6 of A (ratio 5.0) total=58.0
  take 5/10 of B (ratio 4.0) total=78.0
fractional value 78.0

Why is it correct? Every kilo in the knapsack should be filled with the most valuable kilo. Replacing a lower-ratio kilo with a higher-ratio kilo always increases the value.

0/1: greedy breaks

If you cannot split the item, the same rule gives a wrong result:

  greedy 0/1 picks C A value 58
  optimal 0/1 picks B C value 68

After taking C and A, 5 kg is empty but B and D do not fit. Part of the capacity was wasted. B + C, on the other hand, makes 68 with 14 kg. The 0/1 knapsack is solved with DP in $O(nW)$ time (we do not go into DP in this course; it is enough to know why greedy breaks).

PITFALL · do not compute the ratio with int division. If v[i] / w[i] are two ints, values like 7/2 are truncated and the order breaks. Write (double) v[i] / w[i].

Coin change

Pay an amount with the fewest coins. The greedy rule: at each step give the largest coin that fits in the amount.

Coins {25, 10, 5, 1}, amount 68:

left   given
68     25
43     25
18     10
 8      5
 3      1
 2      1
 1      1
 0      → 7 coins

In “standard” systems like this (25-10-5-1, or 50-20-10-5-1) greedy is optimal. But not in every system:

{1,4,6} 8 greedy [6, 1, 1] dp 2
{1,7,10} 14 greedy [10, 1, 1, 1, 1] dp 2

For 8, 4 + 4 is two coins; because greedy grabbed 6, it had to pay the remaining 2 with 1s. For 14, it gave 10 + 1 + 1 + 1 + 1 instead of 7 + 7. The general solution is DP:

$dp[0] = 0,\qquad dp[a] = \min_{c \le a} \big(dp[a-c] + 1\big)$

How to solve a greedy question in the exam

Three patterns for three kinds of questions:

"Run the greedy":
  write the criterion (finish, ratio, largest coin)
  sort, decide one by one with a table
"Is greedy optimal?":
  look for a counterexample with 2-3 elements
  if you cannot find one, build an exchange argument
"Write the method":
  sort the indices by the criterion
  a single loop, take if the condition holds

When looking for a counterexample, ask this question: “Can the first choice of greedy block two better choices at once?” In activity selection, a long activity that starts early; in coin change, a large coin that leaves an awkward remainder; in the 0/1 knapsack, a small item with a high ratio that leaves empty space plays this role. In the fractional knapsack and in the “earliest finishing” rule, such a blocker cannot be built; that is why they are correct.

Where are the greedy algorithms in this course?

The correctness of all of them depends on proving the two properties above for that problem. Dijkstra breaking on a negative edge is also a violation of the greedy-choice property.

Common mistakes

static int maxActivities(int[] s, int[] f) {
    int n = s.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Integer.compare(f[a], f[b]));
    int count = 0, lastFinish = Integer.MIN_VALUE;
    for (int i : idx) {
        if (s[i] >= lastFinish) {
            count++;
            lastFinish = f[i];
        }
    }
    return count;
}

static double fractionalKnapsack(int[] w, int[] v, int cap) {
    int n = w.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Double.compare((double) v[b] / w[b], (double) v[a] / w[a]));
    double total = 0;
    int left = cap;
    for (int i : idx) {
        if (left == 0) break;
        int take = Math.min(left, w[i]);
        total += (double) v[i] * take / w[i];
        left -= take;
    }
    return total;
}