From: Denis Hennessy <denis@...>
Date: 2008-01-28T01:26:58+09:00
Subject: Re: [QUIZ] Making Change (#154)

Here's my submission to the making change quiz.  As Paolo mentioned,  
this is the Knapsack problem which means that finding the absolute  
optimal answer can be extremely expensive. One way of thinking of the  
problem is as an N-dimensional search problem, where N is the number  
of coins available. The key is to limit the variance in each dimension  
to restrict the search space.

We start with a list of coins: [C0, C1, ... Cn) and must end up with a  
count for each coin such that

V = X0C0 + X1C1 + ... + XnCn

The counts all have to be positive and V has to match the target value  
supplied by the user. It's possible that there's no set of counts that  
will produce a correct answer. The 'best' answer is the one that  
contains the least number of coins.

My approach is to take each coin in turn and vary it between a lower  
bound and an upper bound. For each count, I try to match the value  
with the remaining coins. In order to minimise the search space as  
much as possible, I compute the bounds as follows:

For the lower bound, first I compute the least common multiple of the  
coin and the higher value coins (taking the largest one that won't put  
be over the value), and then use the highest multiple of that which is  
less than the value.

For example, if the problem is make_change(75, [30, 5, 1]) and I'm  
varying '5', then the lcm of 5 and [30] is 30 and the lower bound is 60.

Then I compute the same thing for the lower value coins except that I  
combine all of them (giving me the smallest number whereby changing  
lower value coins can no longer improve the solution). The best of  
these two bounds is used as the lower bound.

The upper bound is the highest count of the coin which is still below  
the target value.

In each iteration, I recursively call make_change with the remaining  
value and coins.

Here's a couple of runs with logging to show the effect. Notice that  
in both cases, it doesn't waste time trying permutations of '2' and  
'1' that could not produce a better result.

$ ruby -v make_change.rb 1000001 1000000 2 1
ruby 1.8.6 (2007-09-23 patchlevel 110) [powerpc-darwin9.0.0]
make_change 1000001, [1000000, 2, 1]
make_change 1, [2, 1]
make_change 1, [1]
make_change 1, [1000000, 1]
make_change 1, [1]
[1000000, 1]

$ ruby -v make_change.rb 1000001 1000000 999999 2
ruby 1.8.6 (2007-09-23 patchlevel 110) [powerpc-darwin9.0.0]
make_change 1000001, [1000000, 999999, 2]
make_change 1000001, [999999, 2]
make_change 1000001, [2]
make_change 2, [2]
make_change 1, [999999]
make_change 1, [999999, 2]
make_change 1, [2]
make_change 1, [999999]
make_change 1000001, [1000000, 2]
make_change 1, [2]
make_change 1, [1000000]
make_change 2, [1000000, 2]
make_change 2, [2]
make_change 1, [1000000, 999999]
make_change 1, [999999]
make_change 1, [1000000]
[999999, 2]

/dh

make_change.rb:
#!/usr/bin/env ruby

def greatest_common_divisor(a, b)
   return a if b == 0
   greatest_common_divisor(b, a % b)
end

def least_common_multiple(a, b)
   return 0 if a == 0 or b == 0
   (a * b) / greatest_common_divisor(a, b)
end

def make_change(value, coins=[])
   return [] if value == 0
   return nil if coins.empty?

   puts "make_change #{value}, #{coins.inspect}" if $VERBOSE

   best = nil
   coins.each_with_index do |c, i|
     lcm = coins[0,i].inject(0) { |memo, val| lcm =  
least_common_multiple(c, val); lcm > memo && lcm <= value ? lcm : memo}
     start = lcm == 0 ? 0 : (value - (value % lcm)) / c
     lcm = coins[i+1,coins.size].inject(c) { |memo, val|  
least_common_multiple(memo, val)}
     if lcm != 0
       try = (value - (value % lcm)) / c
       start = try if try > start && try <= value
     end
     max = value / c
     others = coins.reject {|v| v == c}
     start = max if others.empty?
     start.upto(max) do |n|
       remaining = value - n * c
       change = make_change(remaining, others)
       next if change == nil
       try = [c] * n + change
       best = try if best.nil? or try.size < best.size
     end
   end
   best.sort!.reverse! if best
   best
end

if $0 == __FILE__
   if ARGV.size == 0
     puts "Usage: #{File.basename($PROGRAM_NAME)} <value> <coin>  
<coin>..."
     exit
   end
   value = ARGV.shift.to_i
   coins = ARGV.collect {|c| c.to_i}
   coins.sort!.reverse!

   change = make_change value, coins
   if change
     puts change.inspect
   else
     puts "It's not possible to make #{value} with coins of value  
#{coins.inspect}"
   end
end