problème d'empilement de boîte

Question

J'ai trouvé ce fameux problème dp dans de nombreux endroits, mais je ne peux pas comprendre comment résoudre.

  

On vous donne un ensemble de n types de   boîtes rectangulaires en 3-D, où le i ^ e   boîte a une hauteur h (i), w (i) la largeur et la   profondeur d (i) (tous les nombres réels). Toi   veulent créer une pile de boîtes qui   est aussi grand que possible, mais vous pouvez   seulement empiler une boîte au-dessus d'une autre boîte   si les dimensions de la base 2-D de   la zone inférieure sont chacun strictement supérieur   que ceux de la base 2-D de la   boîte supérieure. Bien sûr, vous pouvez faire pivoter   une boîte de telle sorte que toutes les fonctions secondaires que   sa base. Il est également permis d'utiliser   plusieurs instances du même type de   boîte.

Ce problème me semble trop compliqué pour de comprendre les étapes. Comme il est en 3D, je reçois trois séquences de hauteur, largeur et profondeur. Mais comme il est possible d'échanger 3 dimensions le problème devient plus compliqué pour moi. Alors, s'il vous plaît quelqu'un expliquer les étapes pour résoudre le problème quand il n'y a pas swapping et comment le faire lors de la permutation. Je suis devenu fatigué sur le problème. Alors s'il vous plaît, s'il vous plaît quelqu'un expliquer la solution manière simple.

Answer 1

Je pense que vous pouvez résoudre cela en utilisant la programmation dynamique la plus longue suite croissante algorithme: http://people.csail.mit. edu / bdean / 6,046 / dp /

Answer 2

La pile peut être considéré comme une séquence de x, y, triplets z (x, y étant le plan 2D, et z la hauteur), où x (i)> x (i + 1) et y (i) > y (i + 1). L'objectif est de maximiser la somme de z ramasser les triplets de l'ensemble des triplets disponibles - chaque triplet étant un type de boîte dans une orientation particulière. Il est assez facile de voir que l'application de la contrainte x> y ne réduit pas l'espace de solution. Ainsi, chaque case génère 3 triplets, ayant chacun des w, h, d que la coordonnée z.

Si vous considérez les triplés comme un graphe orienté acyclique où les bords de existent z longueur entre deux triplés lorsque les x, les contraintes y sont réunies entre elles, le problème est de trouver le plus long chemin à travers ce graphique.

Answer 3

premier essai Let pour résoudre ce problème en 2-D:

dire que vous avez des rectangles avec X et Y, et la question est similaire (la plus haute tour, mais cette fois-ci vous avez seulement à vous soucier une dimension de base).
donc en premier lieu, vous allez sur toute la collection, la duplication de chaque rectangle en le faisant tourner de 90 degrés (permutation X et Y), à l'exception des carrés (où X (1) = X (2) && Y (1) = Y (2)) . cela représente toutes les variations possibles.
alors vous les trier par leur côté X, du plus grand au plus petit. en cas de valeur en double X, vous supprimez celle avec la valeur Y inférieure.

même principe appliqué dans le scénario 3-D, seulement maintenant vous ne multipliez que par 6 (toutes les variantes possibles du W, H, D) la taille de la collection, mais plutôt par 2. vous faites cela en rejetant toutes les variantes où les la largeur est inférieure à la profondeur (si pour chaque i, W (i)> = D (i)), puis rejetant la variation où la hauteur est la plus élevée, ni la plus faible des trois dimensions (parce que les deux autres variantes peuvent aller l'un sur l'autre et celui-ci ne peut se joindre à). de plus, on a également rejeter duplications (où W (1) = W (2) && H (1) = H (2) && D (1) = D (2)).
Ensuite, vous devez trier par largeur, mais cette fois vous ne t jetez pas les variations avec la même largeur (parce que l'on peut tenir dans une tour qu'un autre ne peut pas), vous pouvez utiliser l'algorithme de LIS comme décrit ci-dessus par @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.

l'affaire était, vous savez que la largeur est la plus longue des deux, si vous connaissez le premier élément ne tient pas au-dessus de tout élément ultérieur.

Answer 4

Je vous suggère de créer un arbre des valeurs (ou une sorte de structure arborescente) et l'analyser avec la recherche de la profondeur, le calcul de la hauteur maximale de la « hauteur » individuelle verticale (depening sur la rotation).

(je pense que c'est l'approche de base).

Détails sur les détails:

La racine de l'arbre doit être le sol, où tout cube se fixe sur. De là, vous venez de créer les nœuds enfants de possibles suivants (boîtes qui peuvent être placés dans une certaine rotation ontop de la boîte en cours) boîtes. Récursivement faire que pour chaque case et rotation.

Lorsque l'arbre est construit, allez à travers elle et CALC la tour totale du sol heigth à une feuille de l'arbre.

Answer 5

Une solution au problème consiste en trois étapes.

1. dimensions de tri pour chaque boîte de sorte que la comparaison des deux boîtiers se réduit à la comparaison de leurs dimensions correspondantes.
2. Trier la séquence de boîtes lexicographique de telle sorte que pour chaque boîte, les boîtes à gauche sont les zones qui peuvent être compatibles.
3. l'algorithme de O(n^2) pour la plus longue augmentation de Subsequence problème .

La troisième étape est le plus cher et se cogne la complexité de la solution à O(n^2). Si vous souhaitez lire une explication complète de l'approche, la façon dont chaque étape contribue à trouver une réponse, et le code complet, jetez un oeil à le blog je l'ai écrit sur le problème .