|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 20 Aug 2002 05:18:10
To : Andrew Lipnitsky
Subject : Re: Укладка пpямоугольников
--------------------------------------------------------------------------------
Wed Aug 07 2002 21:19, Andrew Lipnitsky wrote to Andrey Filimonov:
>> Вот такая простая задача - но хорошего пути решения не знаю, и есть
>> подозрения на np-полноту.
>>
>> Есть прямоугольник X на Y клеток - и N прямоугольников различного размера
>> с целой (в клетках) длиной стороны. Hадо их все в этот прямоугольник
>> выложить так, чтобы они не пересекались (касаться - могут). Собственно,
>> все. ;-) Заранее спасибо.
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
