"be consistent" PerlMonks

Re: How can I calculate the right combination of postage stamps?

 on Nov 26, 2008 at 14:48 UTC ( #726122=note: print w/replies, xml ) Need Help??

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

• Comment on Re: How can I calculate the right combination of postage stamps?

Replies are listed 'Best First'.
Re^2: How can I calculate the right combination of postage stamps?
by jeffa (Bishop) on Nov 26, 2008 at 15:47 UTC

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

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

Re^2: How can I calculate the right combination of postage stamps?
by JavaFan (Canon) on Oct 26, 2010 at 10:24 UTC
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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://726122]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (2)
As of 2023-09-25 11:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?