# bin packing problem

(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

## Implementation

(Icon).
## More information

Limits and references. Suggestions on books and related topics.

Go to the
Dictionary of Algorithms and Data
Structures home page.

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