# Re: Making Change (#154)

**URL:** <https://www.ruby-forum.com/t/re-making-change-154/127435>\
**Category:** Ruby\
**Created:** [January 29, 2008, 5:39am UTC](https://www.ruby-forum.com/t/re-making-change-154/127435 "2008-01-29T05:39:14Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [January 29, 2008, 5:39am UTC](https://www.ruby-forum.com/t/re-making-change-154/127435/1 "2008-01-29T05:39:14Z")

</div>

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](http://www.yahoo.com/r/hs)