"Алгоритм прямоугольников"?

← →
DevilDevil © (2008-06-02 13:45) [0]

Извините за название, суть в следующем.

Есть сколько-то прямоугольников, разных размеров (размеры известны). Задача максимально компактно разместить их в прямоугольной "комнате" (размер "комнаты" тоже известен).

Есть ли какой вменяемый алгоритм для решения задачи ?

← →
Kerk © (2008-06-02 13:46) [1]

Эта задачка была на Google Code Jam Europe пару лет назад :)

← →
Правильный_Вася (2008-06-02 13:52) [2]

типичная задача плотной упаковки
или "задача о рюкзаке"
гуглить

← →
ketmar © (2008-06-02 14:00) [3]

не надо. а надо читать про marching squares.

---
Understanding is not required. Only obedience.

← →
Тыщ © (2008-06-02 14:31) [4]

http://www.lomont.org/Software/
Тут есть, на C#. Rectangle Packing.

← →
DevilDevil © (2008-06-02 15:04) [5]

> Тыщ © (02.06.08 14:31) [4]
не скачивается.

не кинешь по почте, если есть.

← →
Рамиль © (2008-06-02 16:32) [6]

> Правильный_Вася (02.06.08 13:52) [2]

А может раскроя?

← →
Alarm © (2008-06-02 16:45) [7]

Рамиль © (02.06.08 16:32) [6]
Именно раскроя листа (комнаты).
Канторович (линейное программирование)

← →
Правильный_Вася (2008-06-02 17:09) [8]

> А может раскроя?

это одного класса задачи

Одна из известных задач линейного программирования.
Алгоритм есть в любом учебнике (да и в сети навалом).

Не нахожу описание алгоритма.
В Rectangle Packing вроде то, но нет описания.

На всякий случай повторю условия. Есть комната определённого размера. Есть прямоугольники (которые нельзя поворачивать). Задача - максимально компактно расположить "прямоугольники" в "комнате".

похоже, то, что мне нужно:
http://www.gamedev.ru/users/coriolis/articles/Packing_Lightmaps

← →
Правильный_Вася (2008-06-02 18:09) [12]

> максимально компактно расположить "прямоугольники" в "комнате".

тетрис?

"Алгоритм прямоугольников"? Найти похожие ветки