?

Free Version

Upgrade subject to access all content

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.

A

$\{1, 5, 10, 25\}$

B

$\{1, 2, 4, 8\}$

C

$\{1,4\}$

D

$\{1,10,25\}$