Скачать: CL | DM;

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

← →
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]

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

---

← →
TUser ©   (2007-12-21 18:19) [8]

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

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

---

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

> Ji   (20.12.07 18:14)


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

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.47 MB
Время: 0.015 c