Perl: the Markov chain saw PerlMonks

### Re: The greedy change-making problem using regexes

by tall_man (Parson)
 on Mar 10, 2005 at 22:22 UTC ( #438443=note: print w/replies, xml ) Need Help??

What about implementing David Pearson's algorithm instead? It will find the smallest counterexample in polynomial time O(N^3) when N is the number of coins.

Determining whether or not a given coin system can be done by the greedy algorithm is not NP-complete. Finding optimum change in a given coin system that does not allow the greedy algorithm is NP-complete.

It looks quite easy to implement. I will try it when I get a chance.

Update: Code added below. Update2: Rewrote greedy_change with a simple loop instead of the regular expression one I borrowed from AnonyMonk.

```use strict;
use warnings;

sub greedy_change {
my \$change = shift;
my @coins  = @_;

my @result;
for my \$i (0..\$#coins) {
my \$val = int(\$change/\$coins[\$i]);
\$change -= \$val*\$coins[\$i];
push @result,\$val;
}
return @result;
}

+
+
+
sub pearson_counterexample {
my \$i = shift;
my \$j = shift;
my @coins  = @_;

+
# Let position \$i be the highest coin used,
# Let positon \$j be the lowest.  Then the
# potential counterexample will be:
#   1) Compute the greedy change for the
#      next highest coins value - 1.
#
#   2) Copy all coin counts from 0 to \$j-1
#
#   3) Add one to the coin count at position \$j.
#
# If this combination is more efficient than
# the greedy value, we have a counterexample.

+
my \$value = \$coins[\$i-1] - 1;
my @greedy = greedy_change(\$value, @coins);
my @example = (0) x @coins;
\$example[\$_] = \$greedy[\$_] for (0..\$j-1);
\$example[\$j] = \$greedy[\$j]+1;

+
# Compute the numeric value and see if it
# represents the amount more efficiently
# than the greedy way.
my \$example_value = 0;
\$example_value += \$coins[\$_]*\$example[\$_] for (0..\$#example);
@greedy = greedy_change(\$example_value, @coins);
my (\$example_count, \$greedy_count);
\$example_count += \$example[\$_] for (0..\$#example);
\$greedy_count += \$greedy[\$_] for (0..\$#greedy);

+
# This candidate case did not work.
return if \$example_count >= \$greedy_count;
return @example;
}

+
# Read the coin system from the command line, in
# decreasing order of size.
my @coins = @ARGV;
if (@coins < 3) {
print "Must have a least three coins\n";
exit(1);
}
my (\$i,\$j);
my \$found = 0;

+
EXAMPLES:
for (\$i = 1; \$i < @coins; ++\$i) {
for (\$j = \$i; \$j < @coins; ++\$j) {
my @example = pearson_counterexample(\$i, \$j, @coins);
if (@example) {
print "Counterexample: ",join(" ",@example),"\n";
\$found = 1;
last EXAMPLES;
}
}
}

+
print "No counterexamples found.  Good coin system\n" unless \$found;
[download]```

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://438443]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (5)
As of 2017-11-24 03:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In order to be able to say "I know Perl", you must have:

Results (343 votes). Check out past polls.

Notices?