Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

/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 <>
Subscribe to The Perl Review

In reply to How can I calculate the right combination of postage stamps? by brian_d_foy

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (2)
As of 2023-10-04 04:05 GMT
Find Nodes?
    Voting Booth?

    No recent polls found