Packing and cutting problem

[rubytran]

my problem statement:
Given a finite set of rectangles and a strip with known width and infinite height.
The rectangles are placed on a strip without crossing the boundary of the strip and overlapping the packing rectangle.
Objective: the height of the strip used is minimized.

The heuristic: For packing of the rectangles in the strip, these rectangles are arranged from the bottom-left-right position of the strip. After placing each rectangle on the strip, new positions (nodes) for placing the next rectangle are identified. The positioning of rectangle on the strip is based on a 2D translation.

Do anyone know an algorithm in C++ nearly the same my prolem?

[cilu]

[ redirected thread ]

[alanjhd]

Hi,

Did you already check the Stony Brook site? Maybe there's something at:

http://www.cs.sunysb.edu/~algorith/implement/c++.shtml

Cheers,
Alan

[RoboTact]

my problem statement:
The rectangles are placed on a strip without crossing the boundary of the strip and overlapping the packing rectangle.What is the packing rectangle?
Is it so that there is a big rectangle (container), on bottom of which number of smaller rectangles should be placed without overlapping each other, so that the height (from the bottom of container) of overlapped area (with container) is to be minimized?

[mehdi62b]

well,I think you wanna pack some little rectangles in a strip so that they occupy the height of the strip as minimum as possible?
if so?,you should sort the little rectangles according to their widths decreasingly,then start and pack them in the strip verticaly from up to bottom the the next column from bottom to up,for the third column,put sorted rectangles in rows have less widths occupied by previous rectangles and so on..this would occupy the least height of the strip.