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
| [reply] [Watch: Dir/Any] |
|
| [reply] [Watch: Dir/Any] [d/l] [select] |
|
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.)
| [reply] [Watch: Dir/Any] |
|
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] [Watch: Dir/Any] |
|
True for coins, but postage stamps can be very different.
| [reply] [Watch: Dir/Any] |
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] [Watch: Dir/Any] |
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.
| [reply] [Watch: Dir/Any] |
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] [Watch: Dir/Any] [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] [Watch: Dir/Any] |
|
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] [Watch: Dir/Any] |
|
|
|
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.
| [reply] [Watch: Dir/Any] |
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. | [reply] [Watch: Dir/Any] |
|
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] [Watch: Dir/Any] |
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.
| [reply] [Watch: Dir/Any] [d/l] [select] |