(classic problem)
Definition: Determine how to put the most objects in the least number of fixed space bins. More formally, find a partition and assignment of a set of objects such that a constraint is satisfied or an objective function is minimized (or maximized). There are many variants, such as, 3D, 2D, linear, pack by volume, pack by weight, minimize volume, maximize value, fixed shape objects, etc.
See also knapsack problem, cutting stock problem, optimization problem, strip packing, set packing.
Note: A common form of the problem is, what is the least number of bins (containers of fixed volume) needed to hold a set of objects. This problem often appears in manufacturing. For instance, suppose we need a number of pipes of different, specific lengths to plumb a house and we can buy pipe stock in 5 meter lengths. How can we cut the 5 meter pipes to waste as little as possible (minimize the cost of pipe)?
Thanks to Frank A. Adrian <fadrian@symantec.com>, 28 January 2000.
Author: PEB
Limits and references. Suggestions on books and related topics.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 17 December 2004.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "bin packing problem", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/binpacking.html
