Проблема, которую я пытаюсь решить, называется укладкой ящиков.Вот описание: Укладка ящиков
Вам предоставляется набор из n типов прямоугольных трехмерных ящиков, где у i ^ -ого ящика есть высота h (i), ширина w (i) и глубина d (я) (все действительные числа).Вы хотите создать стопку коробок, которая будет как можно более высокой, но вы можете сложить коробку только над другой коробкой, если размеры двухмерной базы нижнего прямоугольника строго превышают размеры двухмерной.Буду основанием верхней коробки.Конечно, вы можете вращать коробку так, чтобы любая сторона функционировала как ее основа.Также допустимо использовать несколько экземпляров одного и того же типа ящика.
Я подумал о следующем решении: пусть одна коробка будет представлена как (h, w, d).Тогда мы можем представить последовательность всех блоков, таких как (h1, w1, d1), (h2, w2, d2), (h3, w3, d3).Чтобы позаботиться о том, чтобы мы могли использовать любое вращение, используя приведенную выше последовательность, я сгенерирую все возможные перестановки для блока.Таким образом, для блока, подобного (7,1,2), будет 6 сгенерированных конфигураций.Чтобы решить проблему, я планирую сначала отсортировать блоки по ширине в порядке убывания.Затем я получу последовательность блоков, таких как (h1, w1, d1), (h2, w2, d2) и т. Д. Затем я решу проблему, используя концепцию, аналогичную подпоследовательности с наибольшим уменьшением. Пусть LDS (i) будет самым длинным убывающимподпоследовательность заканчивается в i. Тогда LDS (i) = {max [LDS (k)] + высота i для kwi и dk> di}
Кто-нибудь видит ошибку с вышеуказанным?
Пожалуйста, дайте мне знать, если приведенное выше решение является правильным