From: "Martin Lüdtke" <martin_luedtke@...>
Date: 2008-01-28T07:00:05+09:00
Subject: Re: Making Change (#154)

def make_change(amount, coins = [25, 10, 5, 1])
  change = { 0 => [] }
  until change.has_key?(amount)
    new_change = {}
    change.each do |amt, chg|
      coins.each { |c| new_change[amt + c] = [c] + chg unless
          amt + c > amount or change.has_key?(amt + c) }
    end
    return nil if new_change.empty?
    change.merge!(new_change)
  end
  change[amount].sort.reverse
end

-------------------

We begin with the simplest known solution (0 => []). Now for each
known solution and for each coin we get new solutions by just adding
the coin. This is repeated until we get a solution for the given
amount. If we don't find any new solutions (new_change.empty?) there
isn't any, so we return just nil.