Ответ 1
Это называется проблемой упаковки бутылок/резки/рюкзаком, и это NP трудно. В общем, вы можете получить приблизительное решение, используя эвристику, например,
http://en.wikipedia.org/wiki/Knapsack_problem
Алгоритм заполнения
У меня есть ящик с некоторой размерной длиной, шириной, высотой.
У меня есть элементы с разной длиной, шириной, высотой.
Существует ли существующий алгоритм, который может определять лучшие элементы, которые нужно использовать для размещения внутри поля?
Ответы
Ответ 2
Возможно, это не ответ, но я верю, что проблема в том, что проблема неопровержима. Да, это вариант проблемы с упаковкой. Но взгляните на исследования Эриха Фридмы в двух измерениях: Кажется, проблема прямоугольников равного размера в квадрате еще не решена - Посмотрите на сложность некоторых из этих решений!
http://www2.stetson.edu/~efriedma/squinsqu/
http://www2.stetson.edu/~efriedma/rigidrect/
(Проблема возникает несколько иначе, то есть, как наилучшим образом организовать определенное количество элементов, занимающих наименьшее пространство, в отличие от выбора каких элементов. Но я ожидаю, что ваша проблема будет уменьшаться для повторения такого рода вычислений по нескольким комбинациям объекты.)
и трехмерный вариант, который выглядит только частично решенным: http://www2.stetson.edu/~efriedma/cubincub/
Предположительно, ваш лучший выбор - это эвристика, как предлагает Андерс, хотя почти наверняка будет субоптимально для почти каждой проблемы. Интересно, что наиболее оптимальные решения выглядят сильно нерегулярными, поэтому вы, вероятно, не найдете их.