laziness, impatience, and hubris PerlMonks

### How can I calculate the right combination of postage stamps?

by brian_d_foy (Abbot)
 on Nov 26, 2008 at 14:42 UTC Need Help??
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 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
--
brian d foy <brian@stonehenge.com>
Subscribe to The Perl Review

Replies are listed 'Best First'.
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 bin-packing 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 bin-packing 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

Just in case this didn't help brian d foy, you can rest assured you helped someone. I think this is exactly the module i need to solve my problem of fitting X number of directories of Y size on a 4 gig DVD.

jeffa

```L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)
```

What I used it for was scheduling some batch document-publishing 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 sub-sites 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.)

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.
True for coins, but postage stamps can be very different.

Cheers Rolf

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:

Cheers - L~R

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 stack-based solution.

IIRC, with the exception of pruning paths once they reach the required postage, the only way to get all solutions is really brute-force. If you are satisfied with the first solution found, then you can trim that somewhat. This is, I believe, your classical NP-Complete problem, which, without some assumptions, is only solvable by brute force.

Very enjoyable (meaning interesting :-) post and problem, BTW.

--MidLifeXis

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
```  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-{

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.

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), NP-complete sometimes isn't should be interesting for you.
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 24-cent stamps come in handy if you ever need to send first-class mail in large envelopes. The first ounce is \$0.83, or 42 + 24 + 17.

First-class 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 3-ounce 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.

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?
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 n-choose-k fashion (see Math::Combinatorics's combine()), except that you won't be combining the stamps merely to fulfill the k-grouping criterion.

Instead, you would enforce your own criteria to guide the grouping process, while poisoning the recursion space if it ever got out-of-bounds. Think of k as a condition instead of a number.

I have a LISP-variant n-choose-k function that allows passing in conditional lambda's. Unfortunately, I don't believe there is a Perl-equivalent 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.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://726121]
Approved by marto
Front-paged by MidLifeXis
help
Chatterbox?
 NodeReaper plugs in the Polybius cabinet [1nickt]: choroba pm-cb-g does not seem to implement the preferences, specifically font family ... should I raise an issue on Githhub or ... ?

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (13)
As of 2017-10-18 12:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My fridge is mostly full of:

Results (244 votes). Check out past polls.

Notices?