--Boundary-00rKnHbXcKwOd0/F
Content-Type: Multipart/Mixed;
  boundaryoundary-00rKnHbXcKwOd0/F"

--Boundary-00rKnHbXcKwOd0/F
Content-Type: text/plain;
  charsettf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Here's my solution, attached and pastied here:
http://pastie.caboo.se/pastes/144060

Its recursive, can solve the simplest problems, but soon gets overwhelmed by 
cases like Yoan's Swiss money test. I killed it after 12 hours. Solutions are 
stored as hashes of coin-value count (if you want it in the array form its 
easy to convert - see line 59). Its also accepts a score function, and so can 
do things like:

jesse@ricercar $ ./make_change.rb 21 1 7 10 least
0 of 1-coins
3 of 7-coins
0 of 10-coins
3 total
jesse@ricercar $ ./make_change.rb 21 1 7 10 variety
4 of 1-coins
1 of 7-coins
1 of 10-coins
6 total
jesse@ricercar $ ./make_change.rb 21 1 7 10 most
21 of 1-coins
0 of 7-coins
0 of 10-coins
21 total

I played around with a few optimizations, like storing the coins array once 
and passing indices instead of duplicating it on line 18, but they hardly 
made a difference.

-Jesse

--Boundary-00rKnHbXcKwOd0/F
Content-Type: application/x-ruby;
  nameake_change.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filenameake_change.rb"

#!/usr/bin/env ruby
# Ruby Quiz 154: Making Change
# Score-function-general solution.
# Jesse Merriman

Infinity  .0 / 0

module Enumerable
  def sum; inject { |sum, x| sum + x }; end
end

LeastCoins  ambda { |sol| - sol.values.sum }
MostCoins   ambda { |sol| sol.values.sum }
Variety     ambda { |sol| sol.values.select { |v| v > 0 }.size }

def make_change amount, coins  25, 10, 5, 1], scorer  eastCoins
  pick  oins.first
  others  oins[1..-1]

  if coins.size 1
    return (amount % pick).zero? ? {pick amount / pick} : nil
  end

  best_so_far  :sol nil, :score -Infinity}

  (0 .. amount / pick).each do |count|
    sol  ake_change amount - count * pick, others, scorer

    if not sol.nil?
      sol[pick]  ount
      s  corer[sol]
      if s > best_so_far[:score]
        best_so_far[:sol]  ol
        best_so_far[:score]  
      end
    end
  end

  best_so_far[:sol]
end

if $0 __FILE__
  amount  RGV.first.to_i
  coins  RGV[1..-2].map { |x| x.to_i }
  scorer  ase ARGV.last
    when /most/i    then MostCoins
    when /variety/i then Variety
    else LeastCoins
  end

  sol  ake_change amount, coins, scorer
  if sol.nil?
    puts 'No solution could be found.'
  else
    sol.each do |coin, count|
      puts "#{count} of #{coin}-coins"
    end
    puts "#{sol.values.sum} total"
    #sol.to_a.map { |x| [x.first] * x.last }.flatten
  end
end


--Boundary-00rKnHbXcKwOd0/F--
--Boundary-00rKnHbXcKwOd0/F--