I need to find the most optimal combination of coins that makes up a certain dollar amount. So essentially, I want to use the least amount of coins to get there.
For example:
if a currency system has the coins: {13, 8, 1}, the greedy solution would make change for 24 as {13, 8, 1, 1, 1}, but the true optimal solution is {8, 8, 8}.
I am looking to write this in Javascript, but pseudocode is fine as I'm sure that would help more people.
In general, the problem is actually NP-complete (see Change-making problem). However, for many currency systems (including the US system of {1, 5, 10, 25} ), the greedy algorithm also happens to be optimal.