NSI1_24_algo_glouton_Corrections.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table style=\"width:100%;\">\n",
    "    <tr>\n",
    "        <th><h2>NSI1</h2></th>\n",
    "        <th><h2>e24b</h2></th>\n",
    "        <th style=\"width:80%;\" colspan=\"2\"><h2>Algorithmique</h2></th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td colspan=\"4\"><h3>Algorithmes gloutons</h3></td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td colspan=\"3\"><h3>Corrections des exercices</h3></td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objectifs de la séquence: \n",
    "Série d'exercices pour mettre en oeuvre des algorithmes gloutons.  \n",
    "Dernier exercice: Problème classique du sac à dos.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 1 : Calcul d’itinéraires (cf diaporama r24a)\n",
    "### Problème posé : \n",
    "Je souhaite me rendre du point A au point D en passant par 2 étapes intermédiaires (B et C).  \n",
    "![Parcours avec 2 étapes](images/NSI1_24_ex1_parcours_AD.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">\n",
    "    \n",
    "**Solutions optimales recherchée :** Je souhaite que mon  trajet soit le plus court possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">\n",
    "    \n",
    "**Solution gloutonne :** En partant de A, je vais systématiquement me rendre à l’étape la plus proche du point actuel pour finalement rejoindre le point D."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q1-1 :** Représentez sous la forme d’un graphe tous les chemins possibles.  \n",
    "![Graphe avec 2 étapes](images/NSI1_24_ex1_parcours_2etapes.png)\n",
    "**Q1-2 :** D’après le cours, combien  de chemins sont possibles avec 3 étapes intermédiaires ? \n",
    "Il existe 6 chemins différents.  \n",
    "![Graphe avec 3 étapes](images/NSI1_24_ex1_parcours_3etapes.png)\n",
    "\n",
    "**Q1-3 :** Vérifiez qu’il existe 24 chemins possibles avec 4 étapes intermédiaires.  (Présentez le calcul qu’il faut faire)  \n",
    "**Départ:** A  \n",
    "**Etapes:** B,C,D et E  \n",
    "**Arrivée:** F  \n",
    "Depuis le point A, j'ai 4 possibilités pour la première étapes (B,C,D et E)  \n",
    "Puis pour chaque étape secondaire, il me reste 3 choix possibles, puis deux, puis la dernière:\n",
    "\n",
    "$S = 4 * 3 * 2 * 1 = 24$\n",
    "\n",
    "**Q1-4 : Généralisation :** Pour n étapes intermédiaires, quel serait le nombre de chemins possibles à envisager ?  \n",
    "\n",
    "$S = n * (n-1) * (n-2) * ... * 2 * 1$  \n",
    "\n",
    "Que l'on peut aussi écrire sous cette forme:  $S = \\displaystyle \\prod_{i=1}^n i$\n",
    "\n",
    "Mais on utilise plus généralement la notation :  $S = n!$  \n",
    "Qui se lit **\"n factorielle\"**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 2 : Festival culturel\n",
    "<div style=\"width:100%;border-collapse:separate;border:solid 2px;border-radius:4px;\">\n",
    "    <div style=\"display:flex;background-color:#EEE;border:1px solid black;\">\n",
    "        <div style=\"display:inline;width:50%;text-align:left;border:1px solid black;\">\n",
    "            <b>Règle de choix de l'algorithme A</b></div>\n",
    "        <div style=\"display:inline;width:50%;text-align:left;border:1px solid black;\">\n",
    "            <b>Règle de choix de l'algorithme B</b></div>\n",
    "    </div>\n",
    "    <div  style=\"display: flex;border:1px solid black;\">\n",
    "        <div style=\"display:inline;width:50%;text-align:left;border:1px solid black;\">À chaque étape choisir, parmi les cinq scènes, le prochain spectacle qui <b>commence</b> en premier.</div>\n",
    "        <div style=\"display:inline;width:50%;text-align:left;border:1px solid black;\">À chaque étape choisir, parmi les cinq scènes,  le prochain spectacle qui <b>finit</b> en premier.</div>\n",
    "    </div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q2-1 :**\n",
    "\n",
    "<table style=\"border:1px solid black;\">\n",
    "    <tr style=\"text-align:left;background-color:#EEE;\">\n",
    "        <td style=\"border:1px solid black;text-align:center;\"><b>Déroulé avec l'algorithme A</b><br>\n",
    "        </td>\n",
    "        <td style=\"border:1px solid black;text-align:center;\"><b>Planning des spectacles</b>\n",
    "        </td>\n",
    "        <td style=\"border:1px solid black;text-align:center;\"><b>Déroulé avec l'algorithme B</b><br>\n",
    "        </td>\n",
    "    </tr>\n",
    "    <tr style=\"text-align:left;background-color:#FFF;\">\n",
    "        <td style=\"border:1px solid black;text-align:center;\">\n",
    "        Étape 1 : spectacle 3A<br>\n",
    "        Étape 2 : spectacle 2B<br>\n",
    "        Étape 3 : spectacle 3B<br>\n",
    "        Étape 4 : spectacle 2C<br>\n",
    "        Étape 5 : spectacle 3D<br>\n",
    "        Étape 6 : spectacle 2D<br>\n",
    "        Étape 7 : spectacle 4D<br>\n",
    "        Étape 8 : spectacle 3F<br>\n",
    "        Étape 9 : spectacle 3G<br>\n",
    "        Étape 10 : spectacle 2G<br>\n",
    "        </td>\n",
    "        <td>\n",
    "                \n",
    "![Planning des spectables](images/NSI1_24_ex2_spectacles.png)\n",
    "        </td>\n",
    "        <td style=\"border:1px solid black;text-align:center;\">\n",
    "        Étape 1 : spectacle 4A<br>\n",
    "        Étape 2 : spectacle 2A<br>\n",
    "        Étape 3 : spectacle 4B<br>\n",
    "        Étape 4 : spectacle 3B<br>\n",
    "        Étape 5 : spectacle 3C ou 2C<br>\n",
    "        Étape 6 : spectacle 3D<br>\n",
    "        Étape 7 : spectacle 5D<br>\n",
    "        Étape 8 : spectacle 5E<br>\n",
    "        Étape 9 : spectacle 5F<br>\n",
    "        Étape 10 : spectacle 3F<br>\n",
    "        Étape 11 : spectacle 3G<br>\n",
    "        Étape 12 : spectacle 2G<br>\n",
    "        </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q2-2 :** L'algorithme glouton B permet de voir 12 spectacles au lieu de 10 avec le A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercice 3 : Traversée de  la grille\n",
    "\n",
    "<div style=\"display:inline-block;width:65%;vertical-align: middle;\">Sur la grille ci-contre, on part de la case tout à gauche marquée de la lettre D.<br>\n",
    "On souhaite atteindre les cases vides sur la partie droite en se déplaçant de case en case.<br>\n",
    "Lorsqu'on est sur une case on peut se déplacer sur une des deux cases  voisines situées sur la droite.<br>\n",
    "On note S la somme de toutes les cases traversées.</div>\n",
    "\n",
    "<div style=\"display:inline-block;width:30%;vertical-align: middle;\">\n",
    "\n",
    "![Grille initiale](images/NSI1_24_ex3_traversee-1.png)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"display:inline-block;width:65%;vertical-align: middle;\">Par exemple on peut effectuer la trajectoire suivante : <br>\n",
    "D - 7 – 5 – 3 – 5 – 7 – 9 – 8 – 9 – 6 qui conduit à S = 59.<br>\n",
    "On cherche à effectuer la trajectoire qui rend la somme S la plus petite possible.\n",
    "</div>\n",
    "\n",
    "<div style=\"display:inline-block;width:30%;vertical-align: middle;\">\n",
    "\n",
    "![Grille avec premier chemin](images/NSI1_24_ex3_traversee-2.png)\n",
    "</div>\n",
    "\n",
    "**Q3-1 :** Que cherche-t-on à sélectionner ?  \n",
    "<span style=\"color:green\">Un ensemble de cases (une trajectoire) </span> \n",
    "\n",
    "**Q3-2 :** Quelles sont les contraintes ?  \n",
    "<span style=\"color:green\">La trajectoire est constituée de cases voisines les unes des autres, doit partir de D, arriver dans la zone vide et ne peut pas \"revenir en arrière\".  </span> \n",
    "\n",
    "**Q3-3 :** Quelle est l'optimisation recherchée ?  \n",
    "<span style=\"color:green\">Minimiser la somme des chiffres présents dans les cases de la trajectoire.</span> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"display:inline-block;width:65%;vertical-align: middle;\">\n",
    "    \n",
    "**Q3-4 :** Déterminer une règle de choix qui permet de définir un algorithme glouton.  \n",
    "<span style=\"color:green\">Lorsqu'on est positionné sur une case, parmi les deux cases suivantes possibles, choisir celle ayant le plus petit chiffre.  </span><br>\n",
    "**Q3-4 :** Quelle trajectoire et quelle somme S obtenez-vous sur cet exemple avec votre algorithme glouton ?  \n",
    "<span style=\"color:green\">D – 4 – 4 – 2 – 5 – 7 – 7 – 8 – 8 – 1  <br>\n",
    "S = 46</span>\n",
    "\n",
    "</div>\n",
    "\n",
    "<div style=\"display:inline-block;width:30%;vertical-align: middle;\">\n",
    "\n",
    "![Grille avec chemin glouton](images/NSI1_24_ex3_traversee-3.png)\n",
    "</div>"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"display:inline-block;width:65%;vertical-align: middle;\">\n",
    "    \n",
    "**Q3-6 :**  \n",
    "Sur cette grille, en cherchant bien, la trajectoire optimale donne une somme S=23.  \n",
    "<span style=\"color:green\">D – 4 – 4 – 3 – 2 – 3 – 1 – 3 – 1 – 2 <br></span>\n",
    "Votre algorithme glouton a-t-il trouvé cette trajectoire optimale ? <br>\n",
    "<span style=\"color:green\">Non.  </span><br>\n",
    "Si la réponse est non, est-ce que la trajectoire trouvée est \"proche\" de la trajectoire optimale ?<br>\n",
    "<span style=\"color:green\">Pas tellement : on obtient deux fois plus. <br></span>\n",
    "\n",
    "\n",
    "</div>\n",
    "\n",
    "<div style=\"display:inline-block;width:30%;vertical-align: middle;\">\n",
    "\n",
    "![Grille avec chemin optimal](images/NSI1_24_ex3_traversee-4.png)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3-7 :**\n",
    "Pour obtenir la solution optimale de façon certaine on souhaite trouver toutes les trajectoires possibles  et calculer pour chacune d'elles la somme associée. \n",
    "<span style=\"color:green\">\n",
    "Pour obtenir une trajectoire, à chaque changement de case, on a 2 possibilités : vers le haut (choix 0) ou vers le bas (choix 1).<br>\n",
    "Or on effectue 9 déplacements.<br>\n",
    "Chaque trajectoire correspond donc de façon unique à un codage sur 9 bits.<br> \n",
    "Par exemple 110011111 correspond à la trajectoire obtenue en faisant:<br> Bas – Bas – Haut – Haut – Bas – Bas – Bas – Bas – Bas.<br>\n",
    "Il y a donc 2^9=512 trajectoires possibles.</span>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problème du sac à dos\n",
    "\n",
    "Rapide rappel des deux situations-problèmes.\n",
    "### Situation n°1 :  \n",
    "\n",
    "Un cambrioleur ne peut emporter que 40 kg sur son dos dans son sac. \n",
    "Il va se demander quels objets choisir pour obtenir une valeur totale maximale tout en ne dépassant pas 40 kg.\n",
    "\n",
    "\n",
    "### Situation n°2\n",
    "\n",
    "On part en vacances avec une clef USB de 8 Go. Nous souhaitons copier sur cette clef des fichiers vidéos pour lesquels la taille n'est pas proportionnelle à la durée car les fichiers sont de formats différents et de résolutions différentes.\n",
    "On se demande quelles vidéos copier sur la clef pour obtenir une durée totale maximale tout en ne dépassant pas 8 Go."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">\n",
    "\n",
    "\n",
    "**Question :**  \n",
    "    \n",
    "Pour la situation n°1 :  \n",
    "    \n",
    "- Quelle est la sélection que l'on cherche à effectuer ?   \n",
    "    \n",
    "    - une sélection d'objets\n",
    "    \n",
    "- Quelle est la contrainte ?   \n",
    "    \n",
    "    - le poids total des objets emportés doit être inférieur ou égal à 40.\n",
    "    \n",
    "- Quelle est l'optimisation recherchée ?   \n",
    "    \n",
    "    - La valeur totale des objets emportés doit être la plus grande possible.\n",
    "    \n",
    "\n",
    "**Question :**  \n",
    "    \n",
    "Pour la situation n°2 :  \n",
    "\n",
    "- Quelle est la sélection que l'on cherche à effectuer ?  \n",
    "    \n",
    "    - une sélection de vidéos\n",
    "    \n",
    "- Quelle est la contrainte ?  \n",
    "    \n",
    "    - Le poids total des vidéos doit être inférieur ou égal à 8.\n",
    "    \n",
    "- Quelle est l'optimisation recherchée ?  \n",
    "    \n",
    "    - La valeur totale des vidéos emportées doit être la plus grande possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithme glouton"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">\n",
    "\n",
    "\n",
    "**Question :**  \n",
    "    \n",
    "Pour la situation n°1 :  \n",
    "    \n",
    "- Pourquoi le cambrioleur a sans doute intérêt à emporter l'objet G ?   \n",
    "    \n",
    "    - car il n'est pas lourd mais a beaucoup de valeur\n",
    "    \n",
    "- Pourquoi le cambrioleur n'a sans doute pas intérêt à emporter l'objet B ?   \n",
    "    \n",
    "    - car il est lourd mais il n' a pas beaucoup de valeur \n",
    "\n",
    "\n",
    "**Question :**  \n",
    "    \n",
    "Pour la situation n°2 :  \n",
    "    \n",
    "- Pourquoi a-t-on sans doute intérêt à emporter la vidéo B ?  \n",
    "    \n",
    "    - car elle n'est pas lourde mais a beaucoup de valeur\n",
    "    \n",
    "- Pourquoi n'a-t-on sans doute pas intérêt à emporter la vidéo J ?   \n",
    "    \n",
    "    - car elle est lourde mais n'a pas beaucoup de valeur"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-danger\">\n",
    "   \n",
    "### Règle de choix :\n",
    "    \n",
    "À chaque étape prendre l'objet ayant le plus grand rapport valeur/poids parmi les objets dont le poids ne fait pas dépasser le poids total autorisé.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Représentation des données\n",
    "\n",
    "Les données seront représentées sous forme de tables (listes de dictionnaires) :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "table_1 = [\n",
    "    {'nom' : 'objet A', 'poids' : 15, 'valeur' : 500},\n",
    "    {'nom' : 'objet B', 'poids' : 24, 'valeur' : 400},\n",
    "    {'nom' : 'objet C', 'poids' : 9,  'valeur' : 350},\n",
    "    {'nom' : 'objet D', 'poids' : 25, 'valeur' : 750},\n",
    "    {'nom' : 'objet E', 'poids' : 5,  'valeur' : 400},\n",
    "    {'nom' : 'objet F', 'poids' : 12, 'valeur' : 800},\n",
    "    {'nom' : 'objet G', 'poids' : 2,  'valeur' : 1400},\n",
    "    {'nom' : 'objet H', 'poids' : 18, 'valeur' : 550}\n",
    "]\n",
    "\n",
    "\n",
    "\n",
    "table_2 = [\n",
    "    {'nom' : 'video A', 'poids' : 4.5,   'valeur' : 114},\n",
    "    {'nom' : 'video B', 'poids' : 0.63,  'valeur' : 85},\n",
    "    {'nom' : 'video C', 'poids' : 3.35,  'valeur' : 40},\n",
    "    {'nom' : 'video D', 'poids' : 0.085, 'valeur' : 4},\n",
    "    {'nom' : 'video E', 'poids' : 2.15,  'valeur' : 18},\n",
    "    {'nom' : 'video F', 'poids' : 2.71,  'valeur' : 80},\n",
    "    {'nom' : 'video G', 'poids' : 0.32,  'valeur' : 5},\n",
    "    {'nom' : 'video H', 'poids' : 3.7,   'valeur' : 86},\n",
    "    {'nom' : 'video I', 'poids' : 2.4,   'valeur' : 64},\n",
    "    {'nom' : 'video J', 'poids' : 6.4,   'valeur' : 12}\n",
    "]    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trier la table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rapport_valeur_poids(dico_objet):\n",
    "    \"\"\" Prend en paramètre un dictionnaire dico_objet \n",
    "        Renvoie le rapport de la valeur divisée par le poids de l'objet.\n",
    "    \"\"\"\n",
    "    return dico_objet['valeur']/dico_objet['poids']\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30.0\n",
      "700.0\n"
     ]
    }
   ],
   "source": [
    "print( rapport_valeur_poids({'nom' : 'objet D', 'poids' : 25, 'valeur' : 750}))\n",
    "# On  s'attend à obtenir 750 / 25 soit 30 unité de valeur par unité de coût\n",
    "print( rapport_valeur_poids({'nom' : 'objet G', 'poids' : 2,  'valeur' : 1400}))\n",
    "# On  s'attend à obtenir 1400 / 2 soit 700 unité de valeur par unité de coût\n",
    "# On en déduit qu'il est préféreble de sélectionner le second objet a priori"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def donner_poids(dico_objet):\n",
    "    \"\"\" Prend en paramètre un dictionnaire dico_objet\n",
    "        Renvoie le poids de l'objet\n",
    "    \"\"\"\n",
    "    return dico_objet['poids']\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25\n"
     ]
    }
   ],
   "source": [
    "print( donner_poids({'nom' : 'objet D', 'poids' : 25, 'valeur' : 750}))\n",
    "# On s'attends à obtenir 25"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">  \n",
    "\n",
    "**Question:**   \n",
    "    \n",
    "    \n",
    "Créer une fonction `creer_table_triee` qui prend en paramètre une table d'objets `table_objets` (table similaire aux deux tables `table_1` et `table_2` ci-dessus) et renvoie une copie triée en deux étapes de cette table :  \n",
    "\n",
    "- triee selon le poids des objets décroissant  \n",
    "\n",
    "\n",
    "- puis triee selon le rapport valeur/poids décroissant  \n",
    "    \n",
    "    \n",
    "On utilisera pour cela les deux fonctions clef de tri `donner_poids` et `rapport_valeur_sur_poids`.\n",
    "    \n",
    "\n",
    "\n",
    "**Si besoin, retourner voir son cours et ses exercices sur le traitement de donnée en tables.**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def creer_table_triee(table_objets):\n",
    "    \"\"\" Prend en paramètre une table d'objets table_objets\n",
    "        Trie selon le poids des objets décroissant\n",
    "        Puis trie selon le rapport valeur/poids décroissant\n",
    "    \"\"\"\n",
    "    table_apres_premier_tri = sorted(table_objets, key = donner_poids, reverse = True)\n",
    "    table_apres_second_tri = sorted(table_apres_premier_tri, key = rapport_valeur_poids, reverse = True)\n",
    "    \"\"\" Le premier tri prépare la liste pour que le second tri place l'objet le moins lourd\n",
    "        devant  en cas d'égalité du rapport valeur / poids.\n",
    "        On recréé la liste des objets dans l'ordre croissant du rapport valeur/coût.\n",
    "    \"\"\"\n",
    "    return table_apres_second_tri"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'nom': 'objet G', 'poids': 2, 'valeur': 1400} rapport valeur / coût =  700.0\n",
      "{'nom': 'objet E', 'poids': 5, 'valeur': 400} rapport valeur / coût =  80.0\n",
      "{'nom': 'objet F', 'poids': 12, 'valeur': 800} rapport valeur / coût =  66.66666666666667\n",
      "{'nom': 'objet C', 'poids': 9, 'valeur': 350} rapport valeur / coût =  38.888888888888886\n",
      "{'nom': 'objet A', 'poids': 15, 'valeur': 500} rapport valeur / coût =  33.333333333333336\n",
      "{'nom': 'objet H', 'poids': 18, 'valeur': 550} rapport valeur / coût =  30.555555555555557\n",
      "{'nom': 'objet D', 'poids': 25, 'valeur': 750} rapport valeur / coût =  30.0\n",
      "{'nom': 'objet B', 'poids': 24, 'valeur': 400} rapport valeur / coût =  16.666666666666668\n",
      "Poids total des objets sélectionnés 110\n"
     ]
    }
   ],
   "source": [
    "def affiche_resultat_glouton(table):\n",
    "    t = creer_table_triee(table) \n",
    "    # t correspond à la liste des objets de table triée selon le rapport valeur / coût\n",
    "    # On affiche chaque élément de t suivi du rapport valeur / coût. \n",
    "    somme_poids = 0 \n",
    "    for element in t:\n",
    "        somme_poids += donner_poids(element)\n",
    "        print(element,'rapport valeur / coût = ', rapport_valeur_poids(element))\n",
    "    # On vérifie bien que les rapport valeur / coût sont décroissants\n",
    "    print (\"Poids total des objets sélectionnés\", somme_poids)\n",
    "    # Pour finir, on affiche le poids total des objets sélectionnés\n",
    "    \n",
    "affiche_resultat_glouton(table_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parcourir la table triée et sélectionner les objets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">  \n",
    "\n",
    "**Question:**  \n",
    "\n",
    "Compléter la fonction `selectionner` qui prend en paramètre une table `table_objets` (table similaire aux deux tables `table_1` et `table_2` ci-dessus) ainsi qu'un poids maximal `poids_max` et retourne dans une table `table_selection` la sélection d'objets obtenue selon l'algorithme glouton.  \n",
    "    \n",
    " \n",
    "On rappelle que pour ajouter un élément `elt` dans une liste `L` on peut utiliser l'instruction `L.append(elt)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selectionner( table_objets, poids_max):\n",
    "    \"\"\" Prend en paramètre une table table_objets, ainsi qu'un poids maximal poids_max\n",
    "        Renvoie dans une table table_selection la sélection d'objets obtenue selon l'algorithme glouton\n",
    "    \"\"\"\n",
    "    table_triee = creer_table_triee(table_objets)\n",
    "    # La liste est triée selon le rapport valeur / coût décroissant\n",
    "    poids_total = 0\n",
    "    table_selection = []\n",
    "    # On initialise les variables. Le sac est vide: Aucun élément, poids nul.\n",
    "    for objet in table_triee:\n",
    "        # Pour chaque objet de la liste triée ...\n",
    "        if poids_total + donner_poids(objet) <= poids_max :\n",
    "            # Si l'objet arrive à rentrer\n",
    "            # Alorson ajoute son 'poids' à la somme des poids des objets dans le sac\n",
    "            poids_total = poids_total + donner_poids(objet)\n",
    "            # et on le rajoute à la liste des objets entrés \n",
    "            table_selection.append(objet)\n",
    "    return table_selection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Exemple pour une sélection d'objet de la table_1 avec un sac de poids_max = 40\n",
      "{'nom': 'objet G', 'poids': 2, 'valeur': 1400} rapport valeur / coût =  700.0\n",
      "{'nom': 'objet E', 'poids': 5, 'valeur': 400} rapport valeur / coût =  80.0\n",
      "{'nom': 'objet F', 'poids': 12, 'valeur': 800} rapport valeur / coût =  66.66666666666667\n",
      "{'nom': 'objet C', 'poids': 9, 'valeur': 350} rapport valeur / coût =  38.888888888888886\n",
      "Poids total des objets sélectionnés 28\n",
      "\n",
      " Exemple pour une sélection d'objet de la table_2 avec un sac de poids_max = 8\n",
      "{'nom': 'video B', 'poids': 0.63, 'valeur': 85} rapport valeur / coût =  134.9206349206349\n",
      "{'nom': 'video D', 'poids': 0.085, 'valeur': 4} rapport valeur / coût =  47.05882352941176\n",
      "{'nom': 'video F', 'poids': 2.71, 'valeur': 80} rapport valeur / coût =  29.52029520295203\n",
      "{'nom': 'video I', 'poids': 2.4, 'valeur': 64} rapport valeur / coût =  26.666666666666668\n",
      "{'nom': 'video G', 'poids': 0.32, 'valeur': 5} rapport valeur / coût =  15.625\n",
      "Poids total des objets sélectionnés 6.145\n"
     ]
    }
   ],
   "source": [
    "# On répond à l'énoncé du problème 1\n",
    "print(\"\\n Exemple pour une sélection d'objet de la table_1 avec un sac de poids_max = 40\")\n",
    "affiche_resultat_glouton( selectionner( table_1, 40) )\n",
    "\n",
    "# On répond à l'énoncé du problème 1\n",
    "print(\"\\n Exemple pour une sélection d'objet de la table_2 avec un sac de poids_max = 8\")\n",
    "affiche_resultat_glouton( selectionner( table_2, 8)  )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">  \n",
    "\n",
    "**Question :**  \n",
    "\n",
    "\n",
    "Les deux solutions fournies ne sont pas les meilleures possibles. Essayer de trouver des solutions meilleures que celles fournies par l'algorithme.\n",
    "    \n",
    "    \n",
    "- Pour la `table_1`, on emmène un poids de 2 + 5 + 12 + 9 = 28. On a 12 de marge pour le poids total. On peut donc remplacer l'objet C qui a un poids de 9 par l'objet H qui a un poids de 18. En faisant ainsi on augmente de 200 la valeur totale du sac.\n",
    "    \n",
    "    \n",
    "- Pour la `table_2`, on emmène un poids de 0.63 + 0.085 + 2.71 + 2.4 + 0.32 = 6.145. On a 8 - 6.145 = 1.855 de marge pour le poids total. On peut donc par exemple remplacer la vidéo I par la vidéo H et augmenter ainsi de 22 la valeur totale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class = \"alert alert-info\">  \n",
    "\n",
    "**Question :**  \n",
    "\n",
    "Dans la table ci-dessous, la valeur représente le score moyen de certains joueurs (à un jeu, à un sport) et le poids  l'indemnité qu'ils exigent pour faire partie d'une équipe lors d'un tournoi. \n",
    "Vous disposez d'un budget égal à 500 : en utilisant la fonctin que vous venez de coder, constituez votre équipe la plus grande possible.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "table_3 = [\n",
    "{\"nom\":\"atuffell0\",\"poids\":78,\"valeur\":186},\n",
    "{\"nom\":\"alacroux1\",\"poids\":35,\"valeur\":71},\n",
    "{\"nom\":\"lesposita2\",\"poids\":31,\"valeur\":90},\n",
    "{\"nom\":\"ascandred3\",\"poids\":53,\"valeur\":182},\n",
    "{\"nom\":\"cheathcoat4\",\"poids\":78,\"valeur\":173},\n",
    "{\"nom\":\"mpechan5\",\"poids\":69,\"valeur\":94},\n",
    "{\"nom\":\"kmurison6\",\"poids\":33,\"valeur\":97},\n",
    "{\"nom\":\"cschwandermann7\",\"poids\":95,\"valeur\":179},\n",
    "{\"nom\":\"khanrott8\",\"poids\":53,\"valeur\":56},\n",
    "{\"nom\":\"wkiln9\",\"poids\":93,\"valeur\":162},\n",
    "{\"nom\":\"tpaolilloa\",\"poids\":63,\"valeur\":67},\n",
    "{\"nom\":\"aboudab\",\"poids\":71,\"valeur\":131},\n",
    "{\"nom\":\"dgribbinsc\",\"poids\":44,\"valeur\":179},\n",
    "{\"nom\":\"vdavittd\",\"poids\":30,\"valeur\":131},\n",
    "{\"nom\":\"ssalmonde\",\"poids\":66,\"valeur\":51},\n",
    "{\"nom\":\"svawtonf\",\"poids\":32,\"valeur\":45},\n",
    "{\"nom\":\"coculleng\",\"poids\":58,\"valeur\":47},\n",
    "{\"nom\":\"lstandenh\",\"poids\":46,\"valeur\":103},\n",
    "{\"nom\":\"cshoardi\",\"poids\":30,\"valeur\":68},\n",
    "{\"nom\":\"mowlnerj\",\"poids\":75,\"valeur\":51},\n",
    "{\"nom\":\"mondrichk\",\"poids\":75,\"valeur\":128},\n",
    "{\"nom\":\"mpatterfieldl\",\"poids\":97,\"valeur\":143},\n",
    "{\"nom\":\"sduttm\",\"poids\":42,\"valeur\":90},\n",
    "{\"nom\":\"ryuryshevn\",\"poids\":78,\"valeur\":50},\n",
    "{\"nom\":\"cwillettso\",\"poids\":36,\"valeur\":176},\n",
    "{\"nom\":\"cmuldowniep\",\"poids\":92,\"valeur\":100},\n",
    "{\"nom\":\"hgabbitasq\",\"poids\":82,\"valeur\":188},\n",
    "{\"nom\":\"vclaughtonr\",\"poids\":72,\"valeur\":60},\n",
    "{\"nom\":\"bnoldas\",\"poids\":36,\"valeur\":173},\n",
    "{\"nom\":\"hurquhartt\",\"poids\":61,\"valeur\":160},\n",
    "{\"nom\":\"ghalkyardu\",\"poids\":55,\"valeur\":199},\n",
    "{\"nom\":\"gallredv\",\"poids\":56,\"valeur\":91},\n",
    "{\"nom\":\"bfritschelw\",\"poids\":93,\"valeur\":178},\n",
    "{\"nom\":\"nrobothamx\",\"poids\":44,\"valeur\":112},\n",
    "{\"nom\":\"tmcginny\",\"poids\":52,\"valeur\":152},\n",
    "{\"nom\":\"avallintinez\",\"poids\":62,\"valeur\":175},\n",
    "{\"nom\":\"santcliffe10\",\"poids\":42,\"valeur\":174},\n",
    "{\"nom\":\"radrien11\",\"poids\":67,\"valeur\":119},\n",
    "{\"nom\":\"lmordie12\",\"poids\":46,\"valeur\":194},\n",
    "{\"nom\":\"cprosch13\",\"poids\":73,\"valeur\":74},\n",
    "{\"nom\":\"wscain14\",\"poids\":94,\"valeur\":94},\n",
    "{\"nom\":\"gripping15\",\"poids\":91,\"valeur\":103},\n",
    "{\"nom\":\"ybatterton16\",\"poids\":93,\"valeur\":161},\n",
    "{\"nom\":\"ckernan17\",\"poids\":75,\"valeur\":106},\n",
    "{\"nom\":\"mhousecroft18\",\"poids\":67,\"valeur\":84},\n",
    "{\"nom\":\"gprudence19\",\"poids\":68,\"valeur\":89},\n",
    "{\"nom\":\"flamberto1a\",\"poids\":100,\"valeur\":65},\n",
    "{\"nom\":\"dgammon1b\",\"poids\":40,\"valeur\":166},\n",
    "{\"nom\":\"jkidde1c\",\"poids\":69,\"valeur\":200},\n",
    "{\"nom\":\"amewrcik1d\",\"poids\":90,\"valeur\":54},\n",
    "{\"nom\":\"fpyke1e\",\"poids\":97,\"valeur\":114},\n",
    "{\"nom\":\"mfellows1f\",\"poids\":80,\"valeur\":188},\n",
    "{\"nom\":\"cknoton1g\",\"poids\":36,\"valeur\":113},\n",
    "{\"nom\":\"nharrema1h\",\"poids\":42,\"valeur\":192},\n",
    "{\"nom\":\"vtomasik1i\",\"poids\":40,\"valeur\":64},\n",
    "{\"nom\":\"scoping1j\",\"poids\":46,\"valeur\":185},\n",
    "{\"nom\":\"mdyball1k\",\"poids\":34,\"valeur\":50},\n",
    "{\"nom\":\"dvelde1l\",\"poids\":80,\"valeur\":112},\n",
    "{\"nom\":\"kconkay1m\",\"poids\":45,\"valeur\":193},\n",
    "{\"nom\":\"dglanister1n\",\"poids\":86,\"valeur\":195},\n",
    "{\"nom\":\"rhobell1o\",\"poids\":88,\"valeur\":167},\n",
    "{\"nom\":\"lseakes1p\",\"poids\":93,\"valeur\":130},\n",
    "{\"nom\":\"twootton1q\",\"poids\":62,\"valeur\":132},\n",
    "{\"nom\":\"agooderridge1r\",\"poids\":49,\"valeur\":121},\n",
    "{\"nom\":\"tkilcullen1s\",\"poids\":80,\"valeur\":180},\n",
    "{\"nom\":\"ssteinor1t\",\"poids\":38,\"valeur\":81},\n",
    "{\"nom\":\"theller1u\",\"poids\":47,\"valeur\":102},\n",
    "{\"nom\":\"jpetrozzi1v\",\"poids\":87,\"valeur\":141},\n",
    "{\"nom\":\"iivanitsa1w\",\"poids\":41,\"valeur\":78},\n",
    "{\"nom\":\"lkohn1x\",\"poids\":43,\"valeur\":114},\n",
    "{\"nom\":\"afinlater1y\",\"poids\":81,\"valeur\":159},\n",
    "{\"nom\":\"mbrogioni1z\",\"poids\":81,\"valeur\":52},\n",
    "{\"nom\":\"fcrinson20\",\"poids\":45,\"valeur\":73},\n",
    "{\"nom\":\"mgreedyer21\",\"poids\":49,\"valeur\":74},\n",
    "{\"nom\":\"ccheyenne22\",\"poids\":33,\"valeur\":200},\n",
    "{\"nom\":\"hwinterbourne23\",\"poids\":56,\"valeur\":90},\n",
    "{\"nom\":\"oblampied24\",\"poids\":34,\"valeur\":90},\n",
    "{\"nom\":\"cbydaway25\",\"poids\":34,\"valeur\":158},\n",
    "{\"nom\":\"kslocumb26\",\"poids\":69,\"valeur\":107},\n",
    "{\"nom\":\"jherion27\",\"poids\":98,\"valeur\":49},\n",
    "{\"nom\":\"vhallagan28\",\"poids\":36,\"valeur\":198},\n",
    "{\"nom\":\"jcanada29\",\"poids\":31,\"valeur\":187},\n",
    "{\"nom\":\"zleavey2a\",\"poids\":94,\"valeur\":146},\n",
    "{\"nom\":\"klownes2b\",\"poids\":36,\"valeur\":144},\n",
    "{\"nom\":\"lmuzzillo2c\",\"poids\":46,\"valeur\":140},\n",
    "{\"nom\":\"uarnal2d\",\"poids\":60,\"valeur\":190},\n",
    "{\"nom\":\"rclem2e\",\"poids\":93,\"valeur\":126},\n",
    "{\"nom\":\"fstuehmeyer2f\",\"poids\":30,\"valeur\":63},\n",
    "{\"nom\":\"dchinery2g\",\"poids\":78,\"valeur\":164},\n",
    "{\"nom\":\"zeilers2h\",\"poids\":46,\"valeur\":51},\n",
    "{\"nom\":\"jcordingly2i\",\"poids\":38,\"valeur\":192},\n",
    "{\"nom\":\"fstollard2j\",\"poids\":93,\"valeur\":134},\n",
    "{\"nom\":\"adannell2k\",\"poids\":62,\"valeur\":47},\n",
    "{\"nom\":\"cbryenton2l\",\"poids\":38,\"valeur\":81},\n",
    "{\"nom\":\"mcardinal2m\",\"poids\":72,\"valeur\":79},\n",
    "{\"nom\":\"escattergood2n\",\"poids\":38,\"valeur\":67},\n",
    "{\"nom\":\"arecord2o\",\"poids\":57,\"valeur\":170},\n",
    "{\"nom\":\"cbertl2p\",\"poids\":47,\"valeur\":183},\n",
    "{\"nom\":\"ssprott2q\",\"poids\":40,\"valeur\":67},\n",
    "{\"nom\":\"fegell2r\",\"poids\":57,\"valeur\":126},\n",
    "{\"nom\":\"eferrie2s\",\"poids\":33,\"valeur\":153},\n",
    "{\"nom\":\"mjizhaki2t\",\"poids\":31,\"valeur\":149},\n",
    "{\"nom\":\"lolsson2u\",\"poids\":64,\"valeur\":76},\n",
    "{\"nom\":\"alorentzen2v\",\"poids\":33,\"valeur\":157},\n",
    "{\"nom\":\"mdominik2w\",\"poids\":44,\"valeur\":110},\n",
    "{\"nom\":\"rmckenny2x\",\"poids\":74,\"valeur\":132},\n",
    "{\"nom\":\"bdavydenko2y\",\"poids\":92,\"valeur\":115},\n",
    "{\"nom\":\"mkienl2z\",\"poids\":38,\"valeur\":102},\n",
    "{\"nom\":\"mgroger30\",\"poids\":68,\"valeur\":186},\n",
    "{\"nom\":\"haggett31\",\"poids\":40,\"valeur\":186},\n",
    "{\"nom\":\"phaggata32\",\"poids\":44,\"valeur\":180},\n",
    "{\"nom\":\"ptrobridge33\",\"poids\":77,\"valeur\":194},\n",
    "{\"nom\":\"dbold34\",\"poids\":30,\"valeur\":144},\n",
    "{\"nom\":\"mgagg35\",\"poids\":84,\"valeur\":131},\n",
    "{\"nom\":\"hellerbeck36\",\"poids\":34,\"valeur\":54},\n",
    "{\"nom\":\"cthredder37\",\"poids\":65,\"valeur\":70},\n",
    "{\"nom\":\"kfilisov38\",\"poids\":99,\"valeur\":174},\n",
    "{\"nom\":\"ktamburo39\",\"poids\":70,\"valeur\":99},\n",
    "{\"nom\":\"ssawer3a\",\"poids\":96,\"valeur\":140},\n",
    "{\"nom\":\"dtribell3b\",\"poids\":71,\"valeur\":153},\n",
    "{\"nom\":\"ahartill3c\",\"poids\":95,\"valeur\":169},\n",
    "{\"nom\":\"aboanas3d\",\"poids\":30,\"valeur\":148},\n",
    "{\"nom\":\"ttreagust3e\",\"poids\":86,\"valeur\":191},\n",
    "{\"nom\":\"abasey3f\",\"poids\":90,\"valeur\":96},\n",
    "{\"nom\":\"ngerraty3g\",\"poids\":42,\"valeur\":174},\n",
    "{\"nom\":\"amunford3h\",\"poids\":31,\"valeur\":93},\n",
    "{\"nom\":\"fmacalaster3i\",\"poids\":34,\"valeur\":139},\n",
    "{\"nom\":\"ahabbin3j\",\"poids\":46,\"valeur\":64},\n",
    "{\"nom\":\"hcurme3k\",\"poids\":64,\"valeur\":154},\n",
    "{\"nom\":\"echeshire3l\",\"poids\":31,\"valeur\":79},\n",
    "{\"nom\":\"aloxton3m\",\"poids\":81,\"valeur\":69},\n",
    "{\"nom\":\"pnewe3n\",\"poids\":33,\"valeur\":143},\n",
    "{\"nom\":\"cbonniface3o\",\"poids\":68,\"valeur\":94},\n",
    "{\"nom\":\"ebaynard3p\",\"poids\":86,\"valeur\":126},\n",
    "{\"nom\":\"jketts3q\",\"poids\":59,\"valeur\":155},\n",
    "{\"nom\":\"tpattillo3r\",\"poids\":85,\"valeur\":46},\n",
    "{\"nom\":\"llindro3s\",\"poids\":56,\"valeur\":129},\n",
    "{\"nom\":\"bholton3t\",\"poids\":96,\"valeur\":158},\n",
    "{\"nom\":\"rcahen3u\",\"poids\":81,\"valeur\":88},\n",
    "{\"nom\":\"kchave3v\",\"poids\":59,\"valeur\":104},\n",
    "{\"nom\":\"cwymer3w\",\"poids\":59,\"valeur\":141},\n",
    "{\"nom\":\"jemloch3x\",\"poids\":65,\"valeur\":156},\n",
    "{\"nom\":\"mferrero3y\",\"poids\":52,\"valeur\":184},\n",
    "{\"nom\":\"tcallan3z\",\"poids\":45,\"valeur\":93},\n",
    "{\"nom\":\"ccodlin40\",\"poids\":32,\"valeur\":45},\n",
    "{\"nom\":\"gpaxeford41\",\"poids\":75,\"valeur\":182},\n",
    "{\"nom\":\"apawlicki42\",\"poids\":32,\"valeur\":96},\n",
    "{\"nom\":\"vhardisty43\",\"poids\":51,\"valeur\":96},\n",
    "{\"nom\":\"jlobb44\",\"poids\":91,\"valeur\":140},\n",
    "{\"nom\":\"spaolacci45\",\"poids\":98,\"valeur\":121},\n",
    "{\"nom\":\"obullivent46\",\"poids\":100,\"valeur\":138},\n",
    "{\"nom\":\"tpatek47\",\"poids\":47,\"valeur\":162},\n",
    "{\"nom\":\"vhully48\",\"poids\":56,\"valeur\":108},\n",
    "{\"nom\":\"nweekland49\",\"poids\":84,\"valeur\":191},\n",
    "{\"nom\":\"smcclelland4a\",\"poids\":66,\"valeur\":185},\n",
    "{\"nom\":\"lheadey4b\",\"poids\":38,\"valeur\":153},\n",
    "{\"nom\":\"ebrumby4c\",\"poids\":71,\"valeur\":118},\n",
    "{\"nom\":\"ebelmont4d\",\"poids\":85,\"valeur\":117},\n",
    "{\"nom\":\"nmcdyer4e\",\"poids\":80,\"valeur\":189},\n",
    "{\"nom\":\"tdelcastel4f\",\"poids\":46,\"valeur\":194},\n",
    "{\"nom\":\"ganlay4g\",\"poids\":90,\"valeur\":191},\n",
    "{\"nom\":\"jspraberry4h\",\"poids\":63,\"valeur\":197},\n",
    "{\"nom\":\"cemps4i\",\"poids\":100,\"valeur\":52},\n",
    "{\"nom\":\"jsalvin4j\",\"poids\":67,\"valeur\":139},\n",
    "{\"nom\":\"mallden4k\",\"poids\":100,\"valeur\":132},\n",
    "{\"nom\":\"wwillcocks4l\",\"poids\":93,\"valeur\":159},\n",
    "{\"nom\":\"caspey4m\",\"poids\":86,\"valeur\":47},\n",
    "{\"nom\":\"sluto4n\",\"poids\":42,\"valeur\":150},\n",
    "{\"nom\":\"mwicher4o\",\"poids\":67,\"valeur\":94},\n",
    "{\"nom\":\"hbrosenius4p\",\"poids\":98,\"valeur\":82},\n",
    "{\"nom\":\"twhoston4q\",\"poids\":100,\"valeur\":150},\n",
    "{\"nom\":\"ptaks4r\",\"poids\":69,\"valeur\":192},\n",
    "{\"nom\":\"mjanew4s\",\"poids\":54,\"valeur\":67},\n",
    "{\"nom\":\"vbeggan4t\",\"poids\":94,\"valeur\":146},\n",
    "{\"nom\":\"bnewns4u\",\"poids\":72,\"valeur\":161},\n",
    "{\"nom\":\"aandresen4v\",\"poids\":79,\"valeur\":57},\n",
    "{\"nom\":\"epearn4w\",\"poids\":84,\"valeur\":121},\n",
    "{\"nom\":\"gpointing4x\",\"poids\":33,\"valeur\":118},\n",
    "{\"nom\":\"kgradon4y\",\"poids\":98,\"valeur\":65},\n",
    "{\"nom\":\"dstrelitz4z\",\"poids\":93,\"valeur\":164},\n",
    "{\"nom\":\"vtreacher50\",\"poids\":69,\"valeur\":193},\n",
    "{\"nom\":\"vbartkowiak51\",\"poids\":92,\"valeur\":139},\n",
    "{\"nom\":\"clagden52\",\"poids\":59,\"valeur\":138},\n",
    "{\"nom\":\"htrace53\",\"poids\":44,\"valeur\":53},\n",
    "{\"nom\":\"ocopsey54\",\"poids\":49,\"valeur\":57},\n",
    "{\"nom\":\"lspary55\",\"poids\":61,\"valeur\":142},\n",
    "{\"nom\":\"efantonetti56\",\"poids\":82,\"valeur\":103},\n",
    "{\"nom\":\"crouchy57\",\"poids\":55,\"valeur\":121},\n",
    "{\"nom\":\"ibentje58\",\"poids\":32,\"valeur\":175},\n",
    "{\"nom\":\"ccharity59\",\"poids\":86,\"valeur\":102},\n",
    "{\"nom\":\"ckhomich5a\",\"poids\":92,\"valeur\":160},\n",
    "{\"nom\":\"lbangs5b\",\"poids\":93,\"valeur\":98},\n",
    "{\"nom\":\"tscotsbrook5c\",\"poids\":74,\"valeur\":91},\n",
    "{\"nom\":\"mknutton5d\",\"poids\":62,\"valeur\":153},\n",
    "{\"nom\":\"etimperley5e\",\"poids\":39,\"valeur\":49},\n",
    "{\"nom\":\"cfoord5f\",\"poids\":52,\"valeur\":181},\n",
    "{\"nom\":\"hkorda5g\",\"poids\":96,\"valeur\":175},\n",
    "{\"nom\":\"jgoor5h\",\"poids\":74,\"valeur\":124},\n",
    "{\"nom\":\"cmaffey5i\",\"poids\":90,\"valeur\":157},\n",
    "{\"nom\":\"sfuzzard5j\",\"poids\":69,\"valeur\":49},\n",
    "{\"nom\":\"mbrickdale5k\",\"poids\":72,\"valeur\":85},\n",
    "{\"nom\":\"bphipp5l\",\"poids\":44,\"valeur\":82},\n",
    "{\"nom\":\"kblaxeland5m\",\"poids\":64,\"valeur\":50},\n",
    "{\"nom\":\"cginnane5n\",\"poids\":78,\"valeur\":136},\n",
    "{\"nom\":\"jteesdale5o\",\"poids\":96,\"valeur\":99},\n",
    "{\"nom\":\"tdyshart5p\",\"poids\":86,\"valeur\":198},\n",
    "{\"nom\":\"wlauritzen5q\",\"poids\":66,\"valeur\":115},\n",
    "{\"nom\":\"dnorthall5r\",\"poids\":67,\"valeur\":108},\n",
    "{\"nom\":\"kturfes5s\",\"poids\":59,\"valeur\":114},\n",
    "{\"nom\":\"kdingate5t\",\"poids\":70,\"valeur\":116},\n",
    "{\"nom\":\"coliff5u\",\"poids\":48,\"valeur\":169},\n",
    "{\"nom\":\"lgarment5v\",\"poids\":75,\"valeur\":177},\n",
    "{\"nom\":\"mshevlin5w\",\"poids\":45,\"valeur\":175},\n",
    "{\"nom\":\"pwatkins5x\",\"poids\":74,\"valeur\":113},\n",
    "{\"nom\":\"dbraithwait5y\",\"poids\":57,\"valeur\":100},\n",
    "{\"nom\":\"gduckit5z\",\"poids\":67,\"valeur\":87},\n",
    "{\"nom\":\"hwillcot60\",\"poids\":72,\"valeur\":139},\n",
    "{\"nom\":\"aofergus61\",\"poids\":76,\"valeur\":145},\n",
    "{\"nom\":\"tkeasey62\",\"poids\":61,\"valeur\":172},\n",
    "{\"nom\":\"ebrookesbie63\",\"poids\":39,\"valeur\":191},\n",
    "{\"nom\":\"atilby64\",\"poids\":36,\"valeur\":82},\n",
    "{\"nom\":\"barne65\",\"poids\":84,\"valeur\":126},\n",
    "{\"nom\":\"akenchington66\",\"poids\":34,\"valeur\":148},\n",
    "{\"nom\":\"jkilcullen67\",\"poids\":84,\"valeur\":72},\n",
    "{\"nom\":\"dgauntlett68\",\"poids\":53,\"valeur\":161},\n",
    "{\"nom\":\"tdaubeny69\",\"poids\":46,\"valeur\":69},\n",
    "{\"nom\":\"ejaniszewski6a\",\"poids\":48,\"valeur\":171},\n",
    "{\"nom\":\"sdunthorn6b\",\"poids\":48,\"valeur\":161},\n",
    "{\"nom\":\"czmitrichenko6c\",\"poids\":62,\"valeur\":110},\n",
    "{\"nom\":\"anutbrown6d\",\"poids\":78,\"valeur\":82},\n",
    "{\"nom\":\"sspinige6e\",\"poids\":89,\"valeur\":157},\n",
    "{\"nom\":\"soutibridge6f\",\"poids\":69,\"valeur\":198},\n",
    "{\"nom\":\"lswindlehurst6g\",\"poids\":90,\"valeur\":49},\n",
    "{\"nom\":\"rblague6h\",\"poids\":82,\"valeur\":71},\n",
    "{\"nom\":\"mlefevre6i\",\"poids\":32,\"valeur\":75},\n",
    "{\"nom\":\"cbeamand6j\",\"poids\":41,\"valeur\":176},\n",
    "{\"nom\":\"vcole6k\",\"poids\":38,\"valeur\":76},\n",
    "{\"nom\":\"sduckworth6l\",\"poids\":57,\"valeur\":149},\n",
    "{\"nom\":\"wmuehler6m\",\"poids\":40,\"valeur\":91},\n",
    "{\"nom\":\"rkeeping6n\",\"poids\":74,\"valeur\":88},\n",
    "{\"nom\":\"dtapping6o\",\"poids\":44,\"valeur\":110},\n",
    "{\"nom\":\"mtinniswood6p\",\"poids\":59,\"valeur\":64},\n",
    "{\"nom\":\"tmacgow6q\",\"poids\":91,\"valeur\":168},\n",
    "{\"nom\":\"dbodd6r\",\"poids\":81,\"valeur\":70},\n",
    "{\"nom\":\"kloveguard6s\",\"poids\":31,\"valeur\":183},\n",
    "{\"nom\":\"rhuffey6t\",\"poids\":63,\"valeur\":103},\n",
    "{\"nom\":\"hmacallan6u\",\"poids\":95,\"valeur\":88},\n",
    "{\"nom\":\"ktenbroek6v\",\"poids\":69,\"valeur\":130},\n",
    "{\"nom\":\"jcharette6w\",\"poids\":72,\"valeur\":171},\n",
    "{\"nom\":\"zmcimmie6x\",\"poids\":55,\"valeur\":98},\n",
    "{\"nom\":\"wbarents6y\",\"poids\":46,\"valeur\":114},\n",
    "{\"nom\":\"mwilder6z\",\"poids\":90,\"valeur\":156},\n",
    "{\"nom\":\"afilip70\",\"poids\":93,\"valeur\":172},\n",
    "{\"nom\":\"bsouthcott71\",\"poids\":55,\"valeur\":127},\n",
    "{\"nom\":\"pstedmond72\",\"poids\":88,\"valeur\":181},\n",
    "{\"nom\":\"gleedal73\",\"poids\":45,\"valeur\":162},\n",
    "{\"nom\":\"jmuehle74\",\"poids\":60,\"valeur\":57},\n",
    "{\"nom\":\"fpenhaligon75\",\"poids\":68,\"valeur\":130},\n",
    "{\"nom\":\"kconaghy76\",\"poids\":74,\"valeur\":118},\n",
    "{\"nom\":\"bproschke77\",\"poids\":83,\"valeur\":85},\n",
    "{\"nom\":\"blope78\",\"poids\":97,\"valeur\":52},\n",
    "{\"nom\":\"dbrunstan79\",\"poids\":55,\"valeur\":77},\n",
    "{\"nom\":\"htolley7a\",\"poids\":45,\"valeur\":73},\n",
    "{\"nom\":\"speto7b\",\"poids\":43,\"valeur\":111},\n",
    "{\"nom\":\"oinnocenti7c\",\"poids\":37,\"valeur\":200},\n",
    "{\"nom\":\"blaffranconi7d\",\"poids\":66,\"valeur\":127},\n",
    "{\"nom\":\"ahaslen7e\",\"poids\":58,\"valeur\":176},\n",
    "{\"nom\":\"hmazey7f\",\"poids\":50,\"valeur\":189},\n",
    "{\"nom\":\"rbewlie7g\",\"poids\":93,\"valeur\":114},\n",
    "{\"nom\":\"bpiccop7h\",\"poids\":41,\"valeur\":146},\n",
    "{\"nom\":\"egisborne7i\",\"poids\":48,\"valeur\":76},\n",
    "{\"nom\":\"dwye7j\",\"poids\":34,\"valeur\":159},\n",
    "{\"nom\":\"kfarnworth7k\",\"poids\":31,\"valeur\":166},\n",
    "{\"nom\":\"bbale7l\",\"poids\":50,\"valeur\":146},\n",
    "{\"nom\":\"ubecom7m\",\"poids\":59,\"valeur\":53},\n",
    "{\"nom\":\"lreedy7n\",\"poids\":97,\"valeur\":137},\n",
    "{\"nom\":\"tvalenta7o\",\"poids\":79,\"valeur\":141},\n",
    "{\"nom\":\"gfulford7p\",\"poids\":48,\"valeur\":104},\n",
    "{\"nom\":\"jcheves7q\",\"poids\":37,\"valeur\":145},\n",
    "{\"nom\":\"ajakeman7r\",\"poids\":41,\"valeur\":58},\n",
    "{\"nom\":\"olaffling7s\",\"poids\":60,\"valeur\":62},\n",
    "{\"nom\":\"sedwicker7t\",\"poids\":100,\"valeur\":155},\n",
    "{\"nom\":\"wmccaffrey7u\",\"poids\":56,\"valeur\":98},\n",
    "{\"nom\":\"mvogel7v\",\"poids\":31,\"valeur\":90},\n",
    "{\"nom\":\"ystolz7w\",\"poids\":48,\"valeur\":85},\n",
    "{\"nom\":\"usmallacombe7x\",\"poids\":75,\"valeur\":162},\n",
    "{\"nom\":\"gmattiuzzi7y\",\"poids\":78,\"valeur\":95},\n",
    "{\"nom\":\"pempleton7z\",\"poids\":83,\"valeur\":51},\n",
    "{\"nom\":\"psamter80\",\"poids\":89,\"valeur\":189},\n",
    "{\"nom\":\"bcotesford81\",\"poids\":78,\"valeur\":144},\n",
    "{\"nom\":\"gjura82\",\"poids\":61,\"valeur\":148},\n",
    "{\"nom\":\"aspinks83\",\"poids\":53,\"valeur\":152},\n",
    "{\"nom\":\"mofeeny84\",\"poids\":98,\"valeur\":107},\n",
    "{\"nom\":\"lfautly85\",\"poids\":61,\"valeur\":170},\n",
    "{\"nom\":\"cfrostdick86\",\"poids\":34,\"valeur\":147},\n",
    "{\"nom\":\"dmcwaters87\",\"poids\":93,\"valeur\":47},\n",
    "{\"nom\":\"kbruton88\",\"poids\":96,\"valeur\":168},\n",
    "{\"nom\":\"alimbert89\",\"poids\":52,\"valeur\":105},\n",
    "{\"nom\":\"acapelle8a\",\"poids\":55,\"valeur\":165},\n",
    "{\"nom\":\"mtrenholm8b\",\"poids\":35,\"valeur\":94},\n",
    "{\"nom\":\"wreck8c\",\"poids\":88,\"valeur\":102},\n",
    "{\"nom\":\"ldelacour8d\",\"poids\":41,\"valeur\":48},\n",
    "{\"nom\":\"kstubs8e\",\"poids\":55,\"valeur\":170},\n",
    "{\"nom\":\"bbilby8f\",\"poids\":99,\"valeur\":145},\n",
    "{\"nom\":\"lsimmgen8g\",\"poids\":59,\"valeur\":63},\n",
    "{\"nom\":\"dsarfatti8h\",\"poids\":56,\"valeur\":81},\n",
    "{\"nom\":\"jtees8i\",\"poids\":59,\"valeur\":171},\n",
    "{\"nom\":\"pyurasov8j\",\"poids\":36,\"valeur\":152},\n",
    "{\"nom\":\"dayce8k\",\"poids\":68,\"valeur\":132},\n",
    "{\"nom\":\"bokenden8l\",\"poids\":71,\"valeur\":149},\n",
    "{\"nom\":\"clocal8m\",\"poids\":39,\"valeur\":188},\n",
    "{\"nom\":\"rdeards8n\",\"poids\":42,\"valeur\":110},\n",
    "{\"nom\":\"dsawley8o\",\"poids\":63,\"valeur\":121},\n",
    "{\"nom\":\"rscutts8p\",\"poids\":34,\"valeur\":70},\n",
    "{\"nom\":\"rdumbell8q\",\"poids\":71,\"valeur\":161},\n",
    "{\"nom\":\"hwinterscale8r\",\"poids\":91,\"valeur\":103},\n",
    "{\"nom\":\"gduggan8s\",\"poids\":97,\"valeur\":151},\n",
    "{\"nom\":\"kshooter8t\",\"poids\":65,\"valeur\":191},\n",
    "{\"nom\":\"agilardone8u\",\"poids\":70,\"valeur\":70},\n",
    "{\"nom\":\"fhedlestone8v\",\"poids\":85,\"valeur\":168},\n",
    "{\"nom\":\"wrunnalls8w\",\"poids\":53,\"valeur\":149},\n",
    "{\"nom\":\"esommerton8x\",\"poids\":92,\"valeur\":122},\n",
    "{\"nom\":\"mkarpman8y\",\"poids\":46,\"valeur\":84},\n",
    "{\"nom\":\"sslafford8z\",\"poids\":51,\"valeur\":158},\n",
    "{\"nom\":\"aghio90\",\"poids\":75,\"valeur\":171},\n",
    "{\"nom\":\"bgerriessen91\",\"poids\":74,\"valeur\":163},\n",
    "{\"nom\":\"gswarbrigg92\",\"poids\":94,\"valeur\":197},\n",
    "{\"nom\":\"lskentelbury93\",\"poids\":51,\"valeur\":84},\n",
    "{\"nom\":\"akarlolak94\",\"poids\":53,\"valeur\":99},\n",
    "{\"nom\":\"bcastells95\",\"poids\":85,\"valeur\":156},\n",
    "{\"nom\":\"beasbie96\",\"poids\":66,\"valeur\":123},\n",
    "{\"nom\":\"kvalentinetti97\",\"poids\":41,\"valeur\":142},\n",
    "{\"nom\":\"rwickrath98\",\"poids\":81,\"valeur\":81},\n",
    "{\"nom\":\"stoyne99\",\"poids\":100,\"valeur\":153},\n",
    "{\"nom\":\"bbodega9a\",\"poids\":67,\"valeur\":136},\n",
    "{\"nom\":\"dlarmuth9b\",\"poids\":72,\"valeur\":75},\n",
    "{\"nom\":\"mfyers9c\",\"poids\":77,\"valeur\":93},\n",
    "{\"nom\":\"mbellhouse9d\",\"poids\":83,\"valeur\":115},\n",
    "{\"nom\":\"cmaclardie9e\",\"poids\":40,\"valeur\":65},\n",
    "{\"nom\":\"tmorales9f\",\"poids\":92,\"valeur\":198},\n",
    "{\"nom\":\"ihucquart9g\",\"poids\":49,\"valeur\":137},\n",
    "{\"nom\":\"lsearchfield9h\",\"poids\":93,\"valeur\":122},\n",
    "{\"nom\":\"rduetsche9i\",\"poids\":68,\"valeur\":117},\n",
    "{\"nom\":\"wforrester9j\",\"poids\":38,\"valeur\":140},\n",
    "{\"nom\":\"emartusewicz9k\",\"poids\":73,\"valeur\":64},\n",
    "{\"nom\":\"mmacanulty9l\",\"poids\":96,\"valeur\":69},\n",
    "{\"nom\":\"lgenese9m\",\"poids\":41,\"valeur\":119},\n",
    "{\"nom\":\"pwatt9n\",\"poids\":82,\"valeur\":192},\n",
    "{\"nom\":\"kjosum9o\",\"poids\":90,\"valeur\":188},\n",
    "{\"nom\":\"bcastagneri9p\",\"poids\":92,\"valeur\":57},\n",
    "{\"nom\":\"hrafter9q\",\"poids\":70,\"valeur\":196},\n",
    "{\"nom\":\"bfrary9r\",\"poids\":57,\"valeur\":45},\n",
    "{\"nom\":\"rbridgstock9s\",\"poids\":96,\"valeur\":100},\n",
    "{\"nom\":\"caxon9t\",\"poids\":49,\"valeur\":195},\n",
    "{\"nom\":\"dtillett9u\",\"poids\":83,\"valeur\":52},\n",
    "{\"nom\":\"rwaghorn9v\",\"poids\":63,\"valeur\":86},\n",
    "{\"nom\":\"gpolendine9w\",\"poids\":47,\"valeur\":88},\n",
    "{\"nom\":\"jtredwell9x\",\"poids\":94,\"valeur\":82},\n",
    "{\"nom\":\"adebellis9y\",\"poids\":61,\"valeur\":98},\n",
    "{\"nom\":\"mkaes9z\",\"poids\":84,\"valeur\":56},\n",
    "{\"nom\":\"hdeningtona0\",\"poids\":80,\"valeur\":82},\n",
    "{\"nom\":\"msturgesa1\",\"poids\":82,\"valeur\":195},\n",
    "{\"nom\":\"bsteelea2\",\"poids\":36,\"valeur\":166},\n",
    "{\"nom\":\"ctwinbornea3\",\"poids\":64,\"valeur\":180},\n",
    "{\"nom\":\"gtissingtona4\",\"poids\":53,\"valeur\":166},\n",
    "{\"nom\":\"dlangelaana5\",\"poids\":58,\"valeur\":134},\n",
    "{\"nom\":\"selgooda6\",\"poids\":32,\"valeur\":175},\n",
    "{\"nom\":\"cgallagera7\",\"poids\":41,\"valeur\":116},\n",
    "{\"nom\":\"ssamesa8\",\"poids\":84,\"valeur\":165},\n",
    "{\"nom\":\"dedgleya9\",\"poids\":44,\"valeur\":114},\n",
    "{\"nom\":\"mlauaa\",\"poids\":44,\"valeur\":91},\n",
    "{\"nom\":\"jlarwayab\",\"poids\":50,\"valeur\":131},\n",
    "{\"nom\":\"esagarac\",\"poids\":53,\"valeur\":100},\n",
    "{\"nom\":\"mpresseyad\",\"poids\":52,\"valeur\":59},\n",
    "{\"nom\":\"mdoolanae\",\"poids\":35,\"valeur\":161},\n",
    "{\"nom\":\"jkleslaf\",\"poids\":88,\"valeur\":135},\n",
    "{\"nom\":\"kkeerag\",\"poids\":72,\"valeur\":184},\n",
    "{\"nom\":\"hkoppsah\",\"poids\":86,\"valeur\":132},\n",
    "{\"nom\":\"pstuerai\",\"poids\":57,\"valeur\":118},\n",
    "{\"nom\":\"wyeomansaj\",\"poids\":59,\"valeur\":69},\n",
    "{\"nom\":\"shunnak\",\"poids\":39,\"valeur\":150},\n",
    "{\"nom\":\"bwynrahameal\",\"poids\":66,\"valeur\":124},\n",
    "{\"nom\":\"mdetoileam\",\"poids\":82,\"valeur\":137},\n",
    "{\"nom\":\"cdarlingtonan\",\"poids\":91,\"valeur\":143},\n",
    "{\"nom\":\"charcourtao\",\"poids\":76,\"valeur\":110},\n",
    "{\"nom\":\"acondyap\",\"poids\":47,\"valeur\":153},\n",
    "{\"nom\":\"nblakemoreaq\",\"poids\":54,\"valeur\":124},\n",
    "{\"nom\":\"gmcnabar\",\"poids\":67,\"valeur\":123},\n",
    "{\"nom\":\"hbatrickas\",\"poids\":80,\"valeur\":193},\n",
    "{\"nom\":\"chubatschat\",\"poids\":79,\"valeur\":154},\n",
    "{\"nom\":\"ebarkeau\",\"poids\":49,\"valeur\":129},\n",
    "{\"nom\":\"elouchav\",\"poids\":94,\"valeur\":190},\n",
    "{\"nom\":\"rlaurentinaw\",\"poids\":39,\"valeur\":131},\n",
    "{\"nom\":\"ostansallax\",\"poids\":71,\"valeur\":77},\n",
    "{\"nom\":\"mchettleay\",\"poids\":78,\"valeur\":65},\n",
    "{\"nom\":\"rmccromleyaz\",\"poids\":65,\"valeur\":92},\n",
    "{\"nom\":\"sledwardb0\",\"poids\":80,\"valeur\":122},\n",
    "{\"nom\":\"egarwillb1\",\"poids\":99,\"valeur\":169},\n",
    "{\"nom\":\"mshepeardb2\",\"poids\":79,\"valeur\":180},\n",
    "{\"nom\":\"jdaveranb3\",\"poids\":87,\"valeur\":83}]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Il y a 400 joueurs dans  la liste initiale\n",
      "{'nom': 'ccheyenne22', 'poids': 33, 'valeur': 200} rapport valeur / coût =  6.0606060606060606\n",
      "{'nom': 'jcanada29', 'poids': 31, 'valeur': 187} rapport valeur / coût =  6.032258064516129\n",
      "{'nom': 'kloveguard6s', 'poids': 31, 'valeur': 183} rapport valeur / coût =  5.903225806451613\n",
      "{'nom': 'vhallagan28', 'poids': 36, 'valeur': 198} rapport valeur / coût =  5.5\n",
      "{'nom': 'ibentje58', 'poids': 32, 'valeur': 175} rapport valeur / coût =  5.46875\n",
      "{'nom': 'selgooda6', 'poids': 32, 'valeur': 175} rapport valeur / coût =  5.46875\n",
      "{'nom': 'oinnocenti7c', 'poids': 37, 'valeur': 200} rapport valeur / coût =  5.405405405405405\n",
      "{'nom': 'kfarnworth7k', 'poids': 31, 'valeur': 166} rapport valeur / coût =  5.354838709677419\n",
      "{'nom': 'jcordingly2i', 'poids': 38, 'valeur': 192} rapport valeur / coût =  5.052631578947368\n",
      "{'nom': 'aboanas3d', 'poids': 30, 'valeur': 148} rapport valeur / coût =  4.933333333333334\n",
      "{'nom': 'ebrookesbie63', 'poids': 39, 'valeur': 191} rapport valeur / coût =  4.897435897435898\n",
      "{'nom': 'cwillettso', 'poids': 36, 'valeur': 176} rapport valeur / coût =  4.888888888888889\n",
      "{'nom': 'clocal8m', 'poids': 39, 'valeur': 188} rapport valeur / coût =  4.82051282051282\n",
      "{'nom': 'mjizhaki2t', 'poids': 31, 'valeur': 149} rapport valeur / coût =  4.806451612903226\n",
      "Poids total des objets sélectionnés 476\n"
     ]
    }
   ],
   "source": [
    "nb_joueurs = len(table_3)\n",
    "print(\"Il y a\",nb_joueurs,\"joueurs dans  la liste initiale\")\n",
    "affiche_resultat_glouton( selectionner(table_3, 500) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Avec 400 joueurs...\n",
      " ...il y a  64034522846623895262347970319503005850702583026002959458684445942802397169186831436278478647463264676294350575035856810848298162883517435228961988646802997937341654150838162426461942352307046244325015114448670890662773914918117331955996440709549671345290477020322434911210797593280795101545372667251627877890009349763765710326350331533965349868386831339352024373788157786791506311858702618270169819740062983025308591298346162272304558339520759611505302236086810433297255194852674432232438669948422404232599805551610635942376961399231917134063858996537970147827206606320217379472010321356624613809077942304597360699567595836096158715129913822286578579549361617654480453222007825818400848436415591229454275384803558374518022675900061399560145595206127211192918105032491008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000  permutations possibles\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "print(\"Avec\",nb_joueurs,\"joueurs...\\n ...il y a \",math.factorial(nb_joueurs),\" permutations possibles\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}