Easy# Greedily Making Change

ALGOR-DIMWSA

The **change-making problem** has the following specification:

**INPUT:** A set of $m$ integers representing denominations of coins in a fictional currency $\{1, d_1, ..., d_m\}$, an integer representing the total value $V$.**OUTPUT:** A number of coins for each denomination $\{n_1, ..., n_m\}$, such that the total value of the coins is $v$, i.e. $$\displaystyle\sum_{i = 1}^m d_i n_i = v.$$

Assume that the denominations are sorted in *decreasing* order. $d_1 \geq ... \geq d_m$. Notice the set of denominations is guaranteed to *always* include 1.

The greedy algorithm for this problem works iteratively by selecting a denomination at each step. Let $v_i$ be the total sum of all the coins selected by round $i$. In round $i$, the greedy algorithm selects the largest denomination coin, $j$, with $d_j \leq V - v_{i-1}$.

For instance, given the denominations $\{1,5,10,25\}$, and the value $V = 38$, the greedy algorithm described above runs as follows:

Round 1: $V = 38$, so select $25$, $v_1 = 25$.

Round 2: $V - v_1 = 13$, so select $10$, $v_2 = 35$.

Round 3: $V - v_2 = 3$, so select $1$, $v_3 = 36$.

Round 4: $V - v_3 = 2$, so select $1$, $v_4 = 37$.

Round 5: $V - v_4 = 1$, so select $1$, $v_5 = 38$.

Done.

This greedy algorithm is not guaranteed to make change using the smallest number of coins possible for every possible set of denominations.

Among the sets of denominations given below, select the set for which the greedy algorithm is **NOT** guaranteed to find the smallest possible set of coins.

**HINT:** Attempt to find a counter-example which contradicts the correctness of the greedy approach.