Determine the optimal combination of coins for a dollar amount

Question

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.

Answer 1

This problem screams dynamic programming.

The basic pseudo code should be something like so:

• Let C(n) be the minimal number of coins used to sum to n.
• At each recursive step, find the next maximal value coin, c, and choose C(n) to be:
• the minimum value between C(n-c)+1 (using said coin, updating the total coins used, and the remaining value) and C(n) (not using the coin) - in both cases removing c from the available coin list for the next iteration.

Note that this algorithm would be good for the general case you are referring to. For any other coin system that each coin is a divisor of the one after it (most coin systems in the world) - the greedy solution is the easiest, and is optimal.

Answer 2

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.