### Re: puzzle: how many ways to make \$100

by rhesa (Vicar)
 on Apr 29, 2006 at 00:21 UTC ( #546445=note: print w/replies, xml ) Need Help??

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.

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 non-zero 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.

Create A New User
Node Status?
node history
Node Type: note [id://546445]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (3)
As of 2018-01-18 20:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (214 votes). Check out past polls.

Notices?