find the smallest number of coins (pennies, nickles, dimes, quarters) that add to a specific total

coin-change2.rb 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

gistfile1.rb

#!/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