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 :

Meilleure combinaison possible avec plusieurs choix


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau candidat au Club
    Homme Profil pro
    Développeur Web
    Inscrit en
    Janvier 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Janvier 2017
    Messages : 2
    Par défaut Meilleure combinaison possible avec plusieurs choix
    Bonjour à tous,

    Je cherche à faire un algorithme mais je sèche complètement.
    Je vous explique le truc :

    - Le but c'est de former la meilleure combinaison possible de 5 joueurs (c'est pour le jeu de l'entraineur pour ceux qui connaissent) pour former la meilleure équipe. Chaque joueur a un prix et un niveau.

    Les contraintes :

    - Le prix total doit pas dépasser X
    - Il faut choisir 1 gardien, 2 milieux, 2 attaquants
    - Un autre critère est de prendre 3 joueurs max de la même équipe mais je pourrais m'en passer.

    J'ai donc une table gardien de 10 choix, 1 table milieux de 25 choix, 1 table attaquants de 25 choix.

    Et là je sèche, mon idée était de faire toutes les combinaisons possibles en ne stockant que celle dont le prix était <= X et de les trier par valeur, déjà je sais pas trop comment faire mais surtout, je ne sais pas si la solution est optimale, si vous avez des idées !

    Merci

  2. #2
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 489
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 489
    Par défaut
    salut

    de façon brutale tu as 5 boucle a faire
    1 sur la table des gardien
    2 sur la table des milieux
    2 sur la table des attaquants

    vu le nombre d’éléments le temps n'est pas determinant

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
      Pour chaque occurrence Igardien de la table Gardien Faire 
         Pour chaque occurrence Imil1 de la table Milieux Faire 
            Pour chaque occurrence Imil2 de la table Milieux Faire 
               Pour chaque occurrence IAtaq1 de la table Attaquants Faire 
                 Pour chaque occurrence IAtaq2 de la table Attaquants Faire 
                      si Attaquants[IAtaq1] <>  Attaquants[IAtaq2] alors
                        si Milieux[Imil1] <>  Milieux[Imil2] alors
                           PrixTot := Gardien[Igardien].prix+Milieux[Imil1].Prix+Milieux[Imil2].prix + Attaquants[IAtaq1].prix+Attaquants[IAtaq2].prix;
                           si PrixTot <= PrixMax alors
                              Ok  =  TestMaxNbSameEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])
                              si  Ok alors 
                                 AddEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])     
                           FinSi                             
                        Fin si  
                      Fin Si
                 Fin Pour
               Fin Pour
            Fin Pour
         Fin Pour
      Fin Pour
    voici un algo basique, il est loin d’être optimisé mais il a le mérite de jeter les bases sur lesquels tu doit plancher

  3. #3
    Nouveau candidat au Club
    Homme Profil pro
    Développeur Web
    Inscrit en
    Janvier 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Janvier 2017
    Messages : 2
    Par défaut
    Hello,

    Merci de ton retour, c'est à peu près ce que j'ai fait au mot près mais j'imaginais qu'il y avait une manière plus propre que 5 boucles imbriquées. Bon je laisse comme ça pour le moment, si y'en a qui on des suggestions entre temps, n'hésitez pas !

  4. #4
    Membre Expert
    Homme Profil pro
    Inscrit en
    Mai 2008
    Messages
    2 040
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Mai 2008
    Messages : 2 040
    Par défaut
    Bonjour,

    Je ferais comme cela :
    - Trois tableaux pour - Gardiens - Milieux - Attaquants
    - On tire au hasard : 1 gardien, 2 Milieux, 2 Attaquants
    - On prend comme critère : moins de x Euros ET meilleure note de l'équipe tirée au hasard
    - On fait N tirages (1000 par exemple)
    - On garde en mémoire la meilleure équipe.

    Un exemple avec Matlab (pour 10 joueurs) :
    Code matlab : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    % Tableaux :  Numéro   Prix   Note
    %Gardiens
    G=[1 150 12;
       2 250 9;
       3 600 18;
       4 320 13;
       5 141 17
       6 100 12;
       7 40 4;
       8 80 19;
       9 90 9;
       10 125 11];
    % Milieu de terrain
    M=[1 15 12;
       2 95 19;
       3 160 18;
       4 32 13;
       5 241 17;
       6 120 10;
       7 50 6;
       8 200 18;
       9 140 15;
       10 50 8];
    % Attaquants
    A=[1 100 12;
        2 125 9;
        3 60 18;
        4 32 13;
        5 541 17
        6 100 16;
        7 400 19;
        8 100 11;
        9 250 15
        10 100 18];
     
    Prix_max=800;
    Equipe=[];
    SNR=0;
    NbG=10;
    NbM=10;
    NbA=10;
    SER=0;
    SERP=0;
    Nb_Tirages=2000;
    for n=1:Nb_Tirages
        g= G(fix(1 + NbG* rand(1)),1);
        m1=M(fix(1 + NbM* rand(1)),1);
        m2=M(fix(1 + NbM* rand(1)),1);
        a1=A(fix(1 + NbA* rand(1)),1);
        a2=A(fix(1 + NbA* rand(1)),1);
        PE=[G(g,2) M(m1,2) M(m2,2) A(a1,2) A(a2,2)];
        NE=[G(g,3) M(m1,3) M(m2,3) A(a1,3) A(a1,3)];
        SE=sum(PE);% Prix de l'équipe
        SN=sum(NE);% Note de l'équipe
            if SN > SNR & SE <= Prix_max % Critère de choix
                 SNR=SN;% Note retenue
                    SER=SE;% Prix retenu
                    SERP=SER;
                Equipe=[G(g,1) M(m1,1) M(m2,1) A(a1,1) A(a2,1)];
        end
    end
    if SER==0
        disp('Pas de solution')
    else
    disp(['Equipe : ' num2str(Equipe)])
    disp(['Total Notes : ' num2str(SNR)])
    disp(['Total Points : ' num2str(SER)])
    disp(' ')
    end

    Résultat :

    Equipe : 8 2 2 7 10
    Total Notes : 95
    Total Points : 770

  5. #5
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 215
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 215
    Par défaut
    Anapurna a clairement dit que son ode était archi-basique. Bien entendu qu'il y a matière à amélioration.

    Amélioration évidente :
    En permutant juste quelques lignes de son code, en remplaçant un test 'différent' par supérieur strict', on arrive à ça ... et à la louche, on divise le temps de traitement par 4 ou 5 :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     
     Pour chaque occurrence Igardien de la table Gardien Faire 
         Pour chaque occurrence Imil1 de la table Milieux Faire 
            Pour chaque occurrence Imil2 de la table Milieux Faire 
               si Milieux[Imil1] > Milieux[Imil2] alors
     
                  Pour chaque occurrence IAtaq1 de la table Attaquants Faire 
                     Pour chaque occurrence IAtaq2 de la table Attaquants Faire 
                         si Attaquants[IAtaq1] >  Attaquants[IAtaq2] alors
                           PrixTot := Gardien[Igardien].prix+Milieux[Imil1].Prix+Milieux[Imil2].prix + Attaquants[IAtaq1].prix+Attaquants[IAtaq2].prix;
                           si PrixTot <= PrixMax alors
                              Ok  =  TestMaxNbSameEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])
                              si  Ok alors 
                                 AddEquipe(Gardien[Igardien],Milieux[Imil1],Milieux[Imil2].prix,Attaquants[IAtaq1],Attaquants[IAtaq2])     
                           FinSi                             
                        Fin Pour
                      Fin Pour
                 Fin Si
               Fin Pour
            Fin Pour
         Fin Pour
    Après, on peut avoir quelques traitements préliminaires qui peuvent encore accélérer le traitement.
    Si par exemple on a 2 gardiens A et B, A vaut plus cher que B, mais il a une performance moindre que B... alors on élimine purement et simplement A de la liste des gardiens. Inutile d'analyser toutes les combinaisons qui contiennent A.

    Si le cas se produit ne serait-ce qu'une fois, on économise 10% du temps de traitement.

    Idem, si avec les 3 ou 4 premiers joueurs, on a déjà dépassé le budget, inutile d'explorer les 25 choix possibles pour le 5ème joueur...

  6. #6
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    3 489
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : Mai 2002
    Messages : 3 489
    Par défaut
    salut

    parmi les amélioration notable tu as effectivement la deuxième boucle de la table attaquant et milieux pour laquelle tu peut commencer a l'indice supérieur de la premier boucle

    exemple
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
        Pour chaque occurrence Imil1 -1 de la table Milieux Faire 
            Pour  Imil2 = Imil1+1 jusqu’à max(table Milieux)  Faire
    de cette manière tu compare
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
       1 et 2
       1 et 3
       1 et 4 ...
      ensuite 
       2 et 3 
       2 et 4 .. 
      et pour finir 
       Max-1 et Max

Discussions similaires

  1. Fenêtre JavaScript avec plusieurs choix
    Par absot dans le forum Général JavaScript
    Réponses: 2
    Dernier message: 08/09/2010, 00h00
  2. Trouver toutes les combinaisons possibles de plusieurs tableaux
    Par divayht dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 23/08/2010, 20h56
  3. case avec plusieurs choix ?
    Par ggwtf dans le forum Qt
    Réponses: 6
    Dernier message: 11/05/2010, 00h37
  4. Recherchev avec plusieurs choix possibles
    Par solorac dans le forum Excel
    Réponses: 1
    Dernier message: 30/09/2008, 15h00
  5. like avec plusieurs choix
    Par mon_pseudo dans le forum Langage SQL
    Réponses: 12
    Dernier message: 20/06/2008, 10h42

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