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.