Bonjour,
Premier post ici, donc désolé si je n'écris pas dans la bonne partie.
Question simple. Résolution complexe...
Soit un contenant de forme parallélépipède rectangle défini par L x l x H (L : Longueur / l : largeur / H : Hauteur).
Soit n éléments de forme parallélépipède rectangle définis par Ln x ln x Hn (Ln : Longueur / ln : largeur / Hn : Hauteur).
Outre le fait de vérifier que chaque élément soit bien plus petit que le contenant et que la somme des volumes est plus petite que le volume du contenant, comment vérifier que les n éléments rentrent bien, ensemble, dans le contenant ?
Je ne sais pas si c'est clair ?
Pour faire plus simple , un déménageur souhaite savoir si tous les cartons (éléments) de déménagement rentrent dans son camion (contenant).
Merci d'avance pour toutes les pistes que vous pouvez me donner!
C'est un exercice très compliqué.
Il y a une question subsidiaire, c'est : quelles sont les positions autorisées.
Pour chaque carton, tu parle de L x l x H. Ok
Tu ne dis pas a x b x c.
Donc ça sous-entend peut-être que la hauteur joue un rôle particulier. Chaque carton a un fond et 4 côtés, et il doit bien être posé sur le fonc, pas sur une des faces.
Ce qui limite un tout petit peu les marges de manoeuvre.
Il y a donc cette question à clarifier.
Par ailleurs, on va supposer que toutes les dimensions sont des entiers. Quitte à mesurer les longueurs en millimètres.
Pour moi, le mot clé pour faire des recherches, c'est le mot combinatoire, ou le mot 'parcours d'arbre'.
Pourquoi parcours d'arbre ?
On choisit un coin du camion.
On a le choix entre n cartons à placer dans ce coin, et 2 orientations possibles pour chaque carton. Donc 2n options.
Puis on prend l'emplacement juste à côté, on a le choix de ne rien mettre à cet endroit, ou on peut choisir entre n-1 cartons, 2 orientations possibles.
Donc notre arbre a déjà 2n*(2n-1) branches ...
etc.
On explore toutes les branches de cet arbre.
Pour optimiser, on explore prioritairement les branches les plus discriminantes (celles où on place les gros cartons d'abord...)
Pour l'instant, on suppose que tous les "fonds" doivent être posés au sol.
Par la suite, on pourra compliquer la chose en supposant que certains cartons peuvent être posés sur n'importe quelle côté.
Il faut donc trier les cartons du plus gros au plus petit pour les "caser" en partant d'un coin.
Mais "du plus gros au plus petit", c'est par rapport à la surface au sol occupé c'est bien ça ?
Les trier du plus gros au plus petit n'est pas une obligation, c'est juste une optimisation. Ou plutôt une tentative d'optimisation.
Si on place un petit , puis un qui est très haut, mais pas forcémént très grand (largeur et longueur), puis à nouveau un petit , on sent bien qu'on condamne des espaces.
Du plus gros au plus petit, je verrai plutôt ça selon le volume. Mais c'est juste une suggestion.
Instinctivement, on sent que si on vient de placer un objet (a x b x c), si on veut coller un autre objet contre la face (a x b), on a intérêt à trouver un autre objet avec des dimensions proches de (a x b).
Par curiosité, je viens de faire quelques recherches, et je suis tombé par exemple sur
208 pages sur un sujet assez similaire ... dont la partie bibliographie page 180, pour éventuellement trouver encore d'autres documentations sur le sujet.
Merci pour le lien qui m'a permis également d'approfondir la recherche.
Et j'étais très loin de m'imaginer que c'était aussi complexe (à priori y'a pas mal de méthodes différentes avec des résultats plus ou moins différents).
Et là, je me dis qu'en plus, je vais voir des contraintes supplémentaires... certains cartons empilables, d'autres non, si empilable, du plus lourd au plus léger, certains cartons ne peuvent être posés que sur une seule face (2 positions) et d'autres sur toutes les faces (6 positions).
Je sens que je m'embarque sur une résolution assez fastidieuse ^^'
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :