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