brian_d_foy has asked for the
wisdom of the Perl Monks concerning the following question:
/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 binpacking module on CPAN.
Part of my daytoday 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 reallife problem is that I have a hodgepodge 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
Re: How can I calculate the right combination of postage stamps?
by ForgotPasswordAgain (Deacon) on Nov 26, 2008 at 14:48 UTC

Maybe I missed the binpacking module on CPAN.
Yep, Algorithm::BinPack. There are a couple others, too, but that's the one I've used and it worked (was very happy :).
UPDATE: I got distracted by your actual problem, which I don't think is solved by the binpacking algorithm. I'm also not formally trained in CS. :} I found this link which seems to explain the problem for the case of coins (which are practically stamps): The Coin Changing Problem
 [reply] 

 [reply] [d/l] [select] 

What I used it for was scheduling some batch documentpublishing jobs. We have a lot of documents on our web site, and they each take a certain amount of time to publish (depending on what the templates do). We did a republish of all documents, but there are too many to do over one night, so we had to split the republishes up. We'd estimated how many documents we could publish per night. Our site has subsites corresponding to departments within the organization, and we needed to republish all of a subsite the same night. Each subsite has a certain number of documents (some have 100 docs, others 500, etc.), which I output using an SQL query. To optimize the schedule, I used Algorithm::BinPack to "pack" the sites into bins of, say, 3000 documents per night. It worked very well.
(Of course, it didn't go perfectly. We'd estimated 3000 per night, but after a few nights we adjusted that number; that was easy to do, just change the bin size in the script. Also it turned out that certain, more "special", subsites needed to be published on certain days, so we had to shuffle them around a bit.)
 [reply] 

In practice, any coin issuing entity will make coins in such a way that a greedy algorithm is optimal. That is, noone is issuing coins as 7c, 6c and 1c coins (a case where greedy isn't optimal to make 24c change (greedy gives you 3 x 7c + 3 x 1c, while optimal is 4 x 6c)). Instead typical coin denominations are 1c, (2c), 5c, 10c, 20 or 25c, (50c), 100c, (200 or 250c), (500c). For instance, US dollar coins come in 1c, 5c, 10c, 25c, 50c, and 100c; Euro coins in 1c, 2c, 5c, 10c, 20c, 50c, 100c, and 200c; Yen coins in 1y, 5y, 10y, 50y, 100y, 500y; Pound Sterling coins in 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p (effectively the same as Euro coins). For all, a greedy algorithm is optimal.
 [reply] 

True for coins, but postage stamps can be very different.
 [reply] 
Re: How can I calculate the right combination of postage stamps?
by Limbic~Region (Chancellor) on Nov 26, 2008 at 15:39 UTC

brian_d_foy,
You can look at this problem two different ways. The first way is a variation on the bin packing problem. There are many threads here as well as a number of modules on CPAN. There are heuristic approaches that are much faster than brute force but they don't guarantee no waste. If I get a chance later, I will augment this node with some links but Super Search is your friend.
The second way, is restricted integer partitioning. See How to generate restricted partitions of an integer and puzzle: how many ways to make $100 for instance. This isn't exactly your problem because it assumes you have an unlimited number of each stamp denomination. On the other hand, it is interesting to learn about. And while we are at it, consider that unrestricted integer partions are also fun  see below for a list:
 [reply] 
Re: How can I calculate the right combination of postage stamps?
by MidLifeXis (Monsignor) on Nov 26, 2008 at 15:27 UTC

Basically, this is very similar to a bin packing problem. Your fitness test is the minimum amount over the postage required, and your termination test is greater than or equal to the amount of postage required. Very commonly solved with a recursive or stackbased solution.
IIRC, with the exception of pruning paths once they reach the required postage, the only way to get all solutions is really bruteforce. If you are satisfied with the first solution found, then you can trim that somewhat. This is, I believe, your classical NPComplete problem, which, without some assumptions, is only solvable by brute force.
Very enjoyable (meaning interesting :) post and problem, BTW.
 [reply] 
Re: How can I calculate the right combination of postage stamps?
by Taulmarill (Deacon) on Nov 26, 2008 at 16:15 UTC

Was kind'a bored, so i worked on a perl solution. This should be much faster:
#!/usr/bin/perl
use strict;
use warnings;
my $desired_postage = $ARGV[0]  1.51;
$desired_postage = int $desired_postage * 100;
my @stamps =
sort { $a <=> $b }
grep { chomp; $_ < $desired_postage }
map { int $_ * 100 }
grep { ! /^#/ }
<DATA>;
my $exact = grep { $_ == $desired_postage } @stamps;
print "Exact postage: " . $exact / 100 . "\n" if $exact;
my $dim_max = 6;
recurse( $desired_postage, [] );
sub recurse {
my( $rest, $select ) = @_;
if ( $rest == 0 ) {
print $_ / 100 . " " for @$select;
print "\n";
return;
}
return if @$select >= $dim_max;
my @filtered = grep {
$_ >= $rest / ($dim_max  @$select)
and $_ <= $rest
} @stamps;
@filtered = grep{ $_ <= $select>[1] } @filtered if $select>[1]
+;
for my $stamp ( sort{ $b <=> $a } @filtered ) {
recurse( $rest  $stamp, [ @$select, $stamp ] );
}
return;
}
Also i made integers of all values, because apearently on a Pentium IV 1.51  0.87  0.42  0.1  0.1  0.02 != 0  [reply] [d/l] 

Also i made integers of all values, because apearently on a Pentium IV 1.51  0.87  0.42  0.1  0.1  0.02 != 0
It fails on AMD as well...
bc gives the correct output. This is a sweet bug in Perl, i presume... 8{  [reply] 

That's not a bug in Perl. It's an artifact of using floating point numbers. There are many numbers that cannot be represented exactly in floating point.
At a glance, it appears that none of those would be exactly represented in the IEEE floating point formats. (I could be wrong.) So there would be some error in the calculation in any language, on any processor.
 [reply] 



Re: How can I calculate the right combination of postage stamps?
by moritz (Cardinal) on Nov 26, 2008 at 16:04 UTC

Since your postage stamps are rather small integer values (or can be made integer values by scaling with 100), NPcomplete sometimes isn't should be interesting for you.
 [reply] 
Re: How can I calculate the right combination of postage stamps?
by mr_mischief (Monsignor) on Dec 01, 2008 at 20:02 UTC

This isn't related to Perl but to the postage aspect of your problem.
Those 24cent stamps come in handy if you ever need to send firstclass mail in large envelopes. The first ounce is $0.83, or 42 + 24 + 17.
Firstclass international letter to Group 1 destinations is $0.72 for the first ounce, so three of those is just right. Additional ounces internationally are $0.24 for Group 1 destinations as well up to 3 ounces. A 3.5 ounce letter is an additional $0.24 over a 3ounce one.
You're probably already aware, but for the curious there is a USPS price guide at http://www.usps.com/prices/ with a page each for Domestic First Class Mail and many of the other rate types.  [reply] 

I don't want to write a Perl script. I bought the crippleware version of Dymo Stamps and it won't let me print exact postage unless I pay umpteen dollars a month. Isn't there a a frickin' web calculator somewhere where I can just enter the available values and the desired postage?
 [reply] 
Re: How can I calculate the right combination of postage stamps? (combinatoric n Choose k with conditions)
by repellent (Priest) on Dec 01, 2008 at 19:08 UTC

brian_d_foy,
You can try traversing the collection of stamps in a combinatoric nchoosek fashion (see Math::Combinatorics's combine()), except that you won't be combining the stamps merely to fulfill the kgrouping criterion.
Instead, you would enforce your own criteria to guide the grouping process, while poisoning the recursion space if it ever got outofbounds. Think of k as a condition instead of a number.
I have a LISPvariant nchoosek function that allows passing in conditional lambda's. Unfortunately, I don't believe there is a Perlequivalent that does a similar thing. Good news is, it shouldn't be too hard to roll your own. Exercise left for the reader :)
UPDATE: Here it is in Perl.
 [reply] [d/l] [select] 

