# Latest content was relocated to https://bintanvictor.wordpress.com. This old blog will be shutdown soon.

## Thursday, June 14, 2012

### change-making problem

Q: You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 10 + 10 + 1 + 1 + 1 + 1 (6 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.

I feel this is more of a math (dymanic programming) puzzle than an algorithm puzzle. I feel if we can figure out how to optimize for N=4,M=100, then we get a clue. In most currencies, there's a 50c coin, a 10c, 5c. Now, 1c is absolutely necessary to meet the first "trial" and out of the question. Let's start with 50/10/5/1 and see how to improve on it.

First, we need a simple function
map<int, int> findCombo (int target, set<int> coinSet);
For example, findCombo(24, set{1,5,10,25} ) ==  map{10-> 2,  1->4}  Actually this findCombo is a tough comp science problem, but here we assume there's a simple solution.

Now, I will keep the same coinSet and call findCombo 100 times with target = 1,...100. We will then blindly aggregate all the maps. We need to minimize the total coins. (That total/100 would be the average we want to minimize.)

Now, the Impossibly Bad coinset would include just a single denomination of {1c}, violating the rule of N distinct denominations. Nevertheless, this coinset would give a total count of 1+2+3+...+100 = 5050. Let's assume the cost of manufacturing each big or small coin is identical, so that 5050 translates to the Impossibly Bad (IB) cost of \$5050. Each legal coinset would give a saving off the IB cost level of \$5050. We want to maximize that saving.

If we get to use a 25c once among the 100 trials, we save \$24; if we get to use a 10c once, we save \$9. If we use a poor coin set of {1c2c3c4c}, then the saving can only be \$1, \$2 or \$3 each time.