Challenge: Twist On Bin Packingby Limbic~Region (Chancellor)
|on Apr 07, 2006 at 13:03 UTC||Need Help??|
Limbic~Region has asked for the
wisdom of the Perl Monks concerning the following question:
If you are not familiar with the bin packing problem, it is the daunting (NP Hard) task of cramming a certain number of items into the fewest bins possible where each bin has a fixed capacity. A not too uncommon question here at the Monastery is how to minimize the number of CDs needed to burn all music files. I have been thinking about an interesting twist on the problem.
What if instead of trying to minimize the number of bins used you were trying to mazimize them. For instance, you wanted to make it look like you had purchased more gifts that you actually had. Presuming that every gift could fit into a single shipping box then you could send each gift in its own box. While this is obviously the maximum number of bins (provided you don't send any empty boxes) people are going to immediately see through your ruse.
Instead, you fill each box as close to capacity as possible but without doing it as efficiently as possible. Sound odd? I thought so too at first. It is easily reconciled when you consider that any attempt at solving the bin packing problem that is not the optimal solution is a series of bins as near capacity as possible without being as efficient as possible.
Imagine that a shipping box can only hold 10 units of weight and you have purchased 7 gifts with weights of 2, 2, 3, 4, 5, 6, and 7. You could get away with sending only 3 boxes by arranging them as:
Instead, you send 4 and everyone is impressed with your generosity:
My challenge then is to come up with an algorithm that provides the most inefficient solution to the bin packing problem while requiring that each bin be filled as near to capacity as possible. Update: This means you start filling the first bin until no more items will fit. Move on to second bin and repeat the process. The goal is to end up with as many bins as possible not the fewest.
Cheers - L~R