Alignement automatique des éléments dans un tableau

Question

Je dois créer un algorithme qui alignera les éléments d'un tableau en utilisant le plus petit nombre possible de lignes.

Les éléments qui doivent être triés doivent conserver leur position/alignement horizontal.

Comme ça : [

J'espère que quelqu'un l'a déjà fait. Merci !

Answer 1

Pour clarifier : je suppose que vous voulez dire que chaque élément doit tenir sur une ligne, et une seule (il ne peut pas se détacher sur la ligne suivante), mais qu'ils peuvent se déplacer horizontalement.

Heuristiquement/naivement, je ferais comme ça :

• Trier les éléments par longueur.
• Essayez de remplir la première ligne libre en choisissant naïvement (du plus long au plus court) des éléments jusqu'à ce que la ligne soit pleine ou qu'aucun élément correspondant ne puisse être trouvé.
• Répétez l'opération jusqu'à ce que tous les éléments soient terminés.

Cela se terminera (relativement) rapidement (quelque part entre O(nlogn) et O(n^2) selon les "raccourcis" heuristiques) mais laissera plus de trous que nécessaire et donnera des solutions autrement non optimales.

Je parierais que ce problème est équivalent à l'un des problèmes classiques NP-complets. https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems Il est donc peu probable que vous trouviez une bonne solution pratique non heuristique.