Most Efficient Way To Carry Exact Sub 5 Dollar Change in Australian Currency

A quick blog post today.  I wanted to know the most efficient way to carry change with me.  I'm a little OCD and I sometimes like to be able to pay with exact money.  It's easy to get to multiples of 5 dollars with notes, so all we need to know is the combinations of coins you would need to carry to give change up to 5 dollars.  The smallest denomination of Australian currency is the 5 cent coin.  This means that I need to be able to give any amount of change from 5c to 495c in 5c intervals with any combination of coins selected.

The code for today's post can be found here.

I defined efficiency using two metrics, least coins and least weight.  Finding the combination of coins was relatively easy.  I started by finding the combinations of minimum coins with an Octave script.  It took a while and I had to make some optimizations to speed it up, but it got there in the end.  I tried to do the same thing with the minimum weight calculations but it took too long.  So I ported the code over to C++ and made a "purse" class to track the weight of coins in the purse.  This sped up the process significantly.  The results are listed below.

Weight of Australian coins according to the reserve bank

$2    6.60 g

$1    9.00 g

50c  15.55 g

20c  11.30 g

10c   5.65 g

5c    2.83 g

Minimum coins needed to give exact sub $5 change

2x$2, 1x$1, 1x50c, 2x20c, 1x10c, 1x5c

2x$2, 1x$1, 1x50c, 1x20c, 2x10c, 1x5c

1x$2, 2x$1, 1x50c, 2x20c, 1x10c, 1x5c

1x$2, 2x$1, 1x50c, 1x20c, 2x10c, 1x5c

Minimum weight of coins to give exact sub $5 change

2x$2, 1x$1, 1x50c, 0x20c, 4x10c, 1x5c

2x$2, 1x$1, 1x50c, 1x20c, 2x10c, 1x5c

By a happy coincidence there is an intersection between the two groups.  The following combination satisfies the minimum weight and minimum coins condition.  8 coins and 63.18 g.

2x$2, 1x$1, 1x50c, 1x20c, 2x10c, 1x5c

Most Efficient Way To Carry Exact Sub 5 Dollar Change in Australian Currency

It might only be a fraction of a gram but it's one of those things I just have to know even though it doesn't really matter.