Алгоритм оптимального заполнения площади блоками

← →
Ji (2007-12-20 18:14) [0]

Здравствуйте!

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

"Оптимально заполнить" подразумевает наименьшее количество оставшегося пустого места.
Наглядный пример - газета объявлений с рекламными площадями, только отличие в том, что нет жесткой сетки.

Подскажите пожалуйста что-нибудь по этому поводу.

← →
oldman © (2007-12-20 18:17) [1]

работай "от большого к малому"

← →
Ji (2007-12-20 18:20) [2]

> oldman © (20.12.07 18:17) [1]

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

← →
oldman © (2007-12-20 18:22) [3]

Работай, например, от левого верхнего угла.
Сначала ставишь самый большой блок.
Смотришь по горизонтали - если не входит, берешь следующую "строку".
Когда большие блоки (или место для них) кончатся, берешь следующий по убыванию блок и возвращаешься к верхнему левому углу.

← →
oldman © (2007-12-20 18:23) [4]

Сначала работаешь по горизонтали, потом по вертикали.

← →
Правильный_ВАся (2007-12-20 18:24) [5]

методы плотной упаковки, оптимального раскроя, задача о рюкзаке
всё гуглить

← →
Alexis © (2007-12-21 13:28) [6]

гуглить по словам

2D bin packing problem
rectangle bin packing
Two dimensional packing
NP problems

A вообще у меня программа есть написанная на Delphi и C++ Builder, которая выполняет subj. Если для лабораторной, то самое оно ...

← →
Lip (2007-12-21 18:06) [7]

Задача динамикой решается.

> Задача динамикой решается.

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

← →
Хелпер (2007-12-22 04:43) [9]

> Ji (20.12.07 18:14)

Упаковку лайтмэпов делаешь? Или по-крайней мере похоже.

Вот тебе ссылка: http://www.blackpawn.com/texts/lightmaps/default.html
Но реализовать будет сложно. Если алгоритм получится простым, то запости сюда, многим будет интересно.

Алгоритм оптимального заполнения площади блоками Найти похожие ветки