Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Résoudre un problème d'emballage


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Résoudre un problème d'emballage
    Bonjour,

    J'ai besoin de votre aide.

    Je suis à la recherche d'une solution pour problème d'emballage.

    L'explication du problème est la suivante

    Une Société spécialisée en déménagement envisage toujours le
    même problème lorsqu’il s’agit de transporter des affaires d’un site à un
    autre. Le problème consiste à minimiser le nombre de boites qu’elle doit
    utiliser pour transporter des objets. Minimiser le nombre de boites conduit
    par la suite à minimiser le nombre de voyages à effectuer entre les deux
    sites, ce qui veut dire aussi être plus compétitif.

    Pour pouvoir transporter les objets, les employés doivent les ranger
    dans des boites de même taille et de mêmes caractéristiques. Les boites ont
    des volumes fixes et identiques, et peuvent porter le même poids maximal.

    De manière plus formelle nous définissons le problème comme suit :
    nous disposant de N objets ayant chacun un volume vi et un poids pi, i =1, 2,
    …, N. Nous voulons ranger ces objets dans des boites ayant toutes le même
    volume V et pouvant toutes accueillir un poids maximal = P.

    Nous admettons que chaque objet peut tenir dans une boite : les vi <
    V et tous les pi <P.

    Nous voulons trouver une manière pour ranger tous ces objets dans
    un nombre minimale de boites. La solution cherchée doit vérifier les
    contraintes suivantes :

    - chaque objet doit être rangé dans une boite.
    - pour chaque boite, le volume total des objets qu’elle contient < V.
    - pour chaque boite, le poids total des objets qu’elle contient < P.
    Travail demandé :
    1. Écrire un programme dans un langage de votre choix qui :
    • saisit des données relatives aux boites et aux objets;
    • calcule le nombre minimale de boites nécessaires pour ranger
    l’ensemble des objets;
    • affiche les détails de la solution.

    Est-ce même une légère aide?

  2. #2
    Responsable Qt & Livres



    Tu nous donnes un énoncé, mais pas de véritable question… Qu'est-ce qui te pose problème, ici ? Qu'as-tu déjà fait, tenté ?
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Nouveau membre du Club
    Dans un premier temps, le plus simple est probablement d'adopter une approche systématique, basée sur quelque chose du type "on essaye toutes les possibilités". Cela est bien sûr très couteux en temps, même pour un ordinateur, une fois que le nombre de boites et d'objets augmente. Mais on va se restreindre pour le moment aux cas "petit".

    Cette approche doit déjà permettre de faire un programme qui donne une solution juste. La suite (qui n'est pas obligatoire si on s'en tient strictement à l'énoncé, mais le sera dans la vrai vie) consiste à optimiser cette méthode. Peut-on exclure certaines combinaisons sans avoir à les tester jusqu'au bout ? Peut-on utiliser des heuristiques pour trouver une solution approchée en un temps plus raisonnable ?

  4. #4
    Membre chevronné
    Résoudre un problème d'emballage
    Bonjour,

    Il faut d'abord constituer le tableau (T0) d'enregistrements, dont chacun caractérise un objet par son poids, son volume, ainsi que le rang de la boîte dans laquelle il sera rangé (cet indice étant initialement nul).
    De ce tableau peuvent être déduits deux autres, dans lesquels les objets sont classés selon l'ordre décroissant de leur poids (TP) ou de leur volume (TV).

    On remplit ensuite la première boîte jusqu'à l'épuisement des choix en prenant systématiquement:
    - soit l'objet de volume maximal compatible avec le volume encore disponible (Vi < V'1), et de poids inférieur à la limite correspondante (Pi < P'1), en travaillant sur le tableau (TV);
    - soit l'objet de poids maximal compatible avec le poids encore disponible (Pi < P'1), et de volume inférieur à la limite correspondante (Vi < P'1, en travaillant sur le tableau (TP);
    - soit encore l'objet présentant le meilleur taux de remplissage g = (Vi/V'1) + (Pi/P'1) calculable sur le tableau initial (T0), l'objet vérifiant toujours les mêmes conditions:
    (Vi < V'1) et (Pi < P'1) .
    On affecte la valeur (1) à l'indice (n) des objets ainsi sélectionnés.

    On remplit de même la seconde boîte à l'aide des objets restants, (n) passant désormais de (0) à (2), puis à la troisième et ainsi de suite jusqu'au rangement complet.

    Le procédé est arbitraire, mais conduit intuitivement à un arrangement suffisamment compact pour être acceptable; ses trois variantes permettent d'ailleurs la comparaison des nombres de colis constitués.

    Et rien n'interdit de voir ce que donnerait le fait d'opérer selon l'ordre croissant des valeurs considérées (procédé probablement moins efficace).

    À titre de comparaison, on peut considérer:
    - le nombre maximal de boîtes, égal au nombre total d'objets (Ntot);
    - les valeurs moyennes du nombre de boîtes déductibles de celles du poids et du volume des objets;
    NV = V/VB = (Vtot/Ntot)/VB ;
    NP = P/PB = (Ptot/Ntot)/PB ;
    - le nombre minimal de colis, qui est celui des objets dépassant simultanément la moitié des deux limites permises, et vérifiant:
    Vi > VB/2 et Pi > PB/2 .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  5. #5
    Membre éclairé
    Sac à dos ?
    Bonjour,

    A brûle-pourpoint, le facteur discriminant semble la densité moyenne Do=<Po/Vo> des objets et Du=<Pu/Vu> des caisses (u pour utile). Comme les caisses sont apparemment identiques donc Du=<Pu/Vu> = Pu/Vu. Si Do > Du, le critère premier de rangement sera le poids sinon ce sera le Volume.

    Ensuite l'axe de travail proposé par wiwaxia semble intéressant. Cependant il semble que le meilleur taux de remplissage dépende plus du Di/Du le plus proche de 1 (soit minimiser (1-di/du)² car alors g = 1/(1-di/du)²).

    Ce ne sont que des pistes qui méritent - ou pas - d'être explorées.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  6. #6
    Candidat au Club
    Citation Envoyé par wiwaxia Voir le message
    Bonjour,

    Il faut d'abord constituer le tableau (T0) d'enregistrements, dont chacun caractérise un objet par son poids, son volume, ainsi que le rang de la boîte dans laquelle il sera rangé (cet indice étant initialement nul).
    De ce tableau peuvent être déduits deux autres, dans lesquels les objets sont classés selon l'ordre décroissant de leur poids (TP) ou de leur volume (TV).

    On remplit ensuite la première boîte jusqu'à l'épuisement des choix en prenant systématiquement:
    - soit l'objet de volume maximal compatible avec le volume encore disponible (Vi < V'1), et de poids inférieur à la limite correspondante (Pi < P'1), en travaillant sur le tableau (TV);
    - soit l'objet de poids maximal compatible avec le poids encore disponible (Pi < P'1), et de volume inférieur à la limite correspondante (Vi < P'1, en travaillant sur le tableau (TP);
    - soit encore l'objet présentant le meilleur taux de remplissage g = (Vi/V'1) + (Pi/P'1) calculable sur le tableau initial (T0), l'objet vérifiant toujours les mêmes conditions:
    (Vi < V'1) et (Pi < P'1) .
    On affecte la valeur (1) à l'indice (n) des objets ainsi sélectionnés.

    On remplit de même la seconde boîte à l'aide des objets restants, (n) passant désormais de (0) à (2), puis à la troisième et ainsi de suite jusqu'au rangement complet.

    Le procédé est arbitraire, mais conduit intuitivement à un arrangement suffisamment compact pour être acceptable; ses trois variantes permettent d'ailleurs la comparaison des nombres de colis constitués.

    Et rien n'interdit de voir ce que donnerait le fait d'opérer selon l'ordre croissant des valeurs considérées (procédé probablement moins efficace).

    À titre de comparaison, on peut considérer:
    - le nombre maximal de boîtes, égal au nombre total d'objets (Ntot);
    - les valeurs moyennes du nombre de boîtes déductibles de celles du poids et du volume des objets;
    NV = V/VB = (Vtot/Ntot)/VB ;
    NP = P/PB = (Ptot/Ntot)/PB ;
    - le nombre minimal de colis, qui est celui des objets dépassant simultanément la moitié des deux limites permises, et vérifiant:
    Vi > VB/2 et Pi > PB/2 .
    Merci, frère, pour l'excellente explication de votre part.
    Je l'appliquerai en Java et je vous montrerai bientôt le résultat.