http://qs1969.pair.com?node_id=726121

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 (Priest) 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
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.

        G. Wade
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.