Existe uma solução mais rápida que O (n ^ 2) para o problema de empilhamento de caixa?

Question

o caixa de empilhamento problema é a seguinte:

.

Você recebe um conjunto de $ n $ tipos de caixas 3-D retangulares, onde o $ i ^ {th} $ caixa tem altura $ h_i $ , largura $ w_i $ e profundidade $ D_I $ (todo real números). Você quer criar uma pilha de caixas que é tão alta quanto possível, mas você só pode empilhar uma caixa em cima de outra caixa se o Dimensões da base 2-D da caixa inferior são estritamente maiores do que os da base 2-D da caixa superior. Claro que você pode Gire uma caixa para que qualquer lado funcione como base. Isso é também permitido usar várias instâncias do mesmo tipo de caixa.

Existe uma solução mais rápida que a $ O (n ^ 2) $ solução dada aqui ?

Answer 1

Isso pode ser resolvido em $ \ mathcal {o} (n \ log ^ 2 {} n) $ usando uma estrutura de dados de consulta 2D de intervalo para otimizar A solução de programação dinâmica que foi explicada no link dado na questão:

como no link, para uma caixa na entrada com dimensões $ (w_i, d_i, h_i) $ , considere todas as rotações da caixa, mas mantenha o Propriedade que a primeira dimensão é sempre $ \ GE $ a segunda dimensão. Portanto, cada caixa de entrada corresponde a três caixas, e considera todas essas caixas de $ 3N $ e classificá-las na área decrescente da base (ou seja, o produto dos dois primeiros dimensões).

Deixe esta sequência classificada ser $ (A_1, B_1, C_1), (A_2, B_2, C_2), \ LDOTS, (A_ {3N}, c_ {3n}, c_ {3n} {3n}) $ .

Deixe $ dp [i] $ ser a altura máxima que você pode obter usando a primeira $ i $ Caixas nesta sequência, de modo que a caixa mais alta é a caixa $ i ^ {th} $ . Inicialmente $ dp [i]= 0 $ para todos $ i $ . A recorrência é

$ dp [i]= c_i + \ max _ {\ subestack {j a_i \\ b_j> b_i}} dp [j] $

Agora, em vez de gastar $ \ mathcal {O} (n) $ tempo para encontrar esta ótima $ j $ , vamos fazer isso mais rápido usando algumas estruturas de dados. Pense em cada caixa $ (A_J, B_J, C_J) $ como um ponto $ (A_J, B_J) $ Em um plano 2D, que tem um valor $ DP [J] $ . Agora o que queremos encontrar é o ponto no retângulo $ [A_I + 1, inf] \ vezes [b_i + 1, inf] $ que tem o valor máximo. Note que podemos ignorar a restrição $ j porque será implicitamente satisfeito pelas restrições dimensionais.

para isso, construa um Árvore de segmento 2D aka árvore fenwick (olhe para a seção 'compressão da árvore de segmento 2D'), usando $ a_i $ como os valores na árvore do segmento externo, e $ b_i $ como os valores nas árvores do segmento interno. Você também pode usar a maioria das outras estruturas de dados de consulta 2D de intervalo para isso.

Você pode consultar o valor máximo nesse retângulo em $ \ mathcal {o} (\ log ^ 2 {} n) $ tempo, e uma vez que você tem Computado $ dp [i] $ , você terá que atualizar esse valor em toda a $ \ mathcal {O} (\ \ Log {} n) $ árvores de segmento interno, o que daria um total de $ \ mathcal {o} (\ log ^ 2 {} n) $ tempo.

Portanto, o problema pode ser resolvido em $ \ mathcal {O} (n \ log ^ 2 {} n) $ tempo e $ \ mathcal {o} (n \ log {} n) $ espaço.