(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 November 2020.
HTML page formatted Mon Nov 2 12:36:42 2020.
Cite this as:
Paul E. Black, "bin packing problem", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 2 November 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/binpacking.html