## Strange Change

A classical example of a greedy algorithm is the algorithm to return change given a set of face values. In Canada (and the US) the usual coins are 25¢, 10¢, 5¢ and 1¢ coins—there’s also a 50¢ coin, but they’re rare nowadays. The algorithm proceeds as follows. You are given a number of cents to return, and you start with the highest face value, $v_1$. You subtract $v_1$ from the numbers of cents while the number of cents still to return is greater or equal to $v_1$. If the number of cents still to return is smaller than $v_1$ but not zero, you repeat using the next denomination, $v_2$, then if there’s still some, with $v_3$, etc. Eventually, you return all the change, using a minimal number of coins.

So the next interesting question is whether our current coinage is optimal, as measured by the (average) quantity of returned change? No. It’s not. Let’s see why.

There are two conditions on the coinage to ensure a good solution. The first is that

$v_1 > v_2 > \cdots > v_{k-1} > v_k$,

and the second is that $v_k=1$. Having a 1¢ coin ensures that all possible amounts of change can be given, if only by using a degenerate solution with tons of 1¢ coins. Once we’ve decided on the values $\{v_i\}_{i=1}^{k}$, the algorithm to give change is straightforward:

void give_change(const int values[], int cents)
{
int face=0;
while (cents)
{
if (cents>=values[face])
{
// display values[face] or
// add it to an array
cents-=values[face];
}
else
face++;
}
}


We can instrument the above function to count the number of coins returned for cents, and cycle between 1 and 99 cents (thus supposing that 1$is not change—not true for Canadian money, where we have 1$ and 2$coins!). With the above function instrumented, we can count the average number of coins returned for a given series of face values, and we’re ready to find better ones. To find for a better solution, we can use simple backtracking to enumerate all possible valid values of $\{v_i\}_{i=1}^{k}$ that satisfy: $100 > v_1 > v_2 > \cdots > v_{k-1} > v_k=1$, and vary $k=1,2,\ldots$ and look at the best solutions, the ones that minimize the average of coins to return change between 1 and 99¢. At first sight, looking for all possible combinations seems computationally expensive, but it’s not really that bad since, because each new face value is smaller than the preceding, we will not explore $99^k$ combinations, but $\frac{99!}{(99-k)!}=99\times{98}\times{97}\cdots\times{99-k+1}$, which, while not that small, is much smaller than $99^k$. And even with $k=7$, it takes only a few minutes on a i7 CPU. * * * So let us dispense ourselves from the mechanics of backtracking for now. Let us just look at the solutions we get when we vary $k$. What do we get?  $k$ Face values AverageCoins 1 1 $50$ 2 10,1 $9.\overline{09}$ 3 22,5,1 $5.\overline{31}$ 4 37,11,3,1 $4.\overline{14}$ 5 40,16,7,3,1 $3.\overline{49}$ 6 62,25,11,5,2,1 $3.\overline{16}$ 7 61,29,18,8,5,2,1 $2.\overline{8}$ The optimal face values found by the algorithm are really strange, and really departs from the familiar coinage. But they do much better. The average number of coins for change using the familiar 25¢, 10¢, 5¢ and 1¢ coins is $4.\overline{74}$. The weird solution yields an average $4.\overline{14}$, roughly 12% better. * * * We used rules that are a bit different than what we are used to, and in particular, we lifted the constraint that we should have at least a coin that is an integer divisor to 100. For example, 25¢, with four quarter to a dollar. If we have a 37¢ coin, we can, indeed, reduce the amount of change we have in our pockets, but we can’t easily give change for 1$. Coin rolls are now also very strange. 37$rolls, really? (and, yes, 37$ because $\mathrm{lcm}(37,100)=3700$.)

One could argue that using base 10 friendly face values (100¢ to 1$) is arbitrary and that, in principle, it’s no more difficult to have 37 or 62¢ coins; but we sacrifice regularity. Change for 1$ becomes 62¢, 25¢, 11¢, and 2¢, which is a good deal more complicated to provide for. I would guess it’s quite impractical—or just plain stupid.

*
* *

OK, let’s get back to backtracking. How does the solver works? Well, it’s basically a recursive method that chooses $v_1$, and once $v_1$ is chosen, explore combinations starting with $1\leqslant{}v_2 < v_1$. At any stage, $i the algorithm fixes $v_i$ and then explore combinations with $1\leqslant{}v_{i+1}. While it sounds complicated, it's not really a lot of code:

void search( int values[],
int last_face,
int & best_total_so_far,
int depth,
int max_depth=4 )
{
if (depth<=max_depth)
{
if (last_face>1)
{
for (int i=last_face-1;i;i--)
{
values[depth]=i;
search(values,i,best_total_so_far,depth+1, max_depth);
}
}
else // ==1
{
//solution?
values[depth]=0;

int this_total;
test(values,this_total); // superfluous to test against

if (this_total <= best_total_so_far)
{
best_total_so_far=this_total;
// display solution here
}
}
}
}


The above includes a call to test(), a function that verifies if the zero-terminated array of face values values[] is a solution and return the total number of coins needed to give all possible amounts of change between 1 and 99¢. It also has max_depth, a parameter that controls the number of coins in the sought solution.

This piece of code enumerates all possible solutions with $k$ coins, under the constraint that $100 > v_1 > v_2 > \cdots > v_{k-1} > v_k=1$, and only displays increasingly better solutions. The last solution(s) it prints is/are the best.

### 2 Responses to Strange Change

1. What is the best you can do if you restrict coinage to divisors of 100?

• Since $100=2^2\cdot{}5^2$, and all coins must divide 100 evenly, the possible coins are (excluding 100) : 50¢, 25¢, 20¢, 10¢, 5¢, 4¢, 2¢ and 1¢ (that’s the distinct powersets of {2,2,5,5}). I would have to run the simulation, but it does much better than just our 50¢, 25¢, 10¢, 5¢, 1¢ system. You hand up 30% less change for returns less than 5¢, especially because of the 2 and 4¢ coins.

…however just dropping the pennies and rounding up to nickels simplifies things a lot.