Coin Change, Part 2
May 21, 2013
We start by noting that the greedy algorithm doesn’t work, in general. If you’re target is 30 and the available coins are 1, 10 and 25, the greedy algorithm requires 6 coins (25 1 1 1 1 1) but the proper solution requires 3 coins (10 10 10). The greedy solution does work for U.S. coins, however; given coins 1, 5, 10 and 25, the greedy algorithm finds the proper solution (25 5) that requires 2 coins.
We’ll give the classic O(kn) algorithm, where k is the number of distinct coin denominations; there is also an O(n) algorithm similar to the one of the previous exercise. The idea is to build a k by n matrix with one row per coin denomination and one column per target that contains the minimum number (or list) of coins of denominations of the current row or the rows above that are required to make the total in the given column. For our sample target of 40 using coins of 1, 5, 10 and 25, the matrix looks like this:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
5 0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 6 7 8 9 10 7 8 9 10 11 8
10 0 1 2 3 4 1 2 3 4 5 1 2 3 4 5 2 3 4 5 6 2 3 4 5 6 3 4 5 6 7 3 4 5 6 7 4 5 6 7 8 4
25 0 1 2 3 4 1 2 3 4 5 1 2 3 4 5 2 3 4 5 6 2 3 4 5 6 1 2 3 4 5 2 3 4 5 6 2 3 4 5 6 3
The table entry tells the number of coins required to make the given total using only the available coins. For instance, in the third row, the available coins have denominations 1, 5 and 10 and a target of 18 requires 5 coins (10 5 1 1 1). The solution is in the lower-right corner: to make a total of 40 requires at minimum 3 coins (25 10 5) from the set 1, 5, 10 and 25.
The values in the matrix, which is traditionally called C with rows i and columns j, are filled left-to-right, top-to-bottom using the following algorithm:
C[i,j] is C[i-1,j] if j < coin[i] or min(C[i-1,j], 1+C[i,j–coin[i]]) otherwise. In the limit, when i = 0 and coin[0] = 1, C[0,j] is j.
Note that we assume the smallest coin always has denomination 1, since otherwise there would be no way to make all possible targets. Here’s the program that computes the minimum count of coins:
(define (count coins n)
(let* ((k (vector-length coins))
(c (make-matrix k (+ n 1) 0)))
(do ((j 0 (+ j 1))) ((< n j))
(matrix-set! c 0 j j))
(do ((i 1 (+ i 1))) ((= i k))
(do ((j 1 (+ j 1))) ((< n j))
(matrix-set! c i j
(if (< j (vector-ref coins i))
(matrix-ref c (- i 1) j)
(min (matrix-ref c (- i 1) j)
(+ 1 (matrix-ref c i
(- j (vector-ref coins i)))))))))
(matrix-ref c (- k 1) n)))
We can determine which coins make up the solution by inspecting the matrix, starting at the lower-right corner. If the matrix value is the same as the one above, move up, because the value in the cell was calculated to be the same as the cell above. Otherwise, emit the current coin and move left in the matrix the same value as the coin. Stop when you get to the upper-left corner. In the case of our example, the value at the lower-right corner, 3, is different than the value above, 4, so emit a 25-cent coin and move twenty-five left to C[25,15]. The value there is the same as the value above, 2, so move up. Then the value differs from the value above, 2 compared to 3, so emit a 10-cent coin and move ten left to C[10,5]. The value there is the same as the value above, 1, so move up to C[5,5]. Now the value differs from the value above, 1 compared to 5, so emit a 5-cent coin and move five left to C[0,5]. The value there is the same as the value above, 0, so move up. And quit, since we’re at the upper-left corner.
(define (coins cs n)
(let* ((k (vector-length cs))
(c (make-matrix k (+ n 1) 0)))
(do ((j 0 (+ j 1))) ((< n j))
(matrix-set! c 0 j j))
(do ((i 1 (+ i 1))) ((= i k))
(do ((j 1 (+ j 1))) ((< n j))
(matrix-set! c i j
(if (< j (vector-ref cs i))
(matrix-ref c (- i 1) j)
(min (matrix-ref c (- i 1) j)
(+ 1 (matrix-ref c i
(- j (vector-ref cs i)))))))))
(let loop ((i (- k 1)) (j n) (zs (list)))
(cond ((and (zero? i) (zero? j)) zs)
((zero? i) (loop i (- j 1) (cons 1 zs)))
((= (matrix-ref c i j) (matrix-ref c (- i 1) j))
(loop (- i 1) j zs))
(else (loop i (- j (vector-ref cs i))
(cons (vector-ref cs i) zs)))))))
Here are some examples:
> (count '#(1 5 10 25) 40)
3
> (coins '#(1 5 10 25) 40)
(5 10 25)
We used the matrix procedures from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/NeueOC2I.
Programming Praxis 
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
#!/usr/bin/env ruby # coin-change2.rb # # find the smallest number of coins (pennies, nickles, dimes, quarters) that # add to a specific total # # Find the numbers that fulfill the polynomial: total = P + N*5 + D*10 * Q*25 # # A "coin set" is a 4-tuple of [P,N,D,Q] # $coin_values = [ 1, 5, 10, 25 ] # given a total, find the maximum number of coins for each # denomination def compute_max_coins(total) max_coins = $coin_values.map {|value| Integer(total / value)} $max_pennies = max_coins[0] $max_nickles = max_coins[1] $max_dimes = max_coins[2] $max_quarters = max_coins[3] end # get all the coin sets for a given total def get_coin_sets(total) coin_sets = [] (0..$max_quarters).each { |q| break if total < q*25 qtotal = total - q*25 (0..$max_dimes).each { |d| break if qtotal < d*10 dtotal = qtotal - d*10 (0..$max_nickles).each { |n| break if dtotal < n*5 p = dtotal - n*5 coin_sets += [[q,d,n,p]] } } } coin_sets end class Array def sum self.reduce(:+) end end def compare(a,b) a == b ? 0 : a < b ? -1 : 1 end if ARGV.size > 0 total = ARGV.shift.to_i else total = 40 end compute_max_coins(total) coin_sets = get_coin_sets(total) shortest_coin_set = coin_sets.sort!{|a,b| compare(a.sum, b.sum)}.first puts "For total = #{total}" puts "There are #{coin_sets.size} sets of coins" set = 1 printf "Set $.25 $.10 $.05 $.01 Coins\n" coin_sets.each do |q,d,n,p| printf "%3d: %4d %4d %4d %4d %5d\n", set, q, d, n, p, [q,d,n,p].sum set += 1 end printf "The smallest coin set has %d coins: %s\n", shortest_coin_set.sum, shortest_coin_set.join(", ") exitHere 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:
(def best-pay (memoize (fn [coins amt] (if (zero? amt) [] (let [cand (for [c (filter #(<= % amt) coins)] (when-let [r (best-pay (filter #(<= % c) coins) (- amt c))] (conj r c))) res (filter identity cand)] (when (seq res) (apply min-key count res)))))))This Python version returns the minimum number of coins and the change.
import sys inf = sys.maxint def min_coins(coins, amount): """return number of coins, list of coins""" C = [0] + [inf] * amount S = [0] + [None] * amount for p in range(1, amount + 1): for c in coins: if c <= p and C[p - c] + 1 < C[p]: C[p] = C[p - c] + 1 S[p] = c mincoins = [] ind = -1 while S[ind]: mincoins.append(S[ind]) ind -= S[ind] return C[-1], mincoinsIn 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 […]