Problema de empilhamento de checkboxs

Eu encontrei este famoso problema de dp em muitos lugares, mas não consigo descobrir como resolver.

Você recebe um conjunto de n tipos de checkboxs retangulares em 3D, nas quais a checkbox tem altura h (i), largura w (i) e profundidade d (i) (todos os números reais). Você quer criar uma pilha de checkboxs que seja a mais alta possível, mas você só pode empilhar uma checkbox em cima de outra checkbox se as dimensões da base 2-D da checkbox inferior forem estritamente maiores do que aquelas das 2 D base da checkbox superior. Claro, você pode girar uma checkbox para que qualquer lado funcione como sua base. Também é permitido usar várias instâncias do mesmo tipo de checkbox.

Este problema parece muito complicado para eu descobrir os passos. Como é 3D, recebo três sequências de altura, largura e profundidade. Mas como é possível trocar 3 dimensões o problema se torna mais complicado para mim. Então, por favor, alguém explique os passos para resolver o problema quando não há troca e, em seguida, como fazê-lo ao trocar. Eu fiquei cansado do problema. Então por favor, por favor alguém explique a solução de maneira fácil.

Eu acho que você pode resolver isso usando o algoritmo de subseqüência crescente de programação dinâmica mais longa : http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Contabilizar as rotações é bastante fácil: para cada torre, tudo o que você precisa verificar é o que acontece se você usar sua altura como o comprimento da base e sua largura como a altura e o que acontece se você usá-la de maneira natural. Por exemplo:

============= = = = = = = L = H = = = = = ============= W 

Torna-se algo como (sim, eu sei que parece nada como deveria, basta seguir as notações):

 ================== = = = = = W = L = = = = ================== H 

Então para cada bloco você tem 3 blocos representando suas possíveis rotações. Ajuste sua matriz de blocos de acordo com isso, então classifique diminuindo a área de base e apenas aplique o algoritmo DP LIS para obter a altura máxima.

A recorrência adaptada é: D [i] = altura máxima que podemos obter se a última torre deve ser 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. 

Veja um vídeo explicando isso aqui: http://people.csail.mit.edu/bdean/6.046/dp/

A pilha pode ser considerada como uma seqüência de tripletes x, y, z (x, y sendo o plano 2D e z a altura), onde x (i)> x (i + 1) e y (i)> y ( i + 1). O objective é maximizar a sum de z escolher os tripletos do conjunto de trios disponíveis – cada trio sendo um tipo de checkbox em uma orientação particular. É bem fácil ver que impor a restrição x> y não reduz o espaço da solução. Portanto, cada checkbox gera três tripletos, cada um com w, h, d como a coordenada z.

Se você considera os trigêmeos como um grafo acíclico direcionado, onde as arestas de comprimento z existem entre duas trincas quando as restrições x, y são satisfeitas entre elas, então o problema é encontrar o caminho mais longo através daquele grafo.

Vamos primeiro tentar resolver esse problema em 2-D:

digamos que você tenha retângulos com X e Y, e a pergunta é semelhante (a torre mais alta, mas desta vez você só precisa se preocupar com uma dimensão base).
Então, primeiro, você percorre toda a coleção, duplicando cada retângulo girando-a 90 graus (trocando X e Y), exceto por quadrados (onde X (1) = X (2) && Y (1) = Y (2)) . isso representa todas as variações possíveis.
então você os classifica pelo lado X, do maior para o menor. no caso de um valor X duplicado, você remove aquele com o valor Y mais baixo.

Mesmo princípio aplicado no cenário 3-D, só agora você NÃO multiplica o tamanho da coleção por 6 (todas as variantes possíveis de W, H, D), mas sim por 2. faz isso descartando todas as variações em que a largura é menor que a profundidade (então para cada i, W (i)> = D (i)), e então descartando a variação onde a altura não é a mais alta nem a mais baixa das três dimensões (porque as outras duas variações podem ir uma sobre em cima do outro e este não pode participar). novamente, você também descarta duplicações (onde W (1) = W (2) & H (1) = H (2) & D (1) = D (2)).
Então você deve ordenar por largura, só que desta vez você não joga fora variações com a mesma largura (porque um pode caber em uma torre que outro não pode) então você pode usar o algoritmo LIS como descrito acima por @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. 

O truque era que você sabe que a largura é a mais longa das duas, então você sabe que o primeiro elemento não caberá em cima de qualquer elemento posterior.

Eu sugiro que você crie uma tree (ou algum tipo de estrutura de tree) e analise-a com a pesquisa de profundidade, calculando a altura máxima dos valores individuais de “altura” (depenando em rotação).

Isso (acho que esta é a abordagem básica).

Detalhes sobre detalhes:

A raiz da tree deve ser o chão, onde qualquer cubo se encheckbox. A partir daí, você cria os nós filhos da próxima checkbox possível (checkboxs que podem ser colocadas em uma certa rotação no topo da checkbox atual). Recursivamente, faça isso para cada checkbox e rotação.

Quando a tree for construída, passe por ela e calcule a altura total da torre, do chão até a folha da tree.

Uma solução para o problema consiste em três etapas.

  1. Classifique as dimensões de cada checkbox para que a comparação de duas checkboxs reduza a comparação das dimensões correspondentes.
  2. Classifique a seqüência de checkboxs lexicograficamente de modo que, para cada checkbox, as checkboxs à esquerda sejam as checkboxs que podem se encheckboxr.
  3. Aplique o algoritmo O(n^2) para o problema de subseqüência de aumento mais longo .

O terceiro passo é o mais caro e aumenta a complexidade da solução para O(n^2) . Se você gostaria de ler uma explicação completa da abordagem, como cada passo contribui para encontrar uma resposta, e código completo, dê uma olhada no post do blog que escrevi sobre o problema .