Вопрос по calculus, algorithm – Поиск оптимальных размеров 3D-боксов для группы трехмерных прямоугольных предметов

4

Когда я говорю «коробка», я имею в виду доставку коробок.

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

All items are rectangular prisms. It's easy to exclude a box size for an item which is too large to fit. I know the box sizes (they are the available box sizes which I have in-stock) Items can be positioned horizontally or vertically, not diagonal. As many boxes as required can be used. The goal is to use as few boxes as possible. Multiple box sizes may be used to optimally fit the varying-sized items.

Какой алгоритм существует, который позволяет мне вычислять размеры ящиков, которые мне нужно использовать для оптимального использования пространства?To fit the most items into as few boxes as possible.

Доступные размеры коробок приходят из того, что у меня есть в наличии на складе. Вы можете создать конечное количество размеров готовых коробок для примера.

Так что это включает только 2 измерения? длина и ширина Francis P
@ FrancisP Cubic, длина, ширина и высота. Я не знаю Техническая слово для кубической прямоугольной формы. unixman83
@ FrancisP Слово - просто прямоугольная призма. Я редактировал это. twain249
Так как ты решил это? Есть ли готовые классы или код на PHP? Есть идеи? Написание одного займет несколько дней! John
Это звучит похоже наKnapsack которыйNP-Complete. Вы можете взглянуть на алгоритмы, чтобы приблизитьKnapsack и посмотри, сможешь ли ты адаптировать его к своим потребностям. twain249

Ваш Ответ

2   ответа
2

Knapsack проблема. Проверьте статья в Википедии для более подробной информации о подходах к проблеме, чем можно дать здесь.

«Вариант проблемы с рюкзаком» не делает его NP-завершенным. BlueRaja - Danny Pflughoeft
Этот ответ не заслуживает 0 баллов. Конечно, это не отвечает на вопрос, который я задал. Но это, вероятно, более полный ответ на проблему, с которой я сталкиваюсь. unixman83
Эй, я не сказал, что это NP завершен! Но вы можете написать целые книги на эту тему, и я не хотел пытаться описать это в 100 словах или меньше. Michael Slade
Есть какие-нибудь указатели на какой-нибудь код? unixman83
7

Проблема с упаковк, то есть это NP-Hard.

Чтобы увидеть это, представьте, что все лотки и пакеты имеют одинаковую ширину и высоту, и, кроме того, все лотки (но не пакеты) имеют одинаковую длину. Тогда это одномерная проблема: у нас есть контейнеры размером V и пакеты размером a1,2, ...,n. Этот упрощенный случай является как раз проблемой бин-упаковки. Таким образом, быстрое решение вашей проблемы дает нам быстрое решение для упаковки в мусорное ведро, поэтому ваша проблема, по крайней мере, так же сложна; и поскольку упаковка в мусорное ведро NP-Hard, то и ваша проблема.

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

Похожий алгоритм "Уменьшение первой подгонки" (сортируйте элементы в порядке убывания, а затем помещайте каждый элемент в первый контейнер, в который он помещается) еще лучше, гарантируя быть в пределах 25% от оптимального решения. Существует также другой, немного более сложный алгоритм, называемый MFFD что гарантирует около 20%.

И, конечно же, имея всего 7 коробок, вы всегда можете просто перебрать решение. Это потребует около 7n шаги(гдеn - количество предметов), так что это решение невозможно с более чем дюжиной предметов.

Моя проблема в том, что размеры ящиков, которые я выберу, частично зависят от общего объема предметов. Пример. Многие мелкие предметы дешевле отправлять в больших коробках ИБП, чем во многих маленьких коробках с фиксированной ставкой USPS. то есть, когда общий объем увеличивается, этообычн лучше использовать большую корзину. unixman83
Да. Спасибо, что ответили на проблему с примеркой пространства, которая у меня была. Это определенно помощь. unixman83
@ unixman83: -_- Вопрос затрагивает размещение элементов в наименьшем количестве полей, ничего не говорит о ценности. Я думаю, вы обнаружите, что ваша новая проблема - это обобщение рюкзака, поэтому вам все еще не повезло с поиском оптимального решения: \ Попробуйте найти некоторые приближения рюкзака. BlueRaja - Danny Pflughoeft

Похожие вопросы