Don't ask to ask, just ask | |
PerlMonks |
Re: Challenge: Twist On Bin Packingby moklevat (Priest) |
on Apr 07, 2006 at 14:02 UTC ( [id://541868]=note: print w/replies, xml ) | Need Help?? |
Very interesting. In thinking about this it might be easier to find a solution if the problem is slightly refactored. Rather than discussing bins and gifts, I think that this problem lends itself better to considering volumes of liquid. We are not concerned with the way in which our bins are packed, rather we assume that whatever unit volume we place in each bin automatically fits in the best possible way (like liquid). Since we can consider this a problem of liquids, we may as well discuss beer. :-)
I therefore propose the following modification of the problem as the The Pint Pouring Problem
At your local pub all beer is served in 1 pint glasses. Following a serious problem at the brewery today's shipment of beer was delivered in cans of various sizes, each less than a pint. The thrifty pub owner asks you to devise an algorithm for pouring as many pints as possible, but that also ensures that as many patrons as possible get a Now to work on a solution... Update:The combination of "as full as possible" and "as many bins as possible" in the original post create an inherent conflict (which, I suppose, is the point). Having said that, I have not been able to think of a case for which a variation on the "Best Fit Decreasing and First Fit Decreasing" strategy will fail. (that's not to say there isn't one, but I have to get *some* work done today). The algorithm:
1) Sort all cans by size. 2) Begining with the largest can and moving smaller, pour as many cans in order that will fit in a single glass. If you come to a can that will overflow the glass go to the next step. 3) Beginning with the smallest cans and moving larger pour as many cans in order that will fit in the glass. If you come to a can that will overflow the glass go to Step 2 and begin filling the next glass. Update:I have removed step zero. Limbic~Region didn't like it and it is unnecessary. It simply reparameterized the problem as if you had smaller glasses. Final Update:The problem has been clarified somewhat and this solution does not fit, as L~R notes below.
In Section
Seekers of Perl Wisdom
|
|