Re^2: Challenge: Twist On Bin Packing

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

Comment on Re^2: Challenge: Twist On Bin Packing

Replies are listed 'Best First'.
Re^3: Challenge: Twist On Bin Packing by moklevat (Priest) on Apr 07, 2006 at 16:12 UTC
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]