This reminds me of the knapsack problem. The first time I solved it it took hours and ~50 loc and only worked for American coins. The second time it took 2 LoC and a minute.