Какие существуют алгоритмы эффективного размещения прямоугольных объектов в прямоугольный контейнер?
Даны размеры контейнера и размеры прямоугольных объектов, которые нужно в нем разместить. Суммарная площадь этих объектов больше, чем площадь контейнера. Нужно максимально эффективно разместить данные объекты в контейнере.
Эта задача NP-полная и для ее решения рекомендуют использовать эвристические методы (например генетические алгоритмы). Я никогда не сталкивался с этой темой и надеюсь получить хотя бы примерное направления решения задачи, например быть ссылки на статьи или алгоритмы, которые решают похожие задачи.
Там есть примеры частных случаев, и ваша задача очень похожа на "задачу о ранце (рюкзаке)", немного на задачу раскроя или замощения, но еще больше она походит на задачу о упаковке, внезапно.
Генетический алгоритм это случайный выбор новых комбинаций. Далее:
а) отбрасываются самые плохие, остаются хорошие
б) несколько новых делают из хороших путём мутации (случайного изменения нескольких случайных позиций)
в) несколько новых делают из хороших путём скрещивания (часть позиций из папы, часть из мамы).
Цикл повторять.
