in reply to puzzle: how many ways to make $100
You're looking for the Greedy Algorithm. It's basically the reverse from your approach: you start out with the highest denomination, then decrease that and spread the difference among the lower denominations.
Here's one link: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro.htm
I dug up my solution to problem 31 on Project Euler.
#!/usr/bin/perl
use List::Util qw/ sum /;
@w = ( 1, 2, 5, 10, 20, 50, 100 );
$S = 100;
$found = 0;
@c = ( 0, 0, 0, 0, 0, 0, 1 );
partition( $S, @c );
print "$/Total found: $found$/";
sub partition {
my ( $s, @c ) = @_;
while(1) {
# exact change
$found++ if $s  amount( \@c, \@w ) == 0;
# last match
return if $c[0] == $s;
# decrement first nonzero
my $i = 0;
$i++ while $c[$i] == 0;
$i == 0 ? $c[0] = 0 : $c[$i];
@c[ 0 .. $i  1 ] = (0) x $i;
# and redistribute difference
for my $j ( reverse 0 .. $i  1 ) {
my $Dj = $s  amount( \@c, \@w );
$c[$j] = int( $Dj / $w[$j] );
}
}
}
sub amount {
my ( $x, $y ) = @_;
return sum map { $x>[$_] * $y>[$_] } 0 .. $#$x;
}
It could use some refactoring, but I was in a hurry and I didn't write it for public consumption ;)
Update: Oh right, yes, output... I get Total found: 4563.
