No really. Look. (holds out hand for you to see)

I have three Quarters, four dimes, and four pennies.

This all adds up to $1.19, you can't make change for a dollar, however this is the largest amount of money you can have in change without being able to make change for a dollar. So at least there is something good about my situation.

In the UK, we can have up to £1.43 in regular coinage without being able to "make change" for a pound: 50, 20, 20, 20, 20, 5, 2, 2, 2, 2.

Of course, this ignores the fact that we have the two pound coin which allows one to have an infinite amount of money without being able to change a pound. Thanks to heyoka for pointing this out.

There must be a neat algorithm or process for determining the largest amount of sub-unit given a set of available denominations, but it's too near the weekend for me to think about.

Alright, I've had too much caffeine, let's try to make an algorithm. (Thanks to everyone who pointed out that it's an algorithm, not a logarithm.)

First step seems like you'd take the largest possible number of your largest subunit that adds up to less than the target.

Second, take your next largest subunit and add the largest possible amount that doesn't add up to the target when combined with any possible quantity of the largest subunit.

Then, repeat for each successively smaller subunit, but comparing each one to every possible permutation of quantities of the larger subunits.

Sounds simple to do in your head, but like a pain in the rear to code. So let's write a Perl script to do it. Forgive this for being ugly, but I'm really too wired to be doing this right now. (This defaults to the US test case, you can switch the commenting on the two "my @subunits" lines for the UK test case, or play with $target and $subunits for fun, as long as the assumptions at the top hold true.) Yes, this works. You might have to change the first line if your perl isn't in /usr/bin/perl.

(Thanks to e-troon for pointing out I missed a couple of UK coins in the first version. They don't effect the output unless you change the target.)

#!/usr/bin/perl -w
#
# Assumptions:
# $target is amount to subdivide, integer
# @subunits is a list of all possible subunits, all
#   integers, in order from largest to smallest
# $target is even divisble by every item in @subunits

my $target = 100;
my @subunits = (25, 10, 5, 1); # Standard US coins
#my @subunits = (50, 20, 10, 5, 2, 1); # Standard UK coins

my %units_so_far;
my @permutations = (0);

foreach $unit (@subunits) {
  my $highestquantity = $target / $unit;
  foreach $perm (@permutations) {
    QLOOP: for $quantity (1 .. $highestquantity) {
      if ($unit * $quantity + $perm == $target) {
        $highestquantity = $quantity - 1;
        last QLOOP;
      }
    }
  }
  my @newperms = @permutations;
  if ($highestquantity) {
    foreach $perm (@permutations) {
      for (1 .. $highestquantity) {
        push @newperms, $_ * $unit + $perm;
      }
    }
  }
  @permutations = @newperms;
  $units_so_far{$unit} = $highestquantity;
}

my $outbuff = "";
my $total = 0;
foreach (keys(%units_so_far)) {
  $total += $_ * $units_so_far{$_};
  if ($units_so_far{$_}) {
    $outbuff .=  "$units_so_far{$_} of denomination $_, ";
  }
}
print "You can have up to $total without making change for $target.\n";
print "(That's " . $outbuff . "if you care.)\n";

10/31/2001: Addendum: Yes, if you add 3 or 200 (or any other quantity that $target won't divide evenly into) to the subunits list, this program will happily use all your CPU power and memory until you kill it or your system crashes, in attempt to calculate infinity in a rather inefficient manner.

Log in or register to write something here or to contact authors.