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.

Posted by programmingpraxis

Filed in Exercises

6 Comments »

6 Responses to “Coin Change, Part 2”

aks said

May 21, 2013 at 4:44 PM

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

	$ ./coin-change2.rb
	For total = 40
	There are 31 sets of coins
	Set $.25 $.10 $.05 $.01 Coins
	1: 1 1 1 0 3
	2: 1 0 3 0 4
	3: 0 4 0 0 4
	4: 0 3 2 0 5
	5: 0 2 4 0 6
	6: 1 1 0 5 7
	7: 0 1 6 0 7
	8: 1 0 2 5 8
	9: 0 0 8 0 8
	10: 0 3 1 5 9
	11: 0 2 3 5 10
	12: 0 1 5 5 11
	13: 0 0 7 5 12
	14: 1 0 1 10 12
	15: 0 3 0 10 13
	16: 0 2 2 10 14
	17: 0 1 4 10 15
	18: 0 0 6 10 16
	19: 1 0 0 15 16
	20: 0 2 1 15 18
	21: 0 1 3 15 19
	22: 0 0 5 15 20
	23: 0 2 0 20 22
	24: 0 1 2 20 23
	25: 0 0 4 20 24
	26: 0 1 1 25 27
	27: 0 0 3 25 28
	28: 0 1 0 30 31
	29: 0 0 2 30 32
	30: 0 0 1 35 36
	31: 0 0 0 40 40
	The smallest coin set has 3 coins: 1, 1, 1, 0

view raw

coin-change2.rb output

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 + N5 + D10 * 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(", ")
	exit

view raw

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(", ")
exit

Here is the output:

$ ./coin-change2.rb                                                                               
For total = 40
There are 31 sets of coins
Set  $.25  $.10  $.05  $.01  Coins
  1:    1     1     1     0      3
  2:    1     0     3     0      4
  3:    0     4     0     0      4
  4:    0     3     2     0      5
  5:    0     2     4     0      6
  6:    1     1     0     5      7
  7:    0     1     6     0      7
  8:    1     0     2     5      8
  9:    0     0     8     0      8
 10:    0     3     1     5      9
 11:    0     2     3     5     10
 12:    0     1     5     5     11
 13:    0     0     7     5     12
 14:    1     0     1    10     12
 15:    0     3     0    10     13
 16:    0     2     2    10     14
 17:    0     1     4    10     15
 18:    0     0     6    10     16
 19:    1     0     0    15     16
 20:    0     2     1    15     18
 21:    0     1     3    15     19
 22:    0     0     5    15     20
 23:    0     2     0    20     22
 24:    0     1     2    20     23
 25:    0     0     4    20     24
 26:    0     1     1    25     27
 27:    0     0     3    25     28
 28:    0     1     0    30     31
 29:    0     0     2    30     32
 30:    0     0     1    35     36
 31:    0     0     0    40     40
The smallest coin set has 3 coins: 1, 1, 1, 0

aks said
May 21, 2013 at 4:46 PM
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.. :-)

Colin said

May 22, 2013 at 3:13 AM

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)))))))

Paul said

May 24, 2013 at 8:30 AM

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], mincoins

brooknovak said
June 11, 2013 at 10:15 AM
In this case you can use a greedy algorithm, as aks said: keep selecting the largest coin possible until you reach your target change.
Modified Coin Change | Programming Praxis said
November 19, 2019 at 10:00 AM
[…] 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 […]

Programming Praxis