Différences

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

--- itc:tps:tp5:exercice2 [2022/01/17 19:51] – goupillwiki
+++ itc:tps:tp5:exercice2 [2022/01/18 13:46] (Version actuelle) – goupillwiki
@@ Ligne 29: / Ligne 29: @@
 ^ indice ^ nom     ^ poids ^ valeur ^
-| 0      | collier | 1     | 1000   |
+| 0      | collier | 1     | 600    |
-| 1      | écran   | 10    | 200    |
-| 1      | écran   | 10    | 200    |
-| 1      | écran   | 10    | 200    |
 | 1      | écran   | 10    | 200    |
+| 2      | globe   | 7     | 120    |
+| 3      | lampe   | 5     | 40     |
+| 4      | fleur   | 4     | 10     |
+| 5      | écrin   | 2     | 300    |
+| 6      | coffre  | 25    | 1500   |
+| 7      | livre   | 5     | 30     |
+| 8      | caisse  | 12    | 100    |
+| 9      | enclume | 20    | 20     |
+| 10     | statuette | 6     | 250  |
+| 11     | livre rare | 5     | 220 |
-===== Implémentation =====
+Dans le programme on disposera d'une liste ayant cette forme :
+<code python>
+liste = [
+  {"nom":"collier", "poids":1, "valeur":600},
+  {"nom":"écran", "poids":10, "valeur":200},
+  {"nom":"globe", "poids":7, "valeur":120},
+  {"nom":"lampe", "poids":5, "valeur":40},
+  {"nom":"fleur", "poids":4, "valeur":10},
+  {"nom":"écrin", "poids":3, "valeur":300},
+  {"nom":"coffre", "poids":25, "valeur":1500},
+  {"nom":"livre", "poids":5, "valeur":30},
+  {"nom":"caisse", "poids":12, "valeur":100},
+  {"nom":"enclume", "poids":20, "valeur":20},
+  {"nom":"statuette", "poids":6, "valeur":250},
+  {"nom":"livre rare", "poids":5, "valeur":220}
+]
+</code>
+===== Rappel sur le tri =====
+Les items du tableau, il faut préciser par rapport à quelle mesure on doit les ordonner. On doit donc indiquer au tri une fonction $item \mapsto evaluation$.
+Par exemple si on veut trier par valeur croissante, il nous faut : $item \mapsto valeur(item)$. On peut définir cette fonction de façon classique :
+<code python>
+def critere_valeur(item):
+    return item["valeur"]
+</code>
+Puis le tri sera :
+<code python>
+liste.sort(key = critere_tri)
+</code>
+et si on veut un ordre décroissant, il suffit de le préciser :
+<code python>
+liste.sort(key = critere_tri, reverse = True)
+</code>
+On peut aussi (ce sera mieux ici) modifier le critère : si on veut trier par valeur décroissante, il suffit de choisir :
+<code python>
+def critere_valeur(item):
+    return -item["valeur"]
+</code>
+Le ''-'' change naturellement l'ordre de sorte que ''liste.sort(key = critere_tri)'' triera par valeur décroissante.
+===== Implémentation =====
-Pour l’écriture des fonctions, on suppose que l’on dispose d’une liste L = [[1, p1, v1], ..., [n, pn, vn]]
+  - On a besoin de trier le tableau suivant un certain critère. Définissez une fonction critère pour les 3 cas :
-de longueur n et d’un poids maximal P .
+    * par valeur décroissante,
-Pour une exploration numérique ou faire un test, on prendra
+    * par poids croissant,
-L = [[1, 14, 126], [2, 2, 32], [3, 5, 20], [4, 1, 5], [5, 6, 18], [6, 8, 80]] et P = 15.
+    * par rapport valeur/poids décroissante.
-On aura besoin de classer nos objets par poids croissants, puis par valeurs décroissantes et enfin
+  - Voici l'algorithme glouton pour le sac à dos :<code lang-none>
-par rapports ri décroissants. Nous avons déjà vu des algorithmes de tri et nous en verrons d’autres
+FONCTION sac_a_dos
-encore plus tard. Pour l’instant, comme ce n’est pas le sujet ici, on utilise la fonction sorted de
+ENTRÉES
-Python qui permet de trier une liste en précisant la clé du tri selon la syntaxe suivante.
+  liste: tableau contant la liste des objets avec leur nom, poids et valeur
-sorted(L, key = lambda x : x[i]) qui trie la liste des x suivant l’ordre croissant des x[i] et
+  P: poids maximum que peut emporter le sac
-sorted(L, key = lambda x : x[i], reverse = True) qui fait la même chose dans l’ordre dé-
+  critere: la fonction définissant le critère de tri
-croissant.
+SORTIE
-Ainsi pour la liste L donnée ci-dessus, l’instruction T = sorted(L, key = lambda x : x[1])
+  un tuple contenant :
-crée une variable T qui est la liste L classée par poids croissants et l’instruction U = sorted(L, key
+    la liste des noms,
-= lambda x : x[2], reverse = True) crée une variable U qui est la liste L classée par valeurs
+    le poids du sac,
-décroissantes
+    la valeur du sac
+DÉBUT
+  initialiser contenu à vide, poids et valeur à 0
+  trier la liste suivant le critère retenu
+  POUR CHAQUE item DE liste FAIRE
+      SI le sac a assez de place pour cet item ALORS
+          ajouter le nom de cet item au contenu
+          ajouter le poids et la valeur de cet item à poids et valeur
+      FIN
+  FIN
+  RENVOYER contenu, poids, valeur
+</code>
+  - Testez la fonction avec les 3 critères en prenant ''P = 20''.
+  - Comme dans ce cas le tableau est de petite taille, cherchez le meilleur sac en force brute (c'est à dire en essayant tous les cas) et comparez avec la réponse obtenue avec l'algorithme glouton.
+  - comparez la complexité de la recherche brute avec la complexité de l'algorithme glouton.