Correct best-fit algorithm for bin packing?

Question

I have the following numbers 6,8,9,4,3,2,10,7,14,12,6,2,3,1,10,11,13,5

I wish to know the correct way to implement the best-fit 1D Bin packing algorithm for these. Because in this video http://www.youtube.com/watch?v=B2P1TzKKWOI&feature=related they are solving it differently than in my mind so i don't know the correct answer.

My Solution, First come first serve, so:

Bin #1: 6,8,2 Bin #2: 9,4,3 Bin #3: 3,10,1 Bin #4: 7,6 Bin #5: 14,2 Bin #6: 12 Bin #7: 10 Bin #8: 11,5 Bin #9: 13 Their Solution, i guess they "pair" the suitable numbers together, so it goes like:

Bin #1: 6,10 Bin #2: 9,7 Bin #3: 14,2 Bin #4: 12,4 Bin #5: 14,2 Bin #6: 13,3 Bin #7: 8,6,2 Bin #8: 10,5,1 Bin #9: 11,3 Which one is correct?

Answer 1

What you have done is called a first-fit algorithm. What they have used is a best- fit algorithm which produces a better solution but is slightly slower. Both these algorithms can be further improved by sorting the list into decreasing order before applying the algorithm. See www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm for some examples.

Answer 2

The algorithms usually called best-fit and first-fit are online algorithms, meaning that you have to put it into a bin as soon as they see it. Looking briefly at the video, what they call best-fit does not appear to be an online algorithm. On the other hand, what you have done doesn't seem to be best-fit, either, although it's a lot closer (so it looks like you just made an error). Unless I have made a mistake, for packing the sequence

6,8,9,4,3,2,10,7,14,12,6,2,3,1,10,11,13,5

into bins of size 16, best-fit will produce the packing

(6,8,2) (9,4,3) (10,6) (7) (14,2) (12,3,1) (10) (11,5) (13).

The algorithm best-fit puts the items in bins in the order they arrive, with each item going into the fullest bin that it fits in. So, if you have the partial packing

(6,8,2) (9,4,3) (10,6) (7) (14) (12)

and you need to pack an item of size 2, it goes into the bin already containing the item of size 14, since at this point the bins have contents 16, 14, 12, and 7, and the ones with contents 16 are too big to hold it.