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

From

Slava Gorbanev ()

To

Andrew Starsh

Date

2002-11-10T04:11:22Z

Area

RU.ALGORITHMS

On Sat, 09 Nov 2002 09:02:29 +0400 Andrew Starsh wrote:

 SG>> есть небольшая производственная задача.  дано: несколько рулонов
 SG>> материала разной ширины и в общем случае бесконечной длины.
 SG>> требуется разместить на них прямоугольные изображения
 AS> Непонятно. Пpямоугольники? Или фигуpы, состоящие из одного и более
 AS> пpямоугольников?

по-моему я написал однозначно.

 SG>> разной площади/размеров таким образом, чтобы, с одной стороны,
 SG>> отходы материала были минимальны, а с другой, чтобы использовалось
 SG>> как можно меньше рулонов с разной шириной.
 AS> Стоп. Количество и шиpина pулонов заpанее не заданы, что ли? Или
 AS> это должно плясать от наличия на складе?

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

на мой взгляд, я сформулировал задачу четко и ясно: дано несколько полос
разной ширины, надо разместить на них разные прямоугольники.  разве что
надо было уточнить, что считать отходами -- это любая часть рулона,
ширина которой меньше ширины рулона.  например, при помещении на рулон
1000mm изображения 400x700mm в отходы может уйти материал площадью либо
600x700mm, либо 300x400mm -- в зависимости от того, какой стороной
повернуто изображение.  очевидно, второй вариант в данном случае
оптимальнее.

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

 SG>> размеры изображения
 AS> фигуpы. А лучше - деталь pаскpоя.

пусть будет раскрой.  хотя на самом деле это изображение для печати.

 SG>> могут превышать ширину материала, т.е. может потребоваться
 SG>> разрезать его (изображение) на несколько частей.
 AS> С пpипуском для последующей стыковки "внахлест" или стыковка "встык"?

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

 AS> Реальное пpоизводство, так? Раскpой pулонного матеpиала (ткань,
 AS> линолеум, нечто нетканное, пластик?)

какое значение имеет природа материала при решении поставленной задачи?

 AS> Так что тут для написания нужно знать конкpетное пpоизводство.

не нужно.

-- 
rnd, animated dead.

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