оптимальное заполнение

From

Slava Gorbanev ()

To

All

Date

2002-11-08T21:23:36Z

Area

RU.ALGORITHMS

есть небольшая производственная задача.  дано: несколько рулонов
материала разной ширины и в общем случае бесконечной длины.  требуется
разместить на них прямоугольные изображения разной площади/размеров
таким образом, чтобы, с одной стороны, отходы материала были минимальны,
а с другой, чтобы использовалось как можно меньше рулонов с разной
шириной.  размеры изображения могут превышать ширину материала, т.е.
может потребоваться разрезать его (изображение) на несколько частей.

в принципе, минимизацию числа рулонов и резку можно сделать вручную, на
этапе ввода данных, главное требование -- минимизация отходов.

хотелось бы знать, что по этому поводу почитать, и какие ключевые слова
скормить googl'у.

-- 
rnd, animated dead.

--- tin/1.5.14-20021012 ("Laetitia") (UNIX) (Linux/2.4.18-10rnd (athlon))
 * Origin: dark tower (2:5057/57.1)