Постановка задачи :
Стопка ящиков. Вам дан набор из n типов прямоугольных трехмерных ящиков, где i^-й ящик имеет высоту h(i), ширину w(i) и глубину d(i) (все действительные числа). Вы хотите создать максимально возможную высоту стопки коробок, но вы можете поставить коробку поверх другой коробки только в том случае, если размеры двумерного основания нижнего ящика строго больше, чем размеры двухмерного основания. D основание более высокого ящика. Конечно, вы можете повернуть коробку так, чтобы любая сторона служила ее основанием. Также допускается использование нескольких экземпляров ящика одного типа.
Объяснение :
Давайте подумаем об этом в реальной жизни без кода. Допустим, у нас есть 2 коробки.
А -> (2,2,4) и Б -> (9,7,3)
У нас есть неограниченный запас ящиков типа А и В. Теперь ограничение состоит в том, что ящик можно разместить над другим ящиком только тогда, когда нижний ящик имеет соответственно строго большие размеры. Это означает, что A в текущей конфигурации не может быть размещен над коробкой B (длина A равна 2, тогда как B имеет 9, поэтому в длину все в порядке, но A имеет высоту 4, а B имеет 3, поэтому A не может быть размещен поверх B как 4). ›3).
Теперь мы можем повернуть коробку так, чтобы каждая коробка давала нам 6 конфигураций (3! = 3x2x1). Теперь для 2 ящиков у нас всего 12 конфигураций, и мы должны выровнять их так, чтобы получить максимальную высоту с ограничением, что ящик внизу должен иметь строго больший размер, чем ящик над ним.
Когда у нас есть 12 конфигураций для двух вышеупомянутых ящиков, мы можем отсортировать их по любому измерению (длина, ширина или высота). Зачем мы это делаем? Допустим, мы сортируем коробки по возрастанию высоты.
{(7,3,9),(3,7,9),(9,3,7),(3,9,7),(2,2,4),(2,2,4),(9,7,3),(7,9,3),(4,2,2),(4,2,2),(2,4,2),(2,4,2)}
Теперь мы знаем, что по мере того, как мы идем вправо по этому списку, мы уверены, что ящик справа от этого списка определенно не может быть внизу ни одного из ящиков слева от него, потому что высота уменьшается по мере того, как мы продвигаемся к вершине. верно.
Допустим, в отсортированном выше списке мы хотим узнать максимальную высоту стека, если ящик в i-й позиции находится наверху стека. Предположим, что «i» равно 4, то есть ящик (2,2,4). Теперь наша главная проблема
getMaxStackHeight (стек Box [], int index (4)) = max {
getMaxStackHeight(Box[] shuffledStack, int index(3)),
getMaxStackHeight(Box[] shuffledStack, int index(2)),
getMaxStackHeight(Box[] shuffledStack, int index(1)),
getMaxStackHeight(Box[] shuffledStack, int index(0))
} + текущая высота (4)
Повторяющуюся функцию можно рассматривать как:
getMaxStackHeight(Box[] стек, n) = Max ((i 1 to n-1)getMaxStackHeight(Box[] стек, i) + currentHeight.
Проще говоря, если ящик с номером i = 4 должен быть наверху стопки, тогда высота может быть либо просто высотой этого ящика, т. е. 4, либо максимальной из возможных стопок, имеющих ящик с номером I = 3. , 2, 1 и 0 вверху плюс высота текущего блока. Сделайте паузу и поймите это. Это означает, что у нас есть 5 возможных стеков — один с i = 4 наверху, затем i = 3 и так далее. Также, когда i = 0, то есть стек, в котором есть только первый ящик и, следовательно, он находится наверху, будет нашим базовым случаем и вернет высоту ящика при i = 0.
Как только мы это поймем, все остальное — просто использование вышеприведенной логики в коде.
import java.util.*;
public class StackOfBoxes{
static void print(Box[] boxStack){
for(Box box : boxStack){
System.out.print(box.toString() + ",");
}
}
private Box[] getShuffledStack(Box[] boxStack){
int size = boxStack.length*6;
Box[] shuffledStack = new Box[size];
for(int i = 0 ; i < boxStack.length;i++){
Box box = boxStack[i];
shuffledStack[6*i] = new Box(Math.max(box.length,box.breadth),Math.min(box.length,box.breadth),box.height);
shuffledStack[6*i+1]=new Box(Math.max(box.height,box.breadth),Math.min(box.height,box.breadth),box.length);
shuffledStack[6*i+2]=new Box(Math.max(box.length,box.height),Math.min(box.length,box.height),box.breadth);
shuffledStack[6*i+3] = new Box(Math.min(box.length,box.breadth),Math.max(box.length,box.breadth),box.height);
shuffledStack[6*i+4]=new Box(Math.min(box.height,box.breadth),Math.max(box.height,box.breadth),box.length);
shuffledStack[6*i+5]=new Box(Math.min(box.length,box.height),Math.max(box.length,box.height),box.breadth);
}
return shuffledStack;
}
private int getMaxStackHeight(Box[] shuffledStack){
int height = 0;
for(int i = 0 ; i < shuffledStack.length ; i++){
int maxHeight = getMaxStackHeight(shuffledStack,i);
height = Math.max(height,maxHeight);
}
return height;
}
private int getMaxStackHeight(Box[] shuffledStack, int index){
Box currentBox = shuffledStack[index];
if(index == 0){
return currentBox.height;
}
int maxHeight = 0;
Box tempBox = null;
for(int i = index -1 ; i >= 0; i--){
tempBox = shuffledStack[i];
if((tempBox.length < currentBox.length) && (tempBox.breadth < currentBox.breadth)){
int heightAtI = getMaxStackHeight(shuffledStack,i);
maxHeight = Math.max(heightAtI,maxHeight);
}
}
return maxHeight + currentBox.height;
}
public static void main(String[] args) {
StackOfBoxes stack = new StackOfBoxes();
Box[] boxStack = { new Box(2,2,4), new Box(9, 7, 3)};
Box[] shuffledStack = stack.getShuffledStack(boxStack);
Arrays.sort(shuffledStack,new SortByHeight());
int maxHeight = stack.getMaxStackHeight(shuffledStack);
System.out.println("MaxHeight : " + maxHeight);
}
static class Box{
int length;
int breadth;
int height;
Box(int length , int breadth , int height){
this.height=height;
this.length=length;
this.breadth=breadth;
}
public String toString(){
return "(" +this.length + "," + this.breadth + "," + this.height + ")";
}
}
}
class SortByHeight implements Comparator<StackOfBoxes.Box>{
@Override
public int compare(StackOfBoxes.Box b1 , StackOfBoxes.Box b2){
return b2.height - b1.height;
}
}
Максимальная высота: 12
Временная сложность = O (n²)
Пространственная сложность = O (n)
