Не тривиальная задачка
 

Есть некоторое количество прямоугольников (60-100).

Задача - скомпоновать их так, что бы получился прямоугольник с максимально эффективно занятой площадью.

Вращать прямоугольники нельзя.
Скорость выполнения значения не имеет.

Может быть есть какое-нибудь классическое решение?

А то у меня вариантов кроме тупого перебора, что-то пока вообще нет.

вспомнил вот.:v2_unsur: был у нас пуру лет назад препод, читал чужие лекции:v2_crazy:: задачки на "упаковку" (минимизацию площади) (698k - pdf), там как раз алгоритмы под твою проблему, делали ему кажется:v2_smile: даже какую-то лабу одним из методов (на пц... методом "имитации отжига", кажется)...

если интересует классический подход - теория самое оно будет:v2_wacko: (хоть и выглядит как бред сивой кобылы), во всяком случае будешь знать в каком направлении копать.:v2_conf2: на wikipedi'и, кстати, практически только "имитация отжига" коротенько описана, так что походу довольно классический метод..

алгортима не знаю, но тут ее точно решили :)

левак какой-то по ссылке.

ну правильно :) карта фондового рынка. там объемы рынка у всех меняются (площади), а карта постоянно упакована в один прямоугольник.

тупой перебор - долго, быстрее (но не оптимально!!!) - генетический алгоритм. точно не расскажу, но смысл в том, что сначала компонуешь случайно. потом _что-то_ меняешь, смотришь, получилось лучше или хуже. если лучше, то опять меняешь.. так оно улучшается, улучшается.. в итоге к чему-то придешь. можно модифицировать. например, заполняешь случайно 10 раз. среди всех ищешь лучший. делаешь в нем 10 разных замен, в лучшей еще 10, и т.д.

Даже для перебора нужен какой то алгоритм. Не представляю только какой.
Да и задачка усложнилась. Теперь прямоуголник в котором нужно распределить прямогольники стал квадратным и фиксированого размера.

1) отсортировать прямоугольники по убыванию площади
2) в угол пустого квадрата помещается наибольший прямоугольник
3) пустое место после размещения ветвится на 2 прямоугольника - большой и маленький, запоминаем, сортируем тоже.
4) берем следующий прямоугольник размещаем его в наименьшее подходящее пустое место, нужно только понять в какой угол, для начала тупо в произвольный.
5) если прямоугольники или пустые места не кончились, go to 3.

У меня похожая идея. Что то вроде тетриса, падают фигуры до упора и сдвигаются в угол и дальше падают если возможно, фигуры выбираются по убыванию размера (90% фигур прямоуголники с соотношением сторон 3 к 5).

в продолжении моего первого поста в этой теме, нашел вот такое: "имитация отжига" (304 Кб - делфовый проект + exe'шник для ознакомления, чтоб делфу в пустую не устанавливать:v2_neutr:), по контексту как раз вроде что надо... разбираться, что к чему сейчас не когда да и не хочется:v2_conf2: пользуйся, если на что сгодится:v2_huh:

с усложнением задачки, правда, все сложнее:v2_rolley