Asp Forum - Re: [QUIZ] Making Change (#154

James Koppel

1/29/2008 4:38:00 AM

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.yaho...

comp.lang.ruby

Re: [QUIZ] Making Change (#154

James Koppel

x Login to ForumsZone