Problems? Is your data what you think it is? PerlMonks

### 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 the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2020-03-29 17:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
To "Disagree to disagree" means to:

Results (171 votes). Check out past polls.

Notices?