Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:premiere:sac_a_dos [2021/05/08 18:36] – goupillwiki
+++ nsi:premiere:sac_a_dos [2022/05/09 20:00] (Version actuelle) – goupillwiki
@@ Ligne 5: / Ligne 5: @@
 Il s'agit d'un problème classique d'algorithmique.
-  * On dispose d'un sac de capacité C en kg,
+C'est le problème du **cambrioleur** : Le cambrioleur doit choisir rapidement quels objets il emporte. Il veut emporter un maximum de valeur mais il doit les mettre dans son sac dont la capacité est limitée.
+Plus formellement :
+  * On dispose d'un sac de capacité C,
   * d'un assortiment d'objets ayant tous un poids et une valeur.
   * On cherche à placer des objets dans le sac en respectant la contrainte de capacité et en maximisant la valeur totale du contenu du sac.
@@ Ligne 23: / Ligne 27: @@
 L'algorithme glouton donne une réponse pas forcément optimale au problème posé mais il est simple :
-  - On trie le tableau selon un critère,
+  - on trie le tableau selon un critère,
-  - puis on remplit le sac en prenant les objets dans l'ordre.
+  - on remplit le sac en prenant les objets dans l'ordre.
-== Valeur décroissante ==
+=== Valeur décroissante ===
 Par exemple, trions le tableau par valeur décroissante.
@@ Ligne 45: / Ligne 49: @@
 Le sac contiendra A et D totalisant une valeur de 131.
-== Poids décroissant ==
+=== Poids croissant ===
 C'est un autre choix possible. Il aboutira à un contenu de sac différent.
@@ Ligne 76: / Ligne 80: @@
 ===== Implémentation =====
-== Les objets ==
+=== Les objets ===
-Les items disponibles seront représentés par des dictionnaires dans un tableau. Par exemple :
+Les items disponibles seront représentés dans un dictionnaire. Par exemple :
 <Code python>
-objets = [
+objets = {
-  { "Nom":"A", "Valeur":126, "Poids":14 },
+  "A": { "valeur":126, "poids":14 },
-  { "Nom":"B", "Valeur":32, "Poids":2 },
+  "B": { "valeur":32, "poids":2 },
-  { "Nom":"C", "Valeur":20, "Poids":5 },
+  "C": { "valeur":20, "poids":5 },
-  { "Nom":"D", "Valeur":5, "Poids":1 },
+  "D": { "valeur":5, "poids":1 },
-  { "Nom":"E", "Valeur":18, "Poids":6 },
+  "E": { "valeur":18, "poids":6 },
-  { "Nom":"F", "Valeur":80, "Poids":8 }
+  "F": { "valeur":80, "poids":8 }
-]
+}
 </Code>
-== Sac ==
+=== Sac ===
 Le contenu du sac sera lui aussi représenté par un tableau. Par exemple :
 <Code python>
-sac = [
+sac = ["A", "D"]
-  { "Nom":"A", "Valeur":126, "Poids":14 },
-  { "Nom":"D", "Valeur":5, "Poids":1 }
-]
 </Code>
-== fonctions utiles ==
+=== fonctions utiles ===
 Nous avons besoin des fonctions suivantes :
-  - ajouter un objet dans un sac si c'est possible,
   - trier les objets dans un ordre défini,
+  - calculer le poids total d'un sac,
   - calculer la valeur d'un sac
+  - tester si on peut ajouter un objet dans un sac,
+  - ajouter un objet dans un sac
-Voici un modèle à compléter :
+Voici un modèle **à compléter** puis **à exécuter** :
-<file python sacados.py>
+<code python>
-'''
+# sacados.py
-Algorithme glouton : problème du sac à dos
+# la dictionnaire objets contenant les objets sera une variable globale.
-'''
-def ajouter_objet_dans_sac(sac, objet):
+def tri(critere):
     '''
-    sac: sac dans lequel mettre l'objet
+    critere: fonction qui pour nom d'objet donné renvoie sa valeur dans le tri
-    objet: objet à mettre dans le sac
+        exemple : si on tri par valeur décroissante, critere(nom) doit renvoyer
-    ajoute l'objet dans le sac si c'est possible.
+        la valeur de l'objet
-    renvoie True en cas de succès, False sinon
+    la fonction renvoie un tableau avec les noms, par critère décroissant.
+    '''
+    return
+def poids(sac):
+    '''
+    sac: tableau des noms des objets contenus dans le sac
+    renvoie la masse totale contenue dans le sac
+    '''
+    return 0
+def valeur(sac):
+    '''
+    sac: tableau des noms des objets contenus dans le sac
+    renvoie la valeur totale de ce sac.
+    '''
+    return 0
+def rentre_dans_le_sac(nom, sac, C):
+    '''
+    nom: nom de l'objet que l'on souhaite ajouter
+    sac: tableau des noms des objets contenus dans le sac
+    C: Capacité max du sac
+    renvoie True si l'objet peut entrer dans le sac, False sinon
     '''
     return False
-def tri_sac(sac, critere):
+def ajouter_objet_dans_sac(nom, sac):
     '''
-    sac: sac à trier
+    nom: nom de l'objet que l'on souhaite ajouter
-    critere: fonction qui pour un un objet donné renvoie sa valeur dans le tri
+    sac: tableau des noms des objets contenus dans le sac
-      exemple : si on tri par valeur décroissante, critere(objet) doit renvoyer la valeur de l'objet
+    modifie sac en y ajoutant nom
-    trie le sac selon le critère, toujours par ordre décroissant
     '''
     return
-def valeur_sac(sac):
+def glouton(C, critere):
     '''
-    sac: sac dont on veut la valeur
+    C: capacité max du sac
-    renvoie la valeur totale de ce sac.
+    critere: fonction utilisée dans le tri
+    renvoie le sac obtenu par l'algorithme glouton suivant le critère défini
     '''
-    return 0
+    return []
-</file>
+# démonstration
+C = 15
+objets = {
+  "A": { "valeur":126, "poids":14 },
+  "B": { "valeur":32, "poids":2 },
+  "C": { "valeur":20, "poids":5 },
+  "D": { "valeur":5, "poids":1 },
+  "E": { "valeur":18, "poids":6 },
+  "F": { "valeur":80, "poids":8 }
+}
+# exemple de critère
+def critere_valeur(nom):
+    obj = objets[nom]
+    return obj["valeur"]
+sac = glouton(C, critere_valeur)
+print(sac)
+print(valeur(sac))
+</code>
+=== Fonction lambda ===
+En mathématique, une fonction consiste en l'association d'antécédents et d'images. On peut noter par exemple $x \mapsto 3x + 5$ l'idée que chaque nombre $x$ antécédent sera associer à l'image $3x+5$ : 0 est associé à 5 ; 1 est à 8 ; 2 est associé à 11 ; etc.
+Notre fonction ''%%critere_valeur%%'' pourrait ainsi se noter $nom \mapsto objets[nom]['valeur']$. On comprendrait ce que fait cette fonction sans la définir avant et sans lui donner de nom, il suffit de savoir que l'antécédent est ''%%nom%%'' et que l'image est ''%%objets[nom]['valeur']%%''.
+Il existe une notation pour cela en Python :
+<code python>
+lambda nom: objets[nom]['valeur']
+</code>
+C'est une fonction anonyme prenant comme argument (//antécédent//) ''%%nom%%'' et renvoie (//image//) ''%%objets[nom]['Valeur']%%''.
+Alors nous pouvons remplacer :
+<code python>
+# code actuel
+def critere_valeur(nom):
+    return objets[nom]['valeur']
+sac = glouton(objets, critere_valeur)
+# en utilisant lambda
+sac = glouton(objets, lambda nom: objets[nom]['valeur'])
+</code>
+Le résultat est le même.
+=== Autre critères ===
+Exécutez le programme avec d'autres critères :
+  * rapport valeur / poids décroissant,
+  * poids croissant\\ //Il faut trouver une astuce puisque le tri se fait dans l'ordre décroissant du critère fourni !//
+Essayez de le faire en utilisant ''%%lambda%%''.