radar4ick
@radar4ick
web-developer

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

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

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

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

Рад буду любым идеям.
  • Вопрос задан
  • 104 просмотра
Решения вопроса 2
Adamos
@Adamos
Берете задачу о рюкзаке и приспосабливаете к своим условиям.
Если прямоугольников меньше сотни - полный перебор с выбором оптимального решения займет считанные секунды.
Если нет - ищете, где вы налажали.
Если не найдете - меняйте язык на не создающий объекты в памяти без спроса.
Ответ написан
@Sumor
Всё сводится к классическим задачам оптимизации. Скорее всего ваша задача очень похожа на задачу об укладке рюкзака.
Решается, скорее всего, динамическим программированием или ветвями и границами.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@dimoff66
Кратко о себе: Я есть
Родион Альметов,

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы