Проблема с укладкой коробки
Проверьте класс FileUtils в Apache Commons - в частности iterateFiles :
Позволяет итерацию по файлам в данной директории (и, необязательно, его подкаталоги).
blockquote>
4 ответа
Я думаю вы можете решить эту проблему, используя алгоритм динамического программирования самой длинной возрастающей подпоследовательности : http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
Учет поворотов достаточно прост: для каждого башня все, что вам нужно проверить, это то, что произойдет, если вы используете ее высоту как длину основания и ее ширину как высоту, и что произойдет, если вы используете ее естественным образом. Например:
=============
= =
= =
= = L
= H =
= =
= =
=============
W
Становится чем-то вроде (да, я знаю, что это выглядит совсем не так, как должно, просто следуйте обозначениям):
==================
= =
= =
= W = L
= =
= =
==================
H
Итак, для каждого блока у вас фактически есть 3 блока, представляющих его возможные вращения. Отрегулируйте массив блоков в соответствии с этим, затем отсортируйте, уменьшив базовую площадь, и просто примените алгоритм DP LIS для получения максимальной высоты.
Адаптированное повторение: D [i] = максимальная высота, которую мы можем получить, если последняя башня должна быть i.
D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)
Answer is the max element of D.
См. Видео, объясняющее это здесь: http://people.csail.mit.edu/bdean/6.046/dp/
Я предлагаю вам создать дерево (или какую-то древовидную структуру) и проанализировать его с помощью поиска по глубине, вычислив максимальную высоту по индивидуальной вертикальной "высоте" (в зависимости от вращения) значения.
Это (я думаю, что это основной подход).
Подробности по сравнению с деталями:
Корень Дерева должен быть полом, на котором умещается любой куб. Оттуда вы просто создаете дочерние узлы возможных следующих (блоков, которые могут быть размещены в определенном повороте поверх текущего блока). Сделайте это рекурсивно для каждого поворота блока и .
Когда дерево будет построено, пройдите через него и рассчитайте общую высоту башни от этажа до листа дерева.
Стек можно рассматривать как последовательность триплетов x,y,z (x,y - двумерная плоскость, а z - высота), где x(i) > x(i+1) и y(i) > y(i+1). Цель - максимизировать сумму z при выборе триплетов из множества доступных триплетов - каждый триплет представляет собой один тип ящика в определенной ориентации. Легко видеть, что соблюдение ограничения x > y не уменьшает пространство решений. Таким образом, каждый ящик порождает 3 триплета, каждый из которых имеет координаты w, h, d в качестве координаты z.
Если рассматривать триплеты как направленный ациклический граф, где ребра длины z существуют между двумя триплетами, когда между ними выполняются ограничения x,y, то задача сводится к нахождению самого длинного пути через этот граф.
Давайте сначала попробуем решить эту проблему в 2-D:
скажем, у вас есть прямоугольники с X и Y, и вопрос аналогичен (самая высокая башня, но на этот раз вам нужно беспокоиться только об одном базовом измерении).
поэтому сначала вы просматриваете всю коллекцию, дублируя каждый прямоугольник, поворачивая его на 90 градусов (меняя местами X и Y), за исключением квадратов (где X (1) = X (2) && Y ( 1) = Y (2)). здесь представлены все возможные варианты.
затем вы сортируете их по X-стороне, от наибольшего к наименьшему. в случае повторяющегося значения X вы удаляете тот, у которого значение Y меньше.
тот же принцип применяется в 3-D сценарии, только теперь вы НЕ просто умножаете размер коллекции на 6 (все возможные варианты W, H, D), а на 2. вы делаете это, отклоняя все варианты, в которых ширина меньше глубины (поэтому для каждого i W (i)> = D (i)), а затем отклонить вариант, в котором высота не является ни самым высоким, ни самым низким из трех измерений (потому что два других варианта могут поставить один на другой, и этот не может присоединиться). опять же, вы также отклоняете дублирование (где W (1) = W (2) && H (1) = H (2) && D (1) = D (2)).
Затем вы должны отсортировать по ширине, только на этот раз вы не выбрасываете варианты с той же шириной (потому что один может поместиться в башне, а другой нет), тогда вы можете использовать алгоритм LIS как описанный выше @IVlad:
D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.
уловка заключалась в том, что вы знаете, что ширина самая длинная из двух, поэтому вы знаете, что первый элемент не поместится поверх любого последующего элемента.