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