Minimize Change

Have you ever been to another country, using a new currency for the first time? The standard problem is naturally that it is very easy to use the notes and the bigger (in terms of value) coins, ending up with a whole mess of more or less valuable coins.

Searching the web gave me some answers, one article from Imperial College of Science, Technology and Medicine's Centre for Planning and Resource Control describes Having Enough Change in Your Pocket.

But the best would be to get a general theory on how to Minimize Change, with a desicion making procedure for each time one performs a monetary operation.

A well known example would be when buying something costing e.g. 26 cents, paying with one 50 cent and one 1 cent to get 25 cent back, instead of just paying with one 50 cent coin. (Which would yield a whole array of different coins - annoying.)

But is there any theory available?

From the pages of University of California, Santa Barbara presents some questions from "Data Structures, Algorithms, and Applications in C++” that serves as good leads. No answers are given though.

The closest I got today was the solution to the Exact Change problem, given by Boaz Patt-Shamir, Yiannis Tsiounis and Yair Frankel, written as an article in SIAM Journal on Discrete Mathematics or as a more available presentation in PowerPoint.

Finally I found a lecture note in algorithms from Griffith University that describes the Making Change problem, which at first sight seems like what we want...

Posted by ludvig at August 27, 2002 08:26 PM | TrackBack