Background: Greedy Change-making algorithm

say we want to make 84 cents with least amount of coins.

Step 1, Use the most of the largest value coin

Step 2, Use the most of the 2nd largest

Step 3, etc

Example: 84 cents US currency, 3 quarters (most without going over), can't use dimes, 1 nickle (most amount without going over), and 4 pennies (most without going over).

Problem: we chose to figure out ways to make this algorithm fail, so in the example, (if there was a 21 cent piece, the algorithm would fail).

42 cents: 1 quarter, 1 dime, 1 nickle, 2 pennies. (Greedy change making algorithm)

42 cents: 2 21-cent pieces

Algorithm fails.

So we are supposed to find a cent value that will make this algorithm fail if we cannot use the nickle. Quarters, Dimes, and Pennies.

## Bookmarks