Inscription / Connexion Nouveau Sujet
Niveau école ingénieur
Partager :

Est-ce que tout rentre ?

Posté par
elyos
31-08-21 à 09:13

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!

Posté par
ty59847
re : Est-ce que tout rentre ? 31-08-21 à 09:29

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...)

Posté par
elyos
re : Est-ce que tout rentre ? 31-08-21 à 10:02

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 ?

Posté par
ty59847
re : Est-ce que tout rentre ? 31-08-21 à 11:48

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.

Posté par
elyos
re : Est-ce que tout rentre ? 01-09-21 à 13:59

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 :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !