My solution uses a queue of combinations of coins. In the basic algorithm, in each iteration, it dequeues the first element, creates a new combination combining it with one of each type of coin (i.e.: the Cartesian product of the set containing just the combination and the set of coins), and then inserts the new combination into the queue unless the sum is too large. When it encounters a combination whose sum equals amount, it saves that combination if it's smaller than the previous optimal combination or if the previous optimal combination is nil.

Of course, that algorithm would be extremely slow - worse than a brute force search due to redundancies. However, I am employing several major optimizations.

Firstly, there is a min-size heuristic which gives an estimate of how small the children of a certain combination could be by dividing the amount of change left by the largest coin less than that amount. If the ceiling of this number is greater than or equal to the size of an existing solution, it knows immediately that no child of this branch could possibly be an optimal solution, and will prune it out immediately.

Secondly, it is of course faster to evaluate more promising branches first. Each iteration, I sort the queue my a solution-proximity heuristic. At the moment, this heuristic is equal to the amount of change left times the min-size heuristic, although I realized as I was typing this that just the amount of change left might possibly be better.

Thirdly, the algorithm as stated above would have quite a few redundancies, so only coins whose value is less than or equal to the newest coin in a combination are added.

Nevertheless, my solution still can get extremely slow when the number of coins needed is a nontrivial number.

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

def cartesian_product(first, *rest)
  return first if rest == []
  rest = cartesian_product(*rest)
  combs = block_given? ? nil : []
  first.each do |v1|
    rest.each do |v2|
      if block_given?
        yield v1+v2
      else
        combs << (v1 + v2)
      end
    end
  end
  combs
end

Infinity = 1.0/0
#Calculates the minimum amount of coins needed to get the amount,
#if fractions of coins were legal.
def min_size_heuristic(amount,comb,coins)
  rem = amount-comb.sum
  return Infinity if rem < 0
  comb.size+rem.to_f/(coins.select{|c|c<=rem&&c<=comb.max}.max) rescue comb.size
end

#Determines the priority of which combinations of coins to search.
#Multiplies min_size_heuristic by the distance of the amount from the current sum
def solution_proximity_heuristic(amount,comb,coins)
  (amount-comb.sum)*min_size_heuristic(amount,comb,coins)
end

def make_change(amount, coins = [25, 10, 5, 1])
  queue =coins.select{|c|c<=amount}.map{|c|[c]}.sort_by{|comb|
    solution_proximity_heuristic(amount,comb,coins)}
  
  smallest_change = nil
  until queue.empty?
    comb = queue.shift
    if comb.sum == amount
      smallest_change = comb if smallest_change.nil? or comb.size < smallest_change.size
      next
    end
    combs = cartesian_product([comb],coins.select{|c|c<=comb.last}.map{|c|[c]})
    combs.delete_if {|comb| comb.sum > amount ||
      smallest_change != nil && 
        min_size_heuristic(amount,comb,coins).ceil >= smallest_change.size}
    queue = (queue+combs).sort_by{|c|solution_proximity_heuristic(amount,c,coins)}
  end
  smallest_change  
end



      ____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs