IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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
    Futur Membre du Club
    Homme Profil pro
    MDW
    Inscrit en
    Janvier 2018
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : MDW

    Informations forums :
    Inscription : Janvier 2018
    Messages : 6
    Points : 5
    Points
    5
    Par défaut 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


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 582
    Points
    188 582
    Par défaut


    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 (tutoriels, FAQ, traductions) ou 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
    Homme Profil pro
    https://rplusplus.com/
    Inscrit en
    Février 2018
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : https://rplusplus.com/
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2018
    Messages : 12
    Points : 35
    Points
    35
    Par défaut
    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 émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut 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
    Expert confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    Mai 2013
    Messages
    1 317
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : Mai 2013
    Messages : 1 317
    Points : 4 124
    Points
    4 124
    Par défaut 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
    Futur Membre du Club
    Homme Profil pro
    MDW
    Inscrit en
    Janvier 2018
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Tunisie

    Informations professionnelles :
    Activité : MDW

    Informations forums :
    Inscription : Janvier 2018
    Messages : 6
    Points : 5
    Points
    5
    Par défaut
    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.

Discussions similaires

  1. Réponses: 12
    Dernier message: 27/08/2007, 13h33
  2. Réponses: 3
    Dernier message: 19/05/2006, 16h54
  3. [UML]résoudre un problème de classe
    Par maraly dans le forum Diagrammes de Classes
    Réponses: 2
    Dernier message: 26/04/2006, 12h24
  4. [Mail] Le php pourrait il résoudre mon problème???
    Par mayoouketchup dans le forum Langage
    Réponses: 3
    Dernier message: 20/12/2005, 14h10
  5. Comment utiliser Developpez.com pour résoudre votre problème
    Par Anomaly dans le forum Mode d'emploi & aide aux nouveaux
    Réponses: 0
    Dernier message: 08/01/2005, 12h11

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo