/My lack of formal computer science training might be blame for this. Maybe you've all seen this in CS 101, but I didn't find satisfactory answers in my googling. Also, I solved this by redefining the problem: I bought a stamp machine so I can print any postage I like :)/

Given a selection of stamps, what's are the different combinations I can make to get to a certain total? My solution, which runs fast enough to be useful, is brute force. I make cross products of the set of stamps I have then filter the combinations. Maybe I missed the bin-packing module on CPAN.

Part of my day-to-day work with The Perl Review is mailing single issues to people apart from the mass mailing with each new issue. The US Postal Service doesn't have a single stamp with the right denomination for the domestic rate ($1.51) or the international rate ($4.40). I have to cobble together several stamps to do that.

Now, that initially seems easy. But, the post offices in Chicago often don't have stamps. They get a delivery once a week, and they don't have good document control. The stamps are literally sitting in small piles in many locations with no accountability. If they do have stamps, it's usually only the first class stamps and not the additional postage stamps. I can order most stamp denominations online, but the delivery takes about a week.

The real-life problem is that I have a hodge-podge of stamp denominations and want to not only make the right price with the least number of stamps, but also sometimes use more stamps so I can get rid of obsolete additional postage (like the $0.24 cent stamp that used to be the additional ounce, but is now the $0.17 stamp for an additional ounce).

#!/usr/bin/perl
use strict;
use warnings;

use List::Util qw(sum);
use Set::CrossProduct;
use Term::ANSIColor;
 
my $desired_postage = $ARGV[0] || 1.51;

my @stamps = 
    sort { $a <=> $b } 
    grep { chomp; $_ < $desired_postage } 
    grep { ! /^#/ } 
    <DATA>;

my $exact = grep { $_ == $desired_postage } @stamps;
print "Exact postage: $exact\n" if $exact;

my $dim = 1;
while( 1 )
    {
    my %combos;
        
    my $cross = Set::CrossProduct->new( [ ( \@stamps ) x ++$dim ] );
    print colored ['red'], 
        "For dim $dim, cardinality is ", $cross->cardinality, "\n";

    while( ! $cross->done )
        {
        my $combo = check( scalar $cross->get, $desired_postage );
        $combos{ $combo }++ if $combo;
        }

    foreach my $combo ( 
        sort { $a =~ tr/|// <=> $b =~ tr/|// || $b cmp $a 
            } keys %combos 
        
        )
        {
        my @stamps = split /\|/, $combo;
        
        printf +("%.2f " x @stamps ) . "\n", @stamps;
        }

    last if keys %combos > 15;
    }
    
sub check
    {
    my( $stamps, $desired_postage ) = @_;
    
    sum( @$stamps ) eq $desired_postage ? make_key( @$stamps ): ();
    }
    
sub make_key { join "|", sort { $b <=> $a } @_ }


__END__
# These are the stamp demoninations that I can buy
# The uncommented ones are the stamps that I have
#0.01
0.02
0.03
0.04
0.05
0.10
#0.17
#0.20
0.26
0.27
#0.39
#0.41
0.42
#0.55
#0.59
#0.62
#0.63
#0.72
#0.75
#0.76
0.80
#0.83
0.84
0.87
#0.94
#1.00
#4.80
5.00
[download]