in reply to Challenge: Twist On Bin Packing

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 suitably full pint glass (say at least 90% full). Assume that cans cannot be split across pint glasses. Fewer pints poured means less revenue for the pub owner, but inadequately filled pints mean angry patrons and the potential for trouble.

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:

0) Step zero is to set a threshold for adequately "full" that is less than 100%.

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.

Replies are listed 'Best First'.
Re^2: Challenge: Twist On Bin Packing
by Limbic~Region (Chancellor) on Apr 07, 2006 at 15:17 UTC
    moklevat,
    No, you can't pick an aribtrary limit less than 100% that you have to meet. As you can see from my example, one of the shipping boxes (in your case pint mugs) is only 2. Sure the bar owner may choose just to accept this as a loss and drink it himself but that doesn't change the nature of the problem.

    Starting with the first mug, fill it as close to the top as you can without over filling or without leaving any beer in the can. Move on to the second mug and repeat the process. The goal being to choose the grouping of cans such that you end up with the most number of mugs and not the least.

    I am not sure if your algorithm works but given its simplicity I hope so. I will set something up to brute-force this weekend and compare the results to your approach.

    Update: As you can see, this approach fails with a bin size of 10 and an input list of 1,1,1,2,2,3,4,6,7,7

    Cheers - L~R

[reply]
      Fair enough, step zero is not necessary for the algorithm to work, it just provides an additional parameter to adjust pint/bin size. Without step zero the algorithm still produces 4 pints/bins, and the last person gets 3 units rather than 2 units.

      1:  7, 2
2:  6, 2
3:  5, 4
4:  3

      [download]
[reply]
[d/l]
Re^2: Challenge: Twist On Bin Packing
by bibliophile (Prior) on Apr 07, 2006 at 15:25 UTC
    Hmm. I would have taken a different tactic...

    Assume that you have an infinite number of standard containers with a given length/width/height. You also have a finite number of items to go in the containers, each item having its own l/w/h (which can be different for each item). The trick then would be to pack items in containers such that each container can hold no more items... but optimizing for empty space.
    Order of packing then becomes the issue.

    Actual code is left as an exersise for the reader. :-)

    -- WARNING: You are logged into reality as root.
[reply]

In Section Seekers of Perl Wisdom