Алгоритм нахождения наименьшей площади, занятой n прямоугольниками
У меня есть несколько прямоугольников, я хочу найти самый маленький прямоугольник, который может охватывать все маленькие. вращение не допускается. 
Используя грубую силу, я хочу найти свой ответ. Я пытаюсь закодировать это в Java. Я знаю, что должен проверить всю перестановку моих n предметов и найти наименьшую площадь. И чтобы упростить это, сначала я попытался найти минимально возможную область. Затем я использовал двумерный массив с логическими значениями, чтобы проверить, занята ли каждая ячейка или нет. Но я не мог понять это (закодировать).
Как проверить, можно ли разместить мои вещи в моей ограниченной области? Например, я нашел свой первый предмет в x[0][0] в x[10][1] и сделать все ячейки в этом диапазоне истинными, но я не знаю, как сказать моей программе проверить другую ячейку для следующего элемента. Можете ли вы рассказать мне о шагах, которые мой алгоритм должен реализовать?
1 ответ
Ваши проблемы подпадают под категорию упаковки 2D-бина. Это NP-сложная задача, поэтому не существует эффективного алгоритма полиномиального времени для ее решения. (Если только P==NP).
Вы можете попробовать алгоритм грубой силы или умную эвристику, которая даст вам довольно оптимальное решение.
Обратитесь по следующим ссылкам:
1. Как программно достигается двухмерная упаковка бункеров? (Для обсуждения различных алгоритмов)
2. http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu (для деталей реализации)
3. http://www.binpacking.4fan.cz/ (для визуализации различных эвристик)
Ваш алгоритм грубой силы очень неэффективен. Перестановка, в которой могут быть размещены прямоугольники, очень велика и ее трудно найти. Я предлагаю вам попробовать вышеупомянутые алгоритмы, которые проще реализовать, чем найти подходящие для всех перестановок.