Re: Укладка пpямоугольников

From

Andrey Tarasevich ()

To

Andrew Lipnitsky

Date

2002-08-20T05:18:10Z

Area

RU.ALGORITHMS

From: "Andrey Tarasevich" <atarasevich@telocity.com>

Wed Aug 07 2002 21:19, Andrew Lipnitsky wrote to Andrey Filimonov:

 >> Вот такая простая задача - но хорошего пути решения не знаю, и есть
 >> подозрения  на np-полноту.
 >> 
 >> Есть прямоугольник X на Y клеток - и N прямоугольников различного размера
 >> с  целой (в клетках) длиной стороны. Надо их все в этот прямоугольник
 >> выложить  так, чтобы они не пересекались (касаться - могут). Собственно,
 >> все. ;-)  Заранее спасибо.

 AL> Вот есть такое решение:
 AL> http://www.lipnitsky.org/ru/projects/flats.php
 AL> Если есть вопросы всегда рады помочь.

Иллюстрации в вышеприведенном архиве содержат только гильотинные размещения.
Как насчет негильотинных? Если программа умеет генерировать только гильотинные
размещения, то в общем случае она не сможет найти решения вышеприведенной
задачи.

Best regards,
Андрей.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)