Bin packing is an NP-complete problem, and it goes like this: Given a set of items x1 x2 x3 ... xn with sizes 0 <= x <= 1 for all the x's, and given an unlimited supply of "bins" of size 1, find the smallest number of bins that can contain all of the items.

Because the problem is NP-complete, we know that there is no known polynomial time algorithm to solve this problem. However, there is an algorithm that might yield a "good enough" answer.

The algorithm, called Decreasing Fit First goes like this: first sort the items according to decreasing size. Then get the largest sized item, put it in bin 0. Then get the next largest item, and try to fit it in bin 0. If it does not fit, then put it in a new bin (bin 1). Now get the next largest item, try to fit it in bin 0, if it won't fit, try bin 1, if not, put it in a new bin 2. Then get the next largest item... and so on, until you run out of items.

It turns out that Decreasing Fit First is 11/9 times the optimal in the worst case. Now, whether this is good enough varies from case to case.

Log in or register to write something here or to contact authors.