Whats the "Optimal Coin Set Problem"? Its the following problem:
Come up with four denominations of coins that produce the lowest average number of coins for all change values between 0 and 100.
This problem comes from a thought experiment: Why are U.S. (and many other world) coins the following values: {1,5,10,25}. Why not some other set? What other set would you choose?
I once had the idea that if all monetary denominations were prime numbers, that people would get a lot better at arithmetic. Maybe something like {1,7,23}. But, I digress.
If we define a numerical criteria for an "optimal" set of coin denominations, then all we have to do is find the set that minimizes that value, and voila! We've done it.
Intuitively, it seems as though it would be simple to write such a program, but when it comes down to it, its kind of complex, especially if the number of coins in the set isn't fixed. Running time is also of consideration. My first-pass implementation takes O(n^8) or somewhere thereabouts. In other words, its very very slow. In fact, as I write this, it still hasn't finished running yet. UPDATE: I totally reworked and optimized the source code, and now its about as fast as it gets. I'm not sure what the O() time is, but at least it doesn't take days to run anymore, except for the very "hard" problems.
There's a very important fact to remember: That the "naive" way of making change isn't always the best way! What does this mean? This means that the following algorithm isn't always correct. The naive algorithm is "greedy" with respect to high valued coins, and will choose a single high valued coin, even when lower valued coins will result in smaller overall numbers of coins. See the solution for places that violate the "naive" algorithm.
Here's a link to the C++ source code
Also, one has to consider "bills" when looking at change values greater than 100 cents. I set my "Bill Threshold" to 100 cents. On the solutions page, you can see what values were chosen for change amounts of 1000 and 10000 cents.