Есть идеи как можно оптимизировать алгоритм по комбинаторике?

Question

[Родион Альметов]

Есть произвольное количество прямоугольников разных размеров(Высота,Ширина,Толщина).
Необходимо сформировать "пачки" с некоторыми ограничениями таким образом, чтобы получить минимальное количество "пачек".
Ограничения:
1) Один прямоугольник можно ставить на другой по определенными условиями (к примеру ширина не должна превышать ширину другого на 30 условных единиц, и таких условий несколько - но это не суть)
2) Пачка не должна превышать общую толщину допустим 300 условных единиц.

В идеале чтобы прямоугольники шли от большего к меньшему.
Ломаю голову и никак не могу прийти к удовлетворяющему результату.

Пока только несколько способов подбора прямоугольников придумал:
1) По габаритам
2) По высоте (предварительно переворачивая их, чтобы высота всегда была больше ширины)
3) Высчитывал дельту между шириной и высотой
4) Сортировал по принципу "квадратности"

Рад буду любым идеям.

Comments

[Дмитрий]

к примеру ширина не должна превышать ширину другого на 30 условных единиц, и таких условий несколько - но это не суть

То есть условия задачи это не суть, но нужно подсказать вам как решать? Оригинально.

Пачка не должна превышать общую толщину допустим 300 условных единиц.

Что значит "пачка не должна превышать толщину"? Как может пачка превышать толщину, да еще "общую"?

[Родион Альметов]

Дмитрий,

То есть условия задачи это не суть, но нужно подсказать вам как решать? Оригинально.

условий много. Суть заключается в методе комбинаторики, для начала можно взять за основу превышение одного прямоугольника над другим не более чем на 30 у.е., если решить задачу для этого условия, то и следующие условия навесить будет не сложно.

Что значит "пачка не должна превышать толщину"? Как может пачка превышать толщину, да еще "общую"?

Каждый прямоугольник (объемный) имеет толщину например 30, соответственно "пачка" может вместить максимум 10 прямоугольников (30*10 <= 300)

Answer 1

[Adamos]

Берете задачу о рюкзаке и приспосабливаете к своим условиям.
Если прямоугольников меньше сотни - полный перебор с выбором оптимального решения займет считанные секунды.
Если нет - ищете, где вы налажали.
Если не найдете - меняйте язык на не создающий объекты в памяти без спроса.

Comments

[Родион Альметов]

Как раз таки прямоугольников может быть как 15 так и 800.
А перебором я пробовал высчитать количество сочетаний хотя бы по 8 прямоугольников в пачке из 300, получилось число 1 квадрильон с чем то (про факториал вообще молчу).
Использую кстати php.
Спасибо за ответ! Про рюкзак читал - но пока не представляю как под себя заточить. Буду пробовать.

[Adamos]

Родион Альметов, если как можно раньше отсекать заведомо не оптимальные ветви перебора - количество вариантов можно сильно сократить. Ну, и любой компьютер в этом веке умеет миллионы операций в секунду.

[Родион Альметов]

Adamos, буду пробовать. Спасибо!

Answer 2

[Sumor]

Всё сводится к классическим задачам оптимизации. Скорее всего ваша задача очень похожа на задачу об укладке рюкзака.
Решается, скорее всего, динамическим программированием или ветвями и границами.

Comments

[Родион Альметов]

Про динамическое программирование тоже читал. А подробное про ветви и границы можно?

Answer 3

[Дмитрий]

Родион Альметов,

1) Сортируем по первому параметру, который "не суть" + по толщине
2) Проходим циклом по отсортированному массиву, высчитывая для каждого прямоугольника ближайших соседей, НЕ удовлетворяющих условию соседства. Допустим для прямоугольника №5 это будут №2 и №7, значит прямоугольник можно соединить только с номерами 3, 4, и 6.

Имея эту информацию начинаем наполнять пачки начиная с самых толстых. Как только произошло превышение толщины, ищем для каждого прямоугольника детали ближайших более тонких соседей, которыми можно заменить их так, чтобы пачка была
а) Нужной толщины
б) С минимальной разницей между толщиной пачки и максимальной толщиной.

Comments

[Родион Альметов]

Отличное решение. Я его самым первым пробовал (по габаритам).
Сейчас пока этот вариант рабочий, но визуально я вижу, что можно сделать еще лучше (хочу совместить этот способ с комбинаторикой, и на каждом шаге попробовать сочетания перебирать из подходящих прямоугольников)