make_change.rb

def make_change amount, coins = [1,2,5,10,20,50,100,200]
  tree = Hash[coins.zip(coins)]
  while tree[amount].nil? do
    tree.keys.each do |value|
      coins.each {|coin| tree[value + coin] ||= coin}
    end
  end
  
  deep = lambda{|a| (coin = tree[a]) ? [coin] + deep[a - coin] : []}
  deep[amount].sort.reverse
end

make_change_test.rb

require "./make_change"
require "test/unit"
require "timeout"

class ChangeTest < Test::Unit::TestCase
  def test_default_notes
    assert_equal [100], make_change(100)
    assert_equal [100, 10, 2], make_change(112)
    assert_equal [200,200,200,200,100,50,20,10,2,2], make_change(984)
  end
 
  def test_custom_notes
    assert_equal [7,7,1], make_change(15, [10,7,1])
    assert_equal [7,7], make_change(14, [10,7,1])
    assert_equal [10,7,7], make_change(24, [10,7,1])
    assert_equal [10,1,1,1], make_change(13, [10,7,1])
  end
 
  def test_performance
    Timeout::timeout(10) do
      assert_equal [200,200,200,200,200,200,200,200,200,100,50,20,10,2,2], make_change(1984)
      assert_equal [1_000_000_000,1], make_change(1_000_000_001, [1_000_000_000,1])
    end
  end
  
  def test_hardcore_performance
    Timeout::timeout(10) do
      assert_equal [1_000_000_000] * 3 + [1_000_000] * 3 + [1] * 9,
        make_change(3_003_000_009, [1_000_000_000, 1_000_000, 1_000, 1])
      assert_equal(2980, make_change(2980, [595, 485, 370, 332, 287, 236, 145, 138, 121, 6]).reduce(:+))
    end
  end
end