Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2008.01.27;
Скачать: 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 вся ветка

Текущий архив: 2008.01.27;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.011 c
3-1190408298
Kostafey
2007-09-22 00:58
2008.01.27
Использование таблиц и полей в качестве параметров хранимых про-


2-1198581830
Koss
2007-12-25 14:23
2008.01.27
Работа с Indy


2-1197306145
Irish_34
2007-12-10 20:02
2008.01.27
UDF


15-1197887433
Дмитрий
2007-12-17 13:30
2008.01.27
Пожалуйста помогите с Pascal


2-1198618035
Евгений Р.
2007-12-26 00:27
2008.01.27
Высота заголовка формы