укладка блоков в теории графов

Question

Пожалуйста, помогите мне найти хорошее решение этой проблемы.

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

Например, у нас есть 3 измерения w * D * h, мы можемпокажите это (h * d, d * h, w * d, d * W, h * w, w * h), пожалуйста, помогите мне решить это в теории графов.в этой задаче мы не можем поставить (2 * 3) выше (2 * 4), потому что он имеет одинаковую ширину. поэтому размер 2 должен быть меньше, чем поле

Answer 1

Редактировать: Работает только в том случае, если окна нельзя вращать вокруг всех осей.

Если я правильно понимаю вопрос, его можно решить с помощью динамического программирования. Простой алгоритм определения высоты максимального стека:

Начните с поворота всех ящиков так, чтобы для Ящика B_i w_i <= d_i. Это занимает время O (n). </p>

Теперь рассортируйте поля по нижней области w_i * d_i, и пусть индексирование покажет это. Это занимает время O (n log n).

Теперь B_i можно поместить в B_j, только если i

Самый большой стек с B_j на вершине равен либо

• B_j на земле
• Стек из первых коробок j-1 с B_j сверху.

Теперь мы можем создать рекурсивную формулу для вычисления высоты максимального стека

H (j) = max (h_j, max (H (i) | i

и вычисляя max (H (j), i <= j <= n), мы получаем высоту максимального стека. </p>

Если нам нужен фактический стек, мы можем прикрепить некоторую информацию к функции H и запомнить индексы.

Answer 2

ОБНОВЛЕНО (правильно? Но, возможно, не самое эффективное):

Каждый блок становится 3 вершинами (назовите эти вершины связанными).Получите взвешенный DAG.Измените алгоритм, описанный здесь Сортируйте топологически (игнорируя тот факт, что некоторые вершины связаны), следуйте алгоритму, но вместо массива целых чисел сохраняйте список путей, которые ведут к каждой вершине.Затем при добавлении путей для новой вершины ('w' в wiki alg) составьте список путей, которые ведут туда, отбрасывая пути к v, которые содержат вершину, связанную с w.В отличие от исходного алгоритма, он является экспоненциальным.

ОРИГИНАЛЬНЫЙ НЕПРАВИЛЬНЫЙ ОТВЕТ (см. Комментарии):

Каждый блок становится 3 узлами для его 3 размеров поверхности.Затем создайте ориентированный граф, соединяющий каждую поверхность со всеми поверхностями меньших размеров.Присвойте цену каждому ребру, чтобы она была равна 3-му измерению узла (то есть высоты), к которому ведет ребро.Теперь это проблема поиска проблемы самого длинного пути в DAG .