Какой алгоритм выбрать для двумерной упаковки?

Question

[Азат]

Здравствуйте. Помогите пожалуйста выбрать алгоритм для данного случая двумерной упаковки:
Имеются прямоугольные объекты, которые нужно разместить в ломанной области. Пример такой области (на картинке заштрихована):

Этот алгоритм хочу использовать для решения подзадачи трехмерной упаковки контейнера (послойно). Помогите пожалуйста.

Answer 1

[Андрей]

Почитайте форум и success story вот отсюда :
https://www.kaggle.com/c/packing-santas-sleigh

Comments

[Азат]

Спасибо! Подскажите пожалуйста почему там высота контейнера от 1 до бесконечности? Не очень понимаю такую постановку задачи, когда одна из сторон контейнера не ограничена

[Андрей]

Это по сути дуальные задачи:
1) можно ограничить объем контейнера и определять победителя по максимальному количеству размещенных коробок из набора;
2) а можно потребовать обязательно разместить все коробки, но победителя выявлять по минимально потребовавшейся высоте контейнера.

Answer 2

[GavriKos]

Гуглите "задача об укладке рюкзака"

Answer 3

[aynur_safin]

Гуглите "задача об упаковке в контейнеры" или "Bin packing problem".
https://en.wikipedia.org/wiki/Bin_packing_problem

Искал решение для своих задач, вот несколько ссылок.

Неплохая реализация решения BPP в Excel.
Прямо в Excel можно задавать все параметры (кол-во и размеры коробок и элементов) и получить готовое решение и даже визуализацию результата.
verolog.deis.unibo.it/bpp-spreadsheet-solver

Статья на Хабре, описание алгоритмов, есть пример реализации.
https://habrahabr.ru/post/136225/

Больше всего мне подошли решения этого автора.
Лучшее сочетание - время выполнения/результат.
clb.demon.fi/projects/rectangle-bin-packing
clb.demon.fi/projects/more-rectangle-bin-packing
clb.demon.fi/projects/even-more-rectangle-bin-packing
Реализация:
https://github.com/juj/RectangleBinPack

Последние я и использовал, переделав под свои потребности.
Пришел к такому, что я использую сразу несколько алгоритмов,
меняя их в процессе выполнения, и рандомно меняя параметры подбора элементов для упаковки.