Aller au contenu

Le sac à dos 🚚☘

Téléchargez le fichier à compléter TPG05.30.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans le dossier [G05_Algo_Glouton].

Consignes communes à chaque partie

Le programme principal contient un appel au module doctest : 

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()
Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.

Exposé du problème☘

Un voleur veut charger un camion avec un certain nombre d'objets. Son objectif est que le chargement ait une valeur maximale.

Pourquoi sac à dos ?

Le problème est en général présenté avec un sac à dos à la place du camion. Entrez « problème du sac à dos » dans un moteur de recherche, vous obtiendrez d'innombrables références. Par exemple celle-ci, qui vous expliquera que, sous ses airs anodins, ce problème fait partie du lot des problèmes importants en informatique.

Contraintes☘

  • Chaque objet a une valeur.
  • Chaque objet a une masse.
  • On ne peut pas charger une masse totale supérieure à M dans le camion.

Exemple☘

On considère que le camion peut transporter au maximum M = 12 tonnes de marchandises. Les objets dans l'entrepôt sont :

nom de l'objet valeur masse (en tonnes)
A 5600 8
B 4000 5
C 3500 4
D 500 1

Structure de données☘

Les données seront représentées sous forme de tables (tableau de dictionnaires).

En d'autres termes, l'entrepôt est constitué d'une liste d'objets, chaque objet est représenté sous la forme d'un dictionnaire avec trois clefs (nom, valeur et masse). Par exemple :

1
2
3
4
objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15},
          {'nom' : 'B', 'valeur' : 400, 'masse' : 24},
          {'nom' : 'C', 'valeur' : 350, 'masse' : 9},
          {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
Rappel

On peut accéder facilement à la valeur d'un attribut d'un objet à l'aide de la clé correspondante :

>>> objets[1]['valeur']
400
>>> objets[3]['nom']
D
>>> objets[0]['masse']
15

Partie A - Stratégie n°1☘

Le voleur trie les objets par ordre décroissant de leur valeur puis les charge dans cet ordre : d'abord l'objet de plus forte valeur, puis l'objet de plus forte valeur parmi ceux qui restent, ..., et ainsi de suite.

  1. Utilisez cette stratégie sur l'exemple proposé. Conduit-elle au chargement de plus forte valeur avec ces objets ?

    Rappel de l'exemple

    Le camion peut transporter au maximum 12 tonnes de marchandises et les objets dans l'entrepôt sont :

    nom de l'objet valeur masse (en tonnes)
    A 5600 8
    B 4000 5
    C 3500 4
    D 500 1

  2. Donnez un exemple montrant que cette stratégie ne conduit pas nécessairement à un chargement de plus forte valeur.

  3. Le voleur souhaite trier les objets par ordre décroissant de leur valeur.

    1. Définir la fonction de critère de tri correspondante.
      Vous pouvez nommer cette fonction critere_valeur().

      Rappel

      Pour celles et ceux qui ne se rappellent plus comment trier une table de données, vous pouvez :

    2. Complétez la définition de la fonction tri_valeur() en respectant ses spécifications.

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
      def tri_valeur(table_objets):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                   représente un objet de clefs 'nom', 'valeur' et 'masse'
    Sortie: None - Modifie en place la table en triant les dictionnaires par
            ordre décroissant de valeur (fonction à effet de bord)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> tri_valeur(objets)
    >>> objets
    [{'nom': 'D', 'valeur': 750, 'masse': 25}, {'nom': 'A', 'valeur': 500, 'masse': 15}, {'nom': 'B', 'valeur': 400, 'masse': 24}, {'nom': 'C', 'valeur': 350, 'masse': 9}]
    """

  4. La fonction camion_glouton1() doit renvoyer le chargement effectué par le voleur selon la stratégie n°1. Complétez la définition de la fonction camion_glouton1(). 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def camion_glouton1(table_objets, charge_utile):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                   représente un objet de clefs 'nom', 'valeur' et 'masse'
    charge_utile - int, masse maximale supportée par le camion

    Sortie: list - renvoie le chargement du camion obtenu par la stratégie n°1
            sous la forme d'une table de dictionnaires (liste d'objets)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> camion_glouton1(objets, 40)
    [{'nom': 'D', 'valeur': 750, 'masse': 25}, {'nom': 'A', 'valeur': 500, 'masse': 15}]
    """

  5. Un entrepôt contient les 26 objets ci-dessous. Le voleur est venu avec un bateau permettant de transporter 500 tonnes. Déterminez le chargement qu'il effectuera en utilisant la stratégie n°1.

    Contenu de l'entrepôt
     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
    entrepot = [{'nom': 'A', 'valeur': 186, 'masse': 78},
           {'nom': 'B', 'valeur': 71, 'masse': 35},
           {'nom': 'C', 'valeur': 90, 'masse': 31},
           {'nom': 'D', 'valeur': 182, 'masse': 53},
           {'nom': 'E', 'valeur': 173, 'masse': 78},
           {'nom': 'F', 'valeur': 94, 'masse': 69},
           {'nom': 'G', 'valeur': 97, 'masse': 33},
           {'nom': 'H', 'valeur': 179, 'masse': 95},
           {'nom': 'I', 'valeur': 56, 'masse': 53},
           {'nom': 'J', 'valeur': 162, 'masse': 93},
           {'nom': 'K', 'valeur': 67, 'masse': 63},
           {'nom': 'L', 'valeur': 131, 'masse': 71},
           {'nom': 'M', 'valeur': 179, 'masse': 44},
           {'nom': 'N', 'valeur': 131, 'masse': 30},
           {'nom': 'O', 'valeur': 51, 'masse': 66},
           {'nom': 'P', 'valeur': 45, 'masse': 32},
           {'nom': 'Q', 'valeur': 47, 'masse': 58},
           {'nom': 'R', 'valeur': 103, 'masse': 46},
           {'nom': 'S', 'valeur': 68, 'masse': 30},
           {'nom': 'T', 'valeur': 51, 'masse': 75},
           {'nom': 'U', 'valeur': 128, 'masse': 75},
           {'nom': 'V', 'valeur': 143, 'masse': 97},
           {'nom': 'W', 'valeur': 90, 'masse': 42},
           {'nom': 'X', 'valeur': 50, 'masse': 78},
           {'nom': 'Y', 'valeur': 176, 'masse': 36},
           {'nom': 'Z', 'valeur': 100, 'masse': 92}]
    Réponse
    >>> camion_glouton1(entrepot, 500)
[{'nom': 'A', 'valeur': 186, 'masse': 78},
 {'nom': 'D', 'valeur': 182, 'masse': 53},
 {'nom': 'H', 'valeur': 179, 'masse': 95},
 {'nom': 'M', 'valeur': 179, 'masse': 44},
 {'nom': 'Y', 'valeur': 176, 'masse': 36},
 {'nom': 'E', 'valeur': 173, 'masse': 78},
 {'nom': 'J', 'valeur': 162, 'masse': 93}]

Partie B - Stratégie n°2☘

Ayant constaté dans l'exemple précédent qu'un objet de masse excessive bloquait le chargement, le voleur décide à présent de choisir de charger les objets dans l'ordre croissant de leur masse.
L'idée est de charger un maximum d'objets, en espèrant ainsi maximiser la valeur.

  1. Justifiez que ce n'est pas nécessairement un bon choix.
    Appelez l'enseignant une fois votre justification écrite sur le cahier.

  2. Malgré tout, le voleur souhaite trier les objets par ordre croissant de leur masse.
    Complétez la définition de la fonction tri_masse() en respectant ses spécifications.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def tri_masse(table_objets):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                    représente un objet de clefs 'nom', 'valeur' et 'masse'
    Sortie: None - Modifie en place la table en triant les dictionnaires par
            ordre croissant de masse (fonction à effet de bord)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> tri_masse(objets)
    >>> objets
    [{'nom': 'C', 'valeur': 350, 'masse': 9}, {'nom': 'A', 'valeur': 500, 'masse': 15}, {'nom': 'B', 'valeur': 400, 'masse': 24}, {'nom': 'D', 'valeur': 750, 'masse': 25}]
    """
    Une piste

    Rappelez-vous que vous pouvez définir une fonction supplémentaire qui servira de critère de tri.

  3. La fonction camion_glouton2() doit renvoyer le chargement effectué par le voleur selon la stratégie n°2. Complétez la définition de la fonction camion_glouton2(). 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def camion_glouton2(table_objets, charge_utile):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                    représente un objet de clefs 'nom', 'valeur' et 'masse'
    charge_utile - int, masse maximale supportée par le camion

    Sortie: list - renvoie le chargement du camion obtenu par la stratégie n°2
            sous la forme d'une table de dictionnaires (liste d'objets)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> camion_glouton2(objets, 40)
    [{'nom': 'C', 'valeur': 350, 'masse': 9}, {'nom': 'A', 'valeur': 500, 'masse': 15}]
    """

  4. Un entrepôt contient les 26 objets ci-dessous. Le voleur est venu avec un bateau permettant de transporter 500 tonnes. Déterminez le chargement qu'il effectuera en utilisant la stratégie n°2.

    Contenu de l'entrepôt
     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
    entrepot = [{'nom': 'A', 'valeur': 186, 'masse': 78},
           {'nom': 'B', 'valeur': 71, 'masse': 35},
           {'nom': 'C', 'valeur': 90, 'masse': 31},
           {'nom': 'D', 'valeur': 182, 'masse': 53},
           {'nom': 'E', 'valeur': 173, 'masse': 78},
           {'nom': 'F', 'valeur': 94, 'masse': 69},
           {'nom': 'G', 'valeur': 97, 'masse': 33},
           {'nom': 'H', 'valeur': 179, 'masse': 95},
           {'nom': 'I', 'valeur': 56, 'masse': 53},
           {'nom': 'J', 'valeur': 162, 'masse': 93},
           {'nom': 'K', 'valeur': 67, 'masse': 63},
           {'nom': 'L', 'valeur': 131, 'masse': 71},
           {'nom': 'M', 'valeur': 179, 'masse': 44},
           {'nom': 'N', 'valeur': 131, 'masse': 30},
           {'nom': 'O', 'valeur': 51, 'masse': 66},
           {'nom': 'P', 'valeur': 45, 'masse': 32},
           {'nom': 'Q', 'valeur': 47, 'masse': 58},
           {'nom': 'R', 'valeur': 103, 'masse': 46},
           {'nom': 'S', 'valeur': 68, 'masse': 30},
           {'nom': 'T', 'valeur': 51, 'masse': 75},
           {'nom': 'U', 'valeur': 128, 'masse': 75},
           {'nom': 'V', 'valeur': 143, 'masse': 97},
           {'nom': 'W', 'valeur': 90, 'masse': 42},
           {'nom': 'X', 'valeur': 50, 'masse': 78},
           {'nom': 'Y', 'valeur': 176, 'masse': 36},
           {'nom': 'Z', 'valeur': 100, 'masse': 92}]
    Réponse
    >>> camion_glouton2(entrepot, 500)
[{'nom': 'N', 'valeur': 131, 'masse': 30},
 {'nom': 'S', 'valeur': 68, 'masse': 30},
 {'nom': 'C', 'valeur': 90, 'masse': 31},
 {'nom': 'P', 'valeur': 45, 'masse': 32},
 {'nom': 'G', 'valeur': 97, 'masse': 33},
 {'nom': 'B', 'valeur': 71, 'masse': 35},
 {'nom': 'Y', 'valeur': 176, 'masse': 36},
 {'nom': 'W', 'valeur': 90, 'masse': 42},
 {'nom': 'M', 'valeur': 179, 'masse': 44},
 {'nom': 'R', 'valeur': 103, 'masse': 46},
 {'nom': 'D', 'valeur': 182, 'masse': 53},
 {'nom': 'I', 'valeur': 56, 'masse': 53}]

Partie C - Stratégie n°3☘

La clef, sans doute, serait de ne pas dissocier les deux contraintes et de sélectionner en priorité les objets ayant la plus grande valeur par unité de masse.

Le voleur décide donc de charger les objets par ordre décroissant des rapports valeur/masse.

  1. A partir de l'exemple donné avant la stratégie n°1, établissez une quatrième colonne donnant le rapport valeur/masse pour chacun des ojets présents dans l'entrepôt.

    Rappel de l'exemple

    Le camion peut transporter au maximum 12 tonnes de marchandises et les objets dans l'entrepôt sont :

    nom de l'objet valeur masse (en tonnes)
    A 5600 8
    B 4000 5
    C 3500 4
    D 500 1

    Une réponse

    nom de l'objet valeur masse (en tonnes) valeur/masse
    A 5600 8 700
    B 4000 5 800
    C 3500 4 875
    D 500 1 500

  2. Utilisez la stratégie n°3 sur cet exemple.
    Conduit-elle au chargement de plus forte valeur ?

    Une réponse

    Le principe glouton mène à d'abord charger l'objet de plus grand rapport valeur/masse, soit l'objet C.
    Il reste 8 tonnes de « disponible » dans le camion : tous les objets restent en course.

    Parmi les objets restant, l'objet B est celui de plus grand rapport valeur/masse.
    Il reste alors 3 tonnes de « disponible » dans le camion.

    Seul l'objet D peut encore être chargé.

    La valeur du chargement avec les objets C, B et D est 3500 + 4000 + 500 = 8000, ce qui est inférieur à la valeur obtenue avec la stratégie n°1 pour cet exemple.

    Ce choix glouton n'est donc pas non plus optimal.

  3. Le voleur décide de charger les objets par ordre décroissant des rapports valeur/masse.
    Complétez la définition de la fonction tri_valeur_masse() en respectant ses spécifications.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def tri_valeur_masse(table_objets):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                   représente un objet de clefs 'nom', 'valeur' et 'masse'
    Sortie: None - Modifie en place la table en triant les dictionnaires par
            ordre décroissant de rapport valeur/masse (fonction à effet de bord)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> tri_valeur_masse(objets)
    >>> objets
    [{'nom': 'C', 'valeur': 350, 'masse': 9}, {'nom': 'A', 'valeur': 500, 'masse': 15}, {'nom': 'D', 'valeur': 750, 'masse': 25}, {'nom': 'B', 'valeur': 400, 'masse': 24}]
    """
    Une piste

    Rappelez-vous que vous pouvez définir une fonction supplémentaire qui servira de critère de tri.

  4. La fonction camion_glouton3() doit renvoyer le chargement effectué par le voleur selon la stratégie n°3. Complétez la définition de la fonction camion_glouton3(). 

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def camion_glouton3(table_objets, charge_utile):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                    représente un objet de clefs 'nom', 'valeur' et 'masse'
    charge_utile - int, masse maximale supportée par le camion

    Sortie: list - renvoie le chargement du camion obtenu par la stratégie n°3
            sous la forme d'une table de dictionnaires (liste d'objets)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> camion_glouton3(objets, 40)
    [{'nom': 'C', 'valeur': 350, 'masse': 9}, {'nom': 'A', 'valeur': 500, 'masse': 15}]
    """

  5. Un entrepôt contient les 26 objets ci-dessous. Le voleur est venu avec un bateau permettant de transporter 500 tonnes. Déterminez le chargement qu'il effectuera en utilisant la stratégie n°3.

    Contenu de l'entrepôt
     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
    entrepot = [{'nom': 'A', 'valeur': 186, 'masse': 78},
           {'nom': 'B', 'valeur': 71, 'masse': 35},
           {'nom': 'C', 'valeur': 90, 'masse': 31},
           {'nom': 'D', 'valeur': 182, 'masse': 53},
           {'nom': 'E', 'valeur': 173, 'masse': 78},
           {'nom': 'F', 'valeur': 94, 'masse': 69},
           {'nom': 'G', 'valeur': 97, 'masse': 33},
           {'nom': 'H', 'valeur': 179, 'masse': 95},
           {'nom': 'I', 'valeur': 56, 'masse': 53},
           {'nom': 'J', 'valeur': 162, 'masse': 93},
           {'nom': 'K', 'valeur': 67, 'masse': 63},
           {'nom': 'L', 'valeur': 131, 'masse': 71},
           {'nom': 'M', 'valeur': 179, 'masse': 44},
           {'nom': 'N', 'valeur': 131, 'masse': 30},
           {'nom': 'O', 'valeur': 51, 'masse': 66},
           {'nom': 'P', 'valeur': 45, 'masse': 32},
           {'nom': 'Q', 'valeur': 47, 'masse': 58},
           {'nom': 'R', 'valeur': 103, 'masse': 46},
           {'nom': 'S', 'valeur': 68, 'masse': 30},
           {'nom': 'T', 'valeur': 51, 'masse': 75},
           {'nom': 'U', 'valeur': 128, 'masse': 75},
           {'nom': 'V', 'valeur': 143, 'masse': 97},
           {'nom': 'W', 'valeur': 90, 'masse': 42},
           {'nom': 'X', 'valeur': 50, 'masse': 78},
           {'nom': 'Y', 'valeur': 176, 'masse': 36},
           {'nom': 'Z', 'valeur': 100, 'masse': 92}]
    Réponse
    >>> camion_glouton3(entrepot, 500)
[{'nom': 'Y', 'valeur': 176, 'masse': 36},
 {'nom': 'N', 'valeur': 131, 'masse': 30},
 {'nom': 'M', 'valeur': 179, 'masse': 44},
 {'nom': 'D', 'valeur': 182, 'masse': 53},
 {'nom': 'G', 'valeur': 97, 'masse': 33},
 {'nom': 'C', 'valeur': 90, 'masse': 31},
 {'nom': 'A', 'valeur': 186, 'masse': 78},
 {'nom': 'S', 'valeur': 68, 'masse': 30},
 {'nom': 'R', 'valeur': 103, 'masse': 46},
 {'nom': 'E', 'valeur': 173, 'masse': 78},
 {'nom': 'B', 'valeur': 71, 'masse': 35}]

Partie D - Comparaisons☘

À la fonction de tri près, les fonctions camion_glouton1(), camion_glouton2() et camion_glouton3() sont identiques. L'idée est donc d'unifier ces fonctions en une seule.

Pour cela, vous allez définir la fonction camion_glouton() qui renvoie le chargement effectué par le voleur selon la stratégie choisie. Un des paramètres de camion_glouton() est le nom de la fonction (sans parenthèses) qui correspond au tri choisi et programmée dans les parties précédentes (tri_valeur, tri_masse ou tri_valeur_masse).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def camion_glouton(table_objets, charge_utile, tri):
    """
    table_objets - list, Tableau de dictionnaires, chaque dictionnaire
                    représente un objet de clefs 'nom', 'valeur' et 'masse'
    charge_utile - int, masse maximale supportée par le camion
    tri - Fonction de tri à choisir, correspondant aux stratégies 1, 2 ou 3

    Sortie: list - renvoie le chargement du camion obtenu par la stratégie choisie
            sous la forme d'une table de dictionnaires (liste d'objets)

    >>> objets = [{'nom' : 'A', 'valeur' : 500, 'masse' : 15}, {'nom' : 'B', 'valeur' : 400, 'masse' : 24}, {'nom' : 'C', 'valeur' : 350, 'masse' : 9}, {'nom' : 'D', 'valeur' : 750, 'masse' : 25}]
    >>> camion_glouton(objets, 40, tri_valeur)
    [{'nom': 'D', 'valeur': 750, 'masse': 25}, {'nom': 'A', 'valeur': 500, 'masse': 15}]
    >>> camion_glouton(objets, 40, tri_masse)
    [{'nom': 'C', 'valeur': 350, 'masse': 9}, {'nom': 'A', 'valeur': 500, 'masse': 15}]
    >>> camion_glouton(objets, 40, tri_valeur_masse)
    [{'nom': 'C', 'valeur': 350, 'masse': 9}, {'nom': 'A', 'valeur': 500, 'masse': 15}]
    """

Application de cet algorithme glouton☘

J. de Villèle, enseignant dans l'académie d'Orléans-Tour, est l'auteur original de cette application. Qu'il en soit ici remercié.

La table de données ci-dessous représente des joueurs d'e-sport. Leur « valeur » correspond à leur score moyen en tournoi depuis le début de leur carrière et leur « masse « correspond au salaire qu'ils demandent pour pouvoir intégrer une nouvelle équipe.

La table
joueurs = [{'nom': 'atuffell0', 'valeur': 186, 'masse': 78},
          {'nom': 'alacroux1', 'valeur': 71, 'masse': 35},
          {'nom': 'lesposita2', 'valeur': 90, 'masse': 31},
          {'nom': 'ascandred3', 'valeur': 182, 'masse': 53},
          {'nom': 'cheathcoat4', 'valeur': 173, 'masse': 78},
          {'nom': 'mpechan5', 'valeur': 94, 'masse': 69},
          {'nom': 'kmurison6', 'valeur': 97, 'masse': 33},
          {'nom': 'cschwandermann7', 'valeur': 179, 'masse': 95},
          {'nom': 'khanrott8', 'valeur': 56, 'masse': 53},
          {'nom': 'wkiln9', 'valeur': 162, 'masse': 93},
          {'nom': 'tpaolilloa', 'valeur': 67, 'masse': 63},
          {'nom': 'aboudab', 'valeur': 131, 'masse': 71},
          {'nom': 'dgribbinsc', 'valeur': 179, 'masse': 44},
          {'nom': 'vdavittd', 'valeur': 131, 'masse': 30},
          {'nom': 'ssalmonde', 'valeur': 51, 'masse': 66},
          {'nom': 'svawtonf', 'valeur': 45, 'masse': 32},
          {'nom': 'coculleng', 'valeur': 47, 'masse': 58},
          {'nom': 'lstandenh', 'valeur': 103, 'masse': 46},
          {'nom': 'cshoardi', 'valeur': 68, 'masse': 30},
          {'nom': 'mowlnerj', 'valeur': 51, 'masse': 75},
          {'nom': 'mondrichk', 'valeur': 128, 'masse': 75},
          {'nom': 'mpatterfieldl', 'valeur': 143, 'masse': 97},
          {'nom': 'sduttm', 'valeur': 90, 'masse': 42},
          {'nom': 'ryuryshevn', 'valeur': 50, 'masse': 78},
          {'nom': 'cwillettso', 'valeur': 176, 'masse': 36},
          {'nom': 'cmuldowniep', 'valeur': 100, 'masse': 92},
          {'nom': 'hgabbitasq', 'valeur': 188, 'masse': 82},
          {'nom': 'vclaughtonr', 'valeur': 60, 'masse': 72},
          {'nom': 'bnoldas', 'valeur': 173, 'masse': 36},
          {'nom': 'hurquhartt', 'valeur': 160, 'masse': 61},
          {'nom': 'ghalkyardu', 'valeur': 199, 'masse': 55},
          {'nom': 'gallredv', 'valeur': 91, 'masse': 56},
          {'nom': 'bfritschelw', 'valeur': 178, 'masse': 93},
          {'nom': 'nrobothamx', 'valeur': 112, 'masse': 44},
          {'nom': 'tmcginny', 'valeur': 152, 'masse': 52},
          {'nom': 'avallintinez', 'valeur': 175, 'masse': 62},
          {'nom': 'santcliffe10', 'valeur': 174, 'masse': 42},
          {'nom': 'radrien11', 'valeur': 119, 'masse': 67},
          {'nom': 'lmordie12', 'valeur': 194, 'masse': 46},
          {'nom': 'cprosch13', 'valeur': 74, 'masse': 73},
          {'nom': 'wscain14', 'valeur': 94, 'masse': 94},
          {'nom': 'gripping15', 'valeur': 103, 'masse': 91},
          {'nom': 'ybatterton16', 'valeur': 161, 'masse': 93},
          {'nom': 'ckernan17', 'valeur': 106, 'masse': 75},
          {'nom': 'mhousecroft18', 'valeur': 84, 'masse': 67},
          {'nom': 'gprudence19', 'valeur': 89, 'masse': 68},
          {'nom': 'flamberto1a', 'valeur': 65, 'masse': 100},
          {'nom': 'dgammon1b', 'valeur': 166, 'masse': 40},
          {'nom': 'jkidde1c', 'valeur': 200, 'masse': 69},
          {'nom': 'amewrcik1d', 'valeur': 54, 'masse': 90},
          {'nom': 'fpyke1e', 'valeur': 114, 'masse': 97},
          {'nom': 'mfellows1f', 'valeur': 188, 'masse': 80},
          {'nom': 'cknoton1g', 'valeur': 113, 'masse': 36},
          {'nom': 'nharrema1h', 'valeur': 192, 'masse': 42},
          {'nom': 'vtomasik1i', 'valeur': 64, 'masse': 40},
          {'nom': 'scoping1j', 'valeur': 185, 'masse': 46},
          {'nom': 'mdyball1k', 'valeur': 50, 'masse': 34},
          {'nom': 'dvelde1l', 'valeur': 112, 'masse': 80},
          {'nom': 'kconkay1m', 'valeur': 193, 'masse': 45},
          {'nom': 'dglanister1n', 'valeur': 195, 'masse': 86},
          {'nom': 'rhobell1o', 'valeur': 167, 'masse': 88},
          {'nom': 'lseakes1p', 'valeur': 130, 'masse': 93},
          {'nom': 'twootton1q', 'valeur': 132, 'masse': 62},
          {'nom': 'agooderridge1r', 'valeur': 121, 'masse': 49},
          {'nom': 'tkilcullen1s', 'valeur': 180, 'masse': 80},
          {'nom': 'ssteinor1t', 'valeur': 81, 'masse': 38},
          {'nom': 'theller1u', 'valeur': 102, 'masse': 47},
          {'nom': 'jpetrozzi1v', 'valeur': 141, 'masse': 87},
          {'nom': 'iivanitsa1w', 'valeur': 78, 'masse': 41},
          {'nom': 'lkohn1x', 'valeur': 114, 'masse': 43},
          {'nom': 'afinlater1y', 'valeur': 159, 'masse': 81},
          {'nom': 'mbrogioni1z', 'valeur': 52, 'masse': 81},
          {'nom': 'fcrinson20', 'valeur': 73, 'masse': 45},
          {'nom': 'mgreedyer21', 'valeur': 74, 'masse': 49},
          {'nom': 'ccheyenne22', 'valeur': 200, 'masse': 33},
          {'nom': 'hwinterbourne23', 'valeur': 90, 'masse': 56},
          {'nom': 'oblampied24', 'valeur': 90, 'masse': 34},
          {'nom': 'cbydaway25', 'valeur': 158, 'masse': 34},
          {'nom': 'kslocumb26', 'valeur': 107, 'masse': 69},
          {'nom': 'jherion27', 'valeur': 49, 'masse': 98},
          {'nom': 'vhallagan28', 'valeur': 198, 'masse': 36},
          {'nom': 'jcanada29', 'valeur': 187, 'masse': 31},
          {'nom': 'zleavey2a', 'valeur': 146, 'masse': 94},
          {'nom': 'klownes2b', 'valeur': 144, 'masse': 36},
          {'nom': 'lmuzzillo2c', 'valeur': 140, 'masse': 46},
          {'nom': 'uarnal2d', 'valeur': 190, 'masse': 60},
          {'nom': 'rclem2e', 'valeur': 126, 'masse': 93},
          {'nom': 'fstuehmeyer2f', 'valeur': 63, 'masse': 30},
          {'nom': 'dchinery2g', 'valeur': 164, 'masse': 78},
          {'nom': 'zeilers2h', 'valeur': 51, 'masse': 46},
          {'nom': 'jcordingly2i', 'valeur': 192, 'masse': 38},
          {'nom': 'fstollard2j', 'valeur': 134, 'masse': 93},
          {'nom': 'adannell2k', 'valeur': 47, 'masse': 62},
          {'nom': 'cbryenton2l', 'valeur': 81, 'masse': 38},
          {'nom': 'mcardinal2m', 'valeur': 79, 'masse': 72},
          {'nom': 'escattergood2n', 'valeur': 67, 'masse': 38},
          {'nom': 'arecord2o', 'valeur': 170, 'masse': 57},
          {'nom': 'cbertl2p', 'valeur': 183, 'masse': 47},
          {'nom': 'ssprott2q', 'valeur': 67, 'masse': 40},
          {'nom': 'fegell2r', 'valeur': 126, 'masse': 57},
          {'nom': 'eferrie2s', 'valeur': 153, 'masse': 33},
          {'nom': 'mjizhaki2t', 'valeur': 149, 'masse': 31},
          {'nom': 'lolsson2u', 'valeur': 76, 'masse': 64},
          {'nom': 'alorentzen2v', 'valeur': 157, 'masse': 33},
          {'nom': 'mdominik2w', 'valeur': 110, 'masse': 44},
          {'nom': 'rmckenny2x', 'valeur': 132, 'masse': 74},
          {'nom': 'bdavydenko2y', 'valeur': 115, 'masse': 92},
          {'nom': 'mkienl2z', 'valeur': 102, 'masse': 38},
          {'nom': 'mgroger30', 'valeur': 186, 'masse': 68},
          {'nom': 'haggett31', 'valeur': 186, 'masse': 40},
          {'nom': 'phaggata32', 'valeur': 180, 'masse': 44},
          {'nom': 'ptrobridge33', 'valeur': 194, 'masse': 77},
          {'nom': 'dbold34', 'valeur': 144, 'masse': 30},
          {'nom': 'mgagg35', 'valeur': 131, 'masse': 84},
          {'nom': 'hellerbeck36', 'valeur': 54, 'masse': 34},
          {'nom': 'cthredder37', 'valeur': 70, 'masse': 65},
          {'nom': 'kfilisov38', 'valeur': 174, 'masse': 99},
          {'nom': 'ktamburo39', 'valeur': 99, 'masse': 70},
          {'nom': 'ssawer3a', 'valeur': 140, 'masse': 96},
          {'nom': 'dtribell3b', 'valeur': 153, 'masse': 71},
          {'nom': 'ahartill3c', 'valeur': 169, 'masse': 95},
          {'nom': 'aboanas3d', 'valeur': 148, 'masse': 30},
          {'nom': 'ttreagust3e', 'valeur': 191, 'masse': 86},
          {'nom': 'abasey3f', 'valeur': 96, 'masse': 90},
          {'nom': 'ngerraty3g', 'valeur': 174, 'masse': 42},
          {'nom': 'amunford3h', 'valeur': 93, 'masse': 31},
          {'nom': 'fmacalaster3i', 'valeur': 139, 'masse': 34},
          {'nom': 'ahabbin3j', 'valeur': 64, 'masse': 46},
          {'nom': 'hcurme3k', 'valeur': 154, 'masse': 64},
          {'nom': 'echeshire3l', 'valeur': 79, 'masse': 31},
          {'nom': 'aloxton3m', 'valeur': 69, 'masse': 81},
          {'nom': 'pnewe3n', 'valeur': 143, 'masse': 33},
          {'nom': 'cbonniface3o', 'valeur': 94, 'masse': 68},
          {'nom': 'ebaynard3p', 'valeur': 126, 'masse': 86},
          {'nom': 'jketts3q', 'valeur': 155, 'masse': 59},
          {'nom': 'tpattillo3r', 'valeur': 46, 'masse': 85},
          {'nom': 'llindro3s', 'valeur': 129, 'masse': 56},
          {'nom': 'bholton3t', 'valeur': 158, 'masse': 96},
          {'nom': 'rcahen3u', 'valeur': 88, 'masse': 81},
          {'nom': 'kchave3v', 'valeur': 104, 'masse': 59},
          {'nom': 'cwymer3w', 'valeur': 141, 'masse': 59},
          {'nom': 'jemloch3x', 'valeur': 156, 'masse': 65},
          {'nom': 'mferrero3y', 'valeur': 184, 'masse': 52},
          {'nom': 'tcallan3z', 'valeur': 93, 'masse': 45},
          {'nom': 'ccodlin40', 'valeur': 45, 'masse': 32},
          {'nom': 'gpaxeford41', 'valeur': 182, 'masse': 75},
          {'nom': 'apawlicki42', 'valeur': 96, 'masse': 32},
          {'nom': 'vhardisty43', 'valeur': 96, 'masse': 51},
          {'nom': 'jlobb44', 'valeur': 140, 'masse': 91},
          {'nom': 'spaolacci45', 'valeur': 121, 'masse': 98},
          {'nom': 'obullivent46', 'valeur': 138, 'masse': 100},
          {'nom': 'tpatek47', 'valeur': 162, 'masse': 47},
          {'nom': 'vhully48', 'valeur': 108, 'masse': 56},
          {'nom': 'nweekland49', 'valeur': 191, 'masse': 84},
          {'nom': 'smcclelland4a', 'valeur': 185, 'masse': 66},
          {'nom': 'lheadey4b', 'valeur': 153, 'masse': 38},
          {'nom': 'ebrumby4c', 'valeur': 118, 'masse': 71},
          {'nom': 'ebelmont4d', 'valeur': 117, 'masse': 85},
          {'nom': 'nmcdyer4e', 'valeur': 189, 'masse': 80},
          {'nom': 'tdelcastel4f', 'valeur': 194, 'masse': 46},
          {'nom': 'ganlay4g', 'valeur': 191, 'masse': 90},
          {'nom': 'jspraberry4h', 'valeur': 197, 'masse': 63},
          {'nom': 'cemps4i', 'valeur': 52, 'masse': 100},
          {'nom': 'jsalvin4j', 'valeur': 139, 'masse': 67},
          {'nom': 'mallden4k', 'valeur': 132, 'masse': 100},
          {'nom': 'wwillcocks4l', 'valeur': 159, 'masse': 93},
          {'nom': 'caspey4m', 'valeur': 47, 'masse': 86},
          {'nom': 'sluto4n', 'valeur': 150, 'masse': 42},
          {'nom': 'mwicher4o', 'valeur': 94, 'masse': 67},
          {'nom': 'hbrosenius4p', 'valeur': 82, 'masse': 98},
          {'nom': 'twhoston4q', 'valeur': 150, 'masse': 100},
          {'nom': 'ptaks4r', 'valeur': 192, 'masse': 69},
          {'nom': 'mjanew4s', 'valeur': 67, 'masse': 54},
          {'nom': 'vbeggan4t', 'valeur': 146, 'masse': 94},
          {'nom': 'bnewns4u', 'valeur': 161, 'masse': 72},
          {'nom': 'aandresen4v', 'valeur': 57, 'masse': 79},
          {'nom': 'epearn4w', 'valeur': 121, 'masse': 84},
          {'nom': 'gpointing4x', 'valeur': 118, 'masse': 33},
          {'nom': 'kgradon4y', 'valeur': 65, 'masse': 98},
          {'nom': 'dstrelitz4z', 'valeur': 164, 'masse': 93},
          {'nom': 'vtreacher50', 'valeur': 193, 'masse': 69},
          {'nom': 'vbartkowiak51', 'valeur': 139, 'masse': 92},
          {'nom': 'clagden52', 'valeur': 138, 'masse': 59},
          {'nom': 'htrace53', 'valeur': 53, 'masse': 44},
          {'nom': 'ocopsey54', 'valeur': 57, 'masse': 49},
          {'nom': 'lspary55', 'valeur': 142, 'masse': 61},
          {'nom': 'efantonetti56', 'valeur': 103, 'masse': 82},
          {'nom': 'crouchy57', 'valeur': 121, 'masse': 55},
          {'nom': 'ibentje58', 'valeur': 175, 'masse': 32},
          {'nom': 'ccharity59', 'valeur': 102, 'masse': 86},
          {'nom': 'ckhomich5a', 'valeur': 160, 'masse': 92},
          {'nom': 'lbangs5b', 'valeur': 98, 'masse': 93},
          {'nom': 'tscotsbrook5c', 'valeur': 91, 'masse': 74},
          {'nom': 'mknutton5d', 'valeur': 153, 'masse': 62},
          {'nom': 'etimperley5e', 'valeur': 49, 'masse': 39},
          {'nom': 'cfoord5f', 'valeur': 181, 'masse': 52},
          {'nom': 'hkorda5g', 'valeur': 175, 'masse': 96},
          {'nom': 'jgoor5h', 'valeur': 124, 'masse': 74},
          {'nom': 'cmaffey5i', 'valeur': 157, 'masse': 90},
          {'nom': 'sfuzzard5j', 'valeur': 49, 'masse': 69},
          {'nom': 'mbrickdale5k', 'valeur': 85, 'masse': 72},
          {'nom': 'bphipp5l', 'valeur': 82, 'masse': 44},
          {'nom': 'kblaxeland5m', 'valeur': 50, 'masse': 64},
          {'nom': 'cginnane5n', 'valeur': 136, 'masse': 78},
          {'nom': 'jteesdale5o', 'valeur': 99, 'masse': 96},
          {'nom': 'tdyshart5p', 'valeur': 198, 'masse': 86},
          {'nom': 'wlauritzen5q', 'valeur': 115, 'masse': 66},
          {'nom': 'dnorthall5r', 'valeur': 108, 'masse': 67},
          {'nom': 'kturfes5s', 'valeur': 114, 'masse': 59},
          {'nom': 'kdingate5t', 'valeur': 116, 'masse': 70},
          {'nom': 'coliff5u', 'valeur': 169, 'masse': 48},
          {'nom': 'lgarment5v', 'valeur': 177, 'masse': 75},
          {'nom': 'mshevlin5w', 'valeur': 175, 'masse': 45},
          {'nom': 'pwatkins5x', 'valeur': 113, 'masse': 74},
          {'nom': 'dbraithwait5y', 'valeur': 100, 'masse': 57},
          {'nom': 'gduckit5z', 'valeur': 87, 'masse': 67},
          {'nom': 'hwillcot60', 'valeur': 139, 'masse': 72},
          {'nom': 'aofergus61', 'valeur': 145, 'masse': 76},
          {'nom': 'tkeasey62', 'valeur': 172, 'masse': 61},
          {'nom': 'ebrookesbie63', 'valeur': 191, 'masse': 39},
          {'nom': 'atilby64', 'valeur': 82, 'masse': 36},
          {'nom': 'barne65', 'valeur': 126, 'masse': 84},
          {'nom': 'akenchington66', 'valeur': 148, 'masse': 34},
          {'nom': 'jkilcullen67', 'valeur': 72, 'masse': 84},
          {'nom': 'dgauntlett68', 'valeur': 161, 'masse': 53},
          {'nom': 'tdaubeny69', 'valeur': 69, 'masse': 46},
          {'nom': 'ejaniszewski6a', 'valeur': 171, 'masse': 48},
          {'nom': 'sdunthorn6b', 'valeur': 161, 'masse': 48},
          {'nom': 'czmitrichenko6c', 'valeur': 110, 'masse': 62},
          {'nom': 'anutbrown6d', 'valeur': 82, 'masse': 78},
          {'nom': 'sspinige6e', 'valeur': 157, 'masse': 89},
          {'nom': 'soutibridge6f', 'valeur': 198, 'masse': 69},
          {'nom': 'lswindlehurst6g', 'valeur': 49, 'masse': 90},
          {'nom': 'rblague6h', 'valeur': 71, 'masse': 82},
          {'nom': 'mlefevre6i', 'valeur': 75, 'masse': 32},
          {'nom': 'cbeamand6j', 'valeur': 176, 'masse': 41},
          {'nom': 'vcole6k', 'valeur': 76, 'masse': 38},
          {'nom': 'sduckworth6l', 'valeur': 149, 'masse': 57},
          {'nom': 'wmuehler6m', 'valeur': 91, 'masse': 40},
          {'nom': 'rkeeping6n', 'valeur': 88, 'masse': 74},
          {'nom': 'dtapping6o', 'valeur': 110, 'masse': 44},
          {'nom': 'mtinniswood6p', 'valeur': 64, 'masse': 59},
          {'nom': 'tmacgow6q', 'valeur': 168, 'masse': 91},
          {'nom': 'dbodd6r', 'valeur': 70, 'masse': 81},
          {'nom': 'kloveguard6s', 'valeur': 183, 'masse': 31},
          {'nom': 'rhuffey6t', 'valeur': 103, 'masse': 63},
          {'nom': 'hmacallan6u', 'valeur': 88, 'masse': 95},
          {'nom': 'ktenbroek6v', 'valeur': 130, 'masse': 69},
          {'nom': 'jcharette6w', 'valeur': 171, 'masse': 72},
          {'nom': 'zmcimmie6x', 'valeur': 98, 'masse': 55},
          {'nom': 'wbarents6y', 'valeur': 114, 'masse': 46},
          {'nom': 'mwilder6z', 'valeur': 156, 'masse': 90},
          {'nom': 'afilip70', 'valeur': 172, 'masse': 93},
          {'nom': 'bsouthcott71', 'valeur': 127, 'masse': 55},
          {'nom': 'pstedmond72', 'valeur': 181, 'masse': 88},
          {'nom': 'gleedal73', 'valeur': 162, 'masse': 45},
          {'nom': 'jmuehle74', 'valeur': 57, 'masse': 60},
          {'nom': 'fpenhaligon75', 'valeur': 130, 'masse': 68},
          {'nom': 'kconaghy76', 'valeur': 118, 'masse': 74},
          {'nom': 'bproschke77', 'valeur': 85, 'masse': 83},
          {'nom': 'blope78', 'valeur': 52, 'masse': 97},
          {'nom': 'dbrunstan79', 'valeur': 77, 'masse': 55},
          {'nom': 'htolley7a', 'valeur': 73, 'masse': 45},
          {'nom': 'speto7b', 'valeur': 111, 'masse': 43},
          {'nom': 'oinnocenti7c', 'valeur': 200, 'masse': 37},
          {'nom': 'blaffranconi7d', 'valeur': 127, 'masse': 66},
          {'nom': 'ahaslen7e', 'valeur': 176, 'masse': 58},
          {'nom': 'hmazey7f', 'valeur': 189, 'masse': 50},
          {'nom': 'rbewlie7g', 'valeur': 114, 'masse': 93},
          {'nom': 'bpiccop7h', 'valeur': 146, 'masse': 41},
          {'nom': 'egisborne7i', 'valeur': 76, 'masse': 48},
          {'nom': 'dwye7j', 'valeur': 159, 'masse': 34},
          {'nom': 'kfarnworth7k', 'valeur': 166, 'masse': 31},
          {'nom': 'bbale7l', 'valeur': 146, 'masse': 50},
          {'nom': 'ubecom7m', 'valeur': 53, 'masse': 59},
          {'nom': 'lreedy7n', 'valeur': 137, 'masse': 97},
          {'nom': 'tvalenta7o', 'valeur': 141, 'masse': 79},
          {'nom': 'gfulford7p', 'valeur': 104, 'masse': 48},
          {'nom': 'jcheves7q', 'valeur': 145, 'masse': 37},
          {'nom': 'ajakeman7r', 'valeur': 58, 'masse': 41},
          {'nom': 'olaffling7s', 'valeur': 62, 'masse': 60},
          {'nom': 'sedwicker7t', 'valeur': 155, 'masse': 100},
          {'nom': 'wmccaffrey7u', 'valeur': 98, 'masse': 56},
          {'nom': 'mvogel7v', 'valeur': 90, 'masse': 31},
          {'nom': 'ystolz7w', 'valeur': 85, 'masse': 48},
          {'nom': 'usmallacombe7x', 'valeur': 162, 'masse': 75},
          {'nom': 'gmattiuzzi7y', 'valeur': 95, 'masse': 78},
          {'nom': 'pempleton7z', 'valeur': 51, 'masse': 83},
          {'nom': 'psamter80', 'valeur': 189, 'masse': 89},
          {'nom': 'bcotesford81', 'valeur': 144, 'masse': 78},
          {'nom': 'gjura82', 'valeur': 148, 'masse': 61},
          {'nom': 'aspinks83', 'valeur': 152, 'masse': 53},
          {'nom': 'mofeeny84', 'valeur': 107, 'masse': 98},
          {'nom': 'lfautly85', 'valeur': 170, 'masse': 61},
          {'nom': 'cfrostdick86', 'valeur': 147, 'masse': 34},
          {'nom': 'dmcwaters87', 'valeur': 47, 'masse': 93},
          {'nom': 'kbruton88', 'valeur': 168, 'masse': 96},
          {'nom': 'alimbert89', 'valeur': 105, 'masse': 52},
          {'nom': 'acapelle8a', 'valeur': 165, 'masse': 55},
          {'nom': 'mtrenholm8b', 'valeur': 94, 'masse': 35},
          {'nom': 'wreck8c', 'valeur': 102, 'masse': 88},
          {'nom': 'ldelacour8d', 'valeur': 48, 'masse': 41},
          {'nom': 'kstubs8e', 'valeur': 170, 'masse': 55},
          {'nom': 'bbilby8f', 'valeur': 145, 'masse': 99},
          {'nom': 'lsimmgen8g', 'valeur': 63, 'masse': 59},
          {'nom': 'dsarfatti8h', 'valeur': 81, 'masse': 56},
          {'nom': 'jtees8i', 'valeur': 171, 'masse': 59},
          {'nom': 'pyurasov8j', 'valeur': 152, 'masse': 36},
          {'nom': 'dayce8k', 'valeur': 132, 'masse': 68},
          {'nom': 'bokenden8l', 'valeur': 149, 'masse': 71},
          {'nom': 'clocal8m', 'valeur': 188, 'masse': 39},
          {'nom': 'rdeards8n', 'valeur': 110, 'masse': 42},
          {'nom': 'dsawley8o', 'valeur': 121, 'masse': 63},
          {'nom': 'rscutts8p', 'valeur': 70, 'masse': 34},
          {'nom': 'rdumbell8q', 'valeur': 161, 'masse': 71},
          {'nom': 'hwinterscale8r', 'valeur': 103, 'masse': 91},
          {'nom': 'gduggan8s', 'valeur': 151, 'masse': 97},
          {'nom': 'kshooter8t', 'valeur': 191, 'masse': 65},
          {'nom': 'agilardone8u', 'valeur': 70, 'masse': 70},
          {'nom': 'fhedlestone8v', 'valeur': 168, 'masse': 85},
          {'nom': 'wrunnalls8w', 'valeur': 149, 'masse': 53},
          {'nom': 'esommerton8x', 'valeur': 122, 'masse': 92},
          {'nom': 'mkarpman8y', 'valeur': 84, 'masse': 46},
          {'nom': 'sslafford8z', 'valeur': 158, 'masse': 51},
          {'nom': 'aghio90', 'valeur': 171, 'masse': 75},
          {'nom': 'bgerriessen91', 'valeur': 163, 'masse': 74},
          {'nom': 'gswarbrigg92', 'valeur': 197, 'masse': 94},
          {'nom': 'lskentelbury93', 'valeur': 84, 'masse': 51},
          {'nom': 'akarlolak94', 'valeur': 99, 'masse': 53},
          {'nom': 'bcastells95', 'valeur': 156, 'masse': 85},
          {'nom': 'beasbie96', 'valeur': 123, 'masse': 66},
          {'nom': 'kvalentinetti97', 'valeur': 142, 'masse': 41},
          {'nom': 'rwickrath98', 'valeur': 81, 'masse': 81},
          {'nom': 'stoyne99', 'valeur': 153, 'masse': 100},
          {'nom': 'bbodega9a', 'valeur': 136, 'masse': 67},
          {'nom': 'dlarmuth9b', 'valeur': 75, 'masse': 72},
          {'nom': 'mfyers9c', 'valeur': 93, 'masse': 77},
          {'nom': 'mbellhouse9d', 'valeur': 115, 'masse': 83},
          {'nom': 'cmaclardie9e', 'valeur': 65, 'masse': 40},
          {'nom': 'tmorales9f', 'valeur': 198, 'masse': 92},
          {'nom': 'ihucquart9g', 'valeur': 137, 'masse': 49},
          {'nom': 'lsearchfield9h', 'valeur': 122, 'masse': 93},
          {'nom': 'rduetsche9i', 'valeur': 117, 'masse': 68},
          {'nom': 'wforrester9j', 'valeur': 140, 'masse': 38},
          {'nom': 'emartusewicz9k', 'valeur': 64, 'masse': 73},
          {'nom': 'mmacanulty9l', 'valeur': 69, 'masse': 96},
          {'nom': 'lgenese9m', 'valeur': 119, 'masse': 41},
          {'nom': 'pwatt9n', 'valeur': 192, 'masse': 82},
          {'nom': 'kjosum9o', 'valeur': 188, 'masse': 90},
          {'nom': 'bcastagneri9p', 'valeur': 57, 'masse': 92},
          {'nom': 'hrafter9q', 'valeur': 196, 'masse': 70},
          {'nom': 'bfrary9r', 'valeur': 45, 'masse': 57},
          {'nom': 'rbridgstock9s', 'valeur': 100, 'masse': 96},
          {'nom': 'caxon9t', 'valeur': 195, 'masse': 49},
          {'nom': 'dtillett9u', 'valeur': 52, 'masse': 83},
          {'nom': 'rwaghorn9v', 'valeur': 86, 'masse': 63},
          {'nom': 'gpolendine9w', 'valeur': 88, 'masse': 47},
          {'nom': 'jtredwell9x', 'valeur': 82, 'masse': 94},
          {'nom': 'adebellis9y', 'valeur': 98, 'masse': 61},
          {'nom': 'mkaes9z', 'valeur': 56, 'masse': 84},
          {'nom': 'hdeningtona0', 'valeur': 82, 'masse': 80},
          {'nom': 'msturgesa1', 'valeur': 195, 'masse': 82},
          {'nom': 'bsteelea2', 'valeur': 166, 'masse': 36},
          {'nom': 'ctwinbornea3', 'valeur': 180, 'masse': 64},
          {'nom': 'gtissingtona4', 'valeur': 166, 'masse': 53},
          {'nom': 'dlangelaana5', 'valeur': 134, 'masse': 58},
          {'nom': 'selgooda6', 'valeur': 175, 'masse': 32},
          {'nom': 'cgallagera7', 'valeur': 116, 'masse': 41},
          {'nom': 'ssamesa8', 'valeur': 165, 'masse': 84},
          {'nom': 'dedgleya9', 'valeur': 114, 'masse': 44},
          {'nom': 'mlauaa', 'valeur': 91, 'masse': 44},
          {'nom': 'jlarwayab', 'valeur': 131, 'masse': 50},
          {'nom': 'esagarac', 'valeur': 100, 'masse': 53},
          {'nom': 'mpresseyad', 'valeur': 59, 'masse': 52},
          {'nom': 'mdoolanae', 'valeur': 161, 'masse': 35},
          {'nom': 'jkleslaf', 'valeur': 135, 'masse': 88},
          {'nom': 'kkeerag', 'valeur': 184, 'masse': 72},
          {'nom': 'hkoppsah', 'valeur': 132, 'masse': 86},
          {'nom': 'pstuerai', 'valeur': 118, 'masse': 57},
          {'nom': 'wyeomansaj', 'valeur': 69, 'masse': 59},
          {'nom': 'shunnak', 'valeur': 150, 'masse': 39},
          {'nom': 'bwynrahameal', 'valeur': 124, 'masse': 66},
          {'nom': 'mdetoileam', 'valeur': 137, 'masse': 82},
          {'nom': 'cdarlingtonan', 'valeur': 143, 'masse': 91},
          {'nom': 'charcourtao', 'valeur': 110, 'masse': 76},
          {'nom': 'acondyap', 'valeur': 153, 'masse': 47},
          {'nom': 'nblakemoreaq', 'valeur': 124, 'masse': 54},
          {'nom': 'gmcnabar', 'valeur': 123, 'masse': 67},
          {'nom': 'hbatrickas', 'valeur': 193, 'masse': 80},
          {'nom': 'chubatschat', 'valeur': 154, 'masse': 79},
          {'nom': 'ebarkeau', 'valeur': 129, 'masse': 49},
          {'nom': 'elouchav', 'valeur': 190, 'masse': 94},
          {'nom': 'rlaurentinaw', 'valeur': 131, 'masse': 39},
          {'nom': 'ostansallax', 'valeur': 77, 'masse': 71},
          {'nom': 'mchettleay', 'valeur': 65, 'masse': 78},
          {'nom': 'rmccromleyaz', 'valeur': 92, 'masse': 65},
          {'nom': 'sledwardb0', 'valeur': 122, 'masse': 80},
          {'nom': 'egarwillb1', 'valeur': 169, 'masse': 99},
          {'nom': 'mshepeardb2', 'valeur': 180, 'masse': 79},
          {'nom': 'jdaveranb3', 'valeur': 83, 'masse': 87}]

Vous êtes un nouvel acteur sur le marché et vous avez un budget de 500 pour constituer une nouvelle équipe. Constituez l'équipe ayant la plus grande valeur possible.
Quelle stratégie avez-vous employé ?

Remarque☘

Imaginons maintenant que les objets soient des poudres (poudre d'or, poudre de perlimpinpin, etc...) : on en charge la fraction que l'on veut.

Dans ce cas, la stratégie n°1 consistant à charger la masse maximale possible de chaque poudre en les prenant dans l'ordre décroissant des valeurs massiques donne un résultat optimal.

Cas particulier

Si deux poudres ont le même prix au kilogramme, les chargements obtenus par l'algorithme peuvent différer par le choix de la poudre.
On considèrera pour simplifier que deux poudres ayant même valeur au kilogramme sont identiques.

Justification du caractère optimal

Rappel du principe

Le chargement total ne peut dépasser M.

  • On prend autant de kg de la poudre la plus chère au kg (une masse M s'il y en a assez, toute la poudre s'il y en a moins que M).
  • La poudre la plus chère au kg étant épuisée, on charge ensuite la poudre la plus chère au kg parmi celles qui restent (on charge jusqu'à M s'il y en a assez, on prend tout sinon).
  • ... et ainsi de suite jusqu'à la masse M maximale du chargement.

Pourquoi cela mène-t-il à un chargement de valeur maximale ?

Notons G le chargement obtenu par l'algorithme glouton et C un chargement de valeur maximale. Notons q la masse de poudre la plus précieuse dans ce chargement C et qg la masse de cette poudre dans G.

  • On a nécessairement q ≤ qg par définition de notre algorithme.
  • Si l'on a q < qg, on peut remplacer dans le chargement C une masse qg-q de poudres moins chères par la poudre la plus précieuse et on améliore ainsi la valeur de C, en contradiction avec son caractère optimal. Cela montre qu'un chargement de valeur optimale a la même masse de la poudre la plus chère que G.

Si la masse M était atteinte, C et G sont identiques. Sinon, on a épuisé la poudre la plus chère. Supprimons cette poudre de notre chargement C et de notre chargement G : le même raisonnement fait sur la poudre la plus chère suivante montre que cette seconde poudre est en même quantité dans les deux chargements...

En poursuivant ainsi, on constate que C et G sont identiques.