Re: making change

This solution acts pretty much the same way humans act: It starts with the big number (the quarters), and once it determines that adding another quarter will put it past the target value, it moves on to the next smaller denomination and tries it. ...at least that's how I do it. ;)

use strict;
use warnings;

my $a_coins = [ 25, 25, 25, 10, 10, 10 , 5, 1, 1, 1, 1 ];
my $wanted = 72;
my @needed = @{ make_change( $a_coins, $wanted ) };
print "@needed = $wanted\n";

sub make_change {
    my( $a_coins, $dest ) = @_;
    my @coins = sort { $b <=> $a } @{ $a_coins };
    my @need;
    my $tally = 0;
    while ( @coins ) {
        my $current = shift @coins;
        next if $tally + $current > $dest;
        $tally += $current;
        push @need, $current;
        return \@need if $tally == $dest;
    }
    shift ( @{$a_coins} );
    @need = @{ make_change( $a_coins, $dest ) };
    my $check=0;
    foreach ( @need ) {
        $check += $_;
    }
    if( $check == $dest ) {
        return \@need;
    } else {
        die "Can't make change.\n";
    }
}
[download]

Updated: I've updated make_change() to use recursion to support cases such as @coins = ( 25, 10, 10, 10 ) and $wanted = 30. Now, if it is found that 25+10 exceeds 30 (which it does), 25 is discarded from the change queue, and the sub is re-run without the quarter getting in the way.

Dave

Comment on Re: making change Select or Download Code

Replies are listed 'Best First'.
OT: making change by Eimi Metamorphoumai (Deacon) on Nov 11, 2004 at 18:07 UTC
Interestingly, that only gives you the smallest number of coins for certain combinations of denominations. For instance, consider making change in a system that didn't have nickles. That is, `$a_coins = [(25) x 4, (10) x 10, (1) x 10]; $wanted = 30;`). Your solution would grab a quarter, and then be stuck with 5 pennies, for a total of 6 coins, where a smarter solution might give three dimes. But for coins in the US system, the greedy algorithm works.	[reply] [d/l]
Re: OT: making change by davido (Cardinal) on Nov 11, 2004 at 18:39 UTC
There is a very interesting article on this subject here: http://www.sciencenews.org/articles/20030510/mathtrek.asp. The article makes a few interesting points. One is that the US coin system would become more efficient (in number of coins needed to provide transaction change) if an 18 cent piece were introduced to replace the dime. Keep the dime, and introduce a 32 cent coin for even greater transaction efficiency. ...though this is going to be harder for your high-school student clerks to add in their heads. It also mentions that the "greedy algorithm" (starting from the largest denomination and working downward) provides the most efficient (in number of coins used) solution for US coin denominations, but isn't guaranteed to do so given the denominations of other countries. Dave	[reply]
Re: OT: making change by Dominus (Parson) on Nov 24, 2004 at 16:16 UTC
Says davido: the US coin system would become more efficient (in number of coins needed to provide transaction change) if an 18 cent piece were introduced to replace the dime. I looked into this in some detail eight or nine years ago. It turns out that there are two optimal systems, assuming that you want to have four coins. One system has a penny, a nickel, a quarter, and a glubbernog, which is worth 18 cents. With this system, you can expect to carry an average of only 3.88 coins at any time; the current system averages 4.69 coins. The other optimal system replaces the quarter with a 29-cent snonkularb. Among 5-coin systems, the optimal one has a penny, a nickel, and coins of denominations 16, 23, and 33 cents; under this system, you can expect to carry an average of only 3.28 coins at any time rather than 4.19 with the current system. (Notice that 4.19 is exactly half a coin less than if you disregard half dollars; that's because half the time you are carrying at least two quarters and can replace them with a half dollar, saving one coin.) The current system could be substantially improved by replacing the mostly-useless half dollar with a 32 or 33-cent coin; this would cut the average to 3.45 or 3.48 coins. Of course, the real goal is to minimize weight and bulk, not number of coins. The obvious solution here is to make the quarters really small. Hope this helps. -- Mark Dominus Perl Paraphernalia	[reply]
Re^2: OT: making change by Ovid (Cardinal) on Nov 24, 2004 at 16:20 UTC
Why is C so powerful? It can optimize computer time. Why is Perl so powerful? It can optimize programmer time. An 18 or 32 cent piece seems the equivalent of C. I prefer Perl :) Cheers, Ovid New address of my CGI Course.	[reply]
Re: OT: making change by Dominus (Parson) on Nov 24, 2004 at 16:23 UTC
Says Eimi Metamorphoumai: Interestingly, that only gives you the smallest number of coins for certain combinations of denominations. I looked into this in some detail a while back also. As you point out, the greedy change algorithm for the US (1, 5, 10, 25) system always delivers the minimum possible number of coins for any amount, but this is a property of the particular denominations used. Clearly, a system with coins of size 1, 10, and 11 does not have this property, since the greedy algorithm gives change for 20 cents by starting with an 11-cent coin, and then delivers nine pennies. When I realized this I started to look around to see if there were any widely-used coinage systems that did not have the greedy property. I was pleased to discover one: the pre-decimalization currency of the United Kingdom included the following coins: half-crown = 30 pence florin = 24 pence shilling = 12 pence sixpence = 6 pence When changing four shillings = 48 pence, the greedy algorithm delivers a half-crown, a shilling, and a sixpence, but the optimal solution delivers two florins. -- Mark Dominus Perl Paraphernalia	[reply]