## Coin Change, Part 2

### May 21, 2013

In the previous exercise we studied the classic coin change problem to find all the ways to make a given amount of change using a given set of coins. Sometimes the problem in a different way: find the minimum set of coins needed to make a given amount of change. As with the prior exercise, sometimes the task is to find just the count and sometimes the task is to find the actual set of coins.

Your task is to write the two programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here is a Ruby solution to find the fewest number of coins adding to a given total:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

coin-change2.rb output

hosted with ❤ by GitHub

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

gistfile1.rb

hosted with ❤ by GitHub

Here is the output:

Of course, a more optimal solution is to just use the maximum value of each coin count (where the coin value * coin count is still less than the current total). Exercise left to others.. :-)

As a note, the matrix solution is very similar in behavior to a recursive solution with memoization (as it is in general for most dynamic programming), and I usually prefer the recursive formulation.

In clojure:

This Python version returns the minimum number of coins and the change.

In this case you can use a greedy algorithm, as aks said: keep selecting the largest coin possible until you reach your target change.

[…] solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be used to […]