Jump to content

First fit algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ruthhe (talk | contribs) at 12:05, 22 January 2007. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The first fit algorithm is an algorithm which provides a fast but often nonoptimal solution to the bin packing problem, involving placing each item into the first bin in which it will fit. It requires Θ(n log n) time.
The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and, particularly for longer list, can greatly increase the time taken to implement the algorithm.