Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
It seems that all the bins have size 16 - is this correct? Also in "Their" solution you have put the pair 14,2 twice. Eliminating the duplicate, "they" have used eight bins, while you have used nine. –  Mark Bennet Sep 7 '12 at 8:55
    
true, but my questions was not which algorithm is better, but rather which algorithm is the true "best-fit algorithm for bin packing" –  AngelicCore Sep 7 '12 at 12:30
1  
add comment

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
No, what the OP has done is best-fit, while accidentally putting the item of size 6 in the wrong bin. It's not clear to me that the method of packing described in the video as "best-fit" is actually an algorithm (that is, there is no definitive description given which tells you which items to pack and in which order). It certainly does not match the description of the algorithm best-fit given on the website you link to (which is indeed the correct description). –  Peter Shor Jan 5 '13 at 18:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.