go ahead... be a heretic PerlMonks

### comment on

 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;

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2020-10-24 18:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite web site is:

Results (246 votes). Check out past polls.

Notices?