The two-dimensional strip packing problem consists of packing in a rectangular strip of width 1 and minimum height a set of n rectangles, where each rectangle has width \(0 < w \le 1\) and height \(0 < h \le h_{max}\) . We consider the high-multiplicity version of the problem in which there are only K different types of rectangles. For the case when \(K = 3\) , we give an algorithm that produces solutions requiring at most height \(\frac{3}{2}h_{max} + \epsilon \) plus the height of an optimal solution, where \(\epsilon \) is any positive constant. For the case when \(K = 4\) , we give an algorithm yielding solutions of height at most \(\frac{7}{3}h_{max} + \epsilon \) plus the height of an optimal solution. For the case when \(K > 3\) , we give an algorithm that gives solutions of height at most \(\lfloor \frac{3}{4}K\rfloor h_{max} + h_{max} + \epsilon \) plus the height of an optimal solution.
