Algorithms and Data Structures for Programming Contests

Greedy Algorithms

Discussion

What is it?

• Construct solution piece-by-piece.
• At each step, make best "local" decision — ignore trade-offs.

Example: making change

Input:

Coin denominations 1 = d₁ < d₂ < ... < d_N; amount A.

Output:

Exact change for A, using as few total coins as possible.

Algorithm

• Give as many coins of denomination d_N as possible, then as many coins of denomination d_N−1 as possible, ...

Problem

• Works fine for "standard" denominations (d₁ = 1¢, d₂ = 5¢, d₃ = 10¢, d₄ = 25¢). But does not achieve minimum number of coins for other denominations (e.g., 1¢, 10¢, 25¢).

Solution?

• Dynamic programming will work, based on the following recursion:
  • either optimal solution does not use any coin with value d_N,
  • or optimal solution uses one coin with value d_N, along with a minimum number of coins for amount A − d_N.

How do we know when greedy will work?

• Required property: for every denomination d_n and for every amount a with d_n ≤ a < d_n+1, one of the best ways of making change for a uses at least one coin of denomination d_n.
• This can be checked, on a tedious case-by-case basis, for the standard denominations (1¢, 5¢, 10¢, 25¢).

Try it!

• Try Problem S4 (Animal Farm) from the CCC programming contest.

Regroup

© Copyright 2012–2015 François Pitt <francois.pitt@utoronto.ca>
last updated at 08:24 (EST) on Thu 5 Mar 2015
Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.