(classic problem)
Definition: Pack a set of rectangles into a strip of width 1 to minimize the height used. Rectangles may not overlap or be rotated. Without loss of generality, the height of rectangles is at most 1. This is NP-hard.
Generalization (I am a kind of ...)
optimization problem.
See also bin packing problem, knapsack problem, cutting stock problem.
Note: Rectangles must have widths at most 1, otherwise they wouldn't fit in the strip. If any height is greater than 1, all heights can be scaled to no more than 1.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 6 May 2005.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "strip packing", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 6 May 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/strippacking.html
