From: Niklas Frykholm <r2d2@...>
Date: 2001-08-02T00:23:49+09:00
Subject: [ruby-talk:18967] Re: Who can count change??

(Writing a program that returns the number of ways to make change for a
certain ammount.)

> Well it's not much but here is my attempt. I gave up on it since it didn't
> seem like anyone was interested in pursuing it any further. It can calculate
> the number of possiblities for $100 in 1 hour 23 min.
> ...

Here is my variant. It does $100 in 2.5s, $1000 in 31.2 s and
$10000 in 343s without any precomputation. (Time is approximately linear
in the ammount.)

It is built on a recursive algorithm which can be found at
http://www.telospub.com/journal/MIER/Piele/Vol6No1/Piele613.html

To run fast it uses a buffer to store the computed values and uses an
iterative rather than recursive algorithm. To reduce the memory requirements
and the garbage collection/thrashing, the buffer does not store all values,
but only the last 10001 ones (fewer if we ask for change for a smaller
ammount than $100).


COINS = [1,5,10,25,50,100,200,500,1000,2000,5000,10000]

def ways(sum)
	used_coins = COINS.find_all {|c| c<=sum}
	buffer_size = used_coins.max + 1

	buffer = [Array.new(buffer_size,1)]
	(used_coins.size-1).times {buffer << Array.new(buffer_size,0)}

	0.upto(sum) do |value|
		1.upto(used_coins.length-1) do |used|
			i = value % buffer_size
			buffer[used][i] = buffer[used-1][i] +
				buffer[used][(value-used_coins[used])%buffer_size]
		end
	end
	return buffer[used_coins.size-1][sum % buffer_size]
end

ARGV.each {|x| puts ways(x.to_i)}


// Niklas