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

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 Average
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<k the algorithm fixes v_i and then explore combinations with 1\leqslant{}v_{i+1}<v_i. 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--)
        search(values,i,best_total_so_far,depth+1, max_depth);
    else // ==1

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

       if (this_total <= best_total_so_far)
         // 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: