```On 1/25/08, Ruby Quiz <james / grayproductions.net> wrote:
> This week's Ruby Quiz is to complete a change making function with this
> skeleton:
>
>        def make_change(amount, coins = [25, 10, 5, 1])
>
> Your function should always return the optimal change with optimal being the
> least amount of coins involved.  You can assume you have an infinite number of
> coins to work with.

Here's my somewhat simplisitc solution.  I just work upwards through
progressively larger sets of coins until I find one that works.  I
think the only interesting part is that you can select what to do when
there is no exact match.

#select what to do when can't make exact change
STRATEGY=[:RoundDown,:RoundUp,:Refuse]

class Array
def sum
inject(0){|s,v|s+v}
end
end

def minimum_change coins,strategy
case STRATEGY
when :RoundDown
0
when :RoundUp
coins
when :Refuse
nil
end
end

#make amount of change with the fewest possible coins
#
# iterate through progressively larger sets of coins
# until you find a set that adds up to amount,
def make_change(amount, coins = [25, 10, 5, 1])
change = Array.new(amount+1)
coins=coins.sort
#handle cases where change is less than smallest coin
return [minimum_change(coins,STRATEGY)] if amount < coins
#initial sets are one coin
sets = coins.map{|c|[c]}
loop do
sets.each{|set|
return set.reverse if set.sum==amount
#  record the first set to match each sum  (incase we can't make
exact change)
change[set.sum]||=set
}
#generate more sets by adding 1 of each coin to existing sets
#only keep unique sums smaller than target amount.
sets = sets.inject([]){|result,set|
newsets=coins.map{|c|(set+[c]).sort}.find_all{|s|s.sum<=amount }
result+newsets
}.uniq
#if we can't make exact change, reduce amount until we can
if sets.empty?
amount -=1 until change[amount]
#use STRATEGY to round up or down
minchange=minimum_change(coins,STRATEGY)
return (change[amount].reverse<<minchange)- if minchange
return minchange
end
end
end

```