(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 Black.
Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "bin packing problem", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/binpacking.html