From: Sander Land <sander.land@...>
Date: 2008-01-28T02:42:29+09:00
Subject: Re: [QUIZ] Making Change (#154)

Here's my very simple recursive solution. It has a cache though, so
it's O(coins.size * amount) like the standard knapsack algorithm.

def make_change(amount, coins = [25, 10, 5, 1])
  r = Hash.new{|h,k|
    h[k] = k<0 ? [1/0.0,[]] : coins.map{|c| l=h[k-c]; [l[0]+1,l[1]+[c]] }.min
  }.merge(0=>[0,[]])[amount]
  r[1] if r[0].to_f.finite?
end