Différences

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

--- nsi:terminales:sac_a_dos [2023/02/03 11:28] – goupillwiki
+++ nsi:terminales:sac_a_dos [2023/02/03 12:08] (Version actuelle) – goupillwiki
@@ Ligne 5: / Ligne 5: @@
 ===== Qu'est-ce ? =====
-Un problème classique d'algorithmique. On dispose d'un sac de capacité $C$ en kg et 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.
+Un problème classique d'algorithmique. On dispose d'un sac de capacité $C$ et 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.
 <WRAP tip>On peut voir cela comme un problème de cambrioleur : le cambrioleur dispose d'un sac de taille forcément limitée, et se demande ce qu'il a intérêt à voler. On comprend qu'il prendra des bijoux qui sont précieux et peu encombrant. Prendra-t-il une statuette ? un appareil électronique ? Il cherche à emporter le plus de valeur possible mais est limité par son sac.</WRAP>
-**Exemple :** On dispose d'un sac d'une capacité de $C = 15\,kg$ et de la liste d'objets suivants :
+**Exemple :** On dispose d'un sac d'une capacité de $C = 15$ et de la liste d'objets suivants :
-^ Objet ^ Valeur ^ Poids ^
+^ Objet ^ Valeur ^ Encombrement ^
-| A     | 126    | 14    |
+| A     | 126    | 14           |
-| B     | 32     | 2     |
+| B     | 32     | 2            |
-| C     | 20     | 5     |
+| C     | 20     | 5            |
-| D     | 5      | 1     |
+| D     | 5      | 1            |
-| E     | 18     | 6     |
+| E     | 18     | 6            |
-| F     | 80     | 8     |
+| F     | 80     | 8            |
 ===== Vu en première : L'algorithme glouton =====
@@ Ligne 30: / Ligne 30: @@
 Par exemple, si on choisit de trier par **valeur décroissante**, on obtient :
-^ Objet ^ Valeur ^ Poids ^
+^ Objet ^ Valeur ^ Encombrement ^
-| A     | 126    | 14    |
+| A     | 126    | 14           |
-| F     | 80     | 8     |
+| F     | 80     | 8            |
-| B     | 32     | 2     |
+| B     | 32     | 2            |
-| C     | 20     | 5     |
+| C     | 20     | 5            |
-| E     | 18     | 6     |
+| E     | 18     | 6            |
-| D     | 5      | 1     |
+| D     | 5      | 1            |
 Puis on complète le sac :
@@ Ligne 47: / Ligne 47: @@
 == Tri par valeur / poids décroissant ==
-On aurait aussi pu trier par **rapport valeur / poids décroissant**
+On aurait aussi pu trier par **rapport valeur / encombrement décroissant**
-^ Objet ^ Valeur ^ Poids ^ rapport V/P ^
+^ Objet ^ Valeur ^ Encombrement ^ rapport V/E ^
-| B     | 32     | 2     | 16          |
+| B     | 32     | 2            | 16          |
-| F     | 80     | 8     | 10          |
+| F     | 80     | 8            | 10          |
-| A     | 126    | 14    | 9           |
+| A     | 126    | 14           | 9           |
-| D     | 5      | 1     | 5           |
+| D     | 5      | 1            | 5           |
-| C     | 20     | 5     | 4           |
+| C     | 20     | 5            | 4           |
-| E     | 18     | 6     | 3           |
+| E     | 18     | 6            | 3           |
 Dans ce cas on prend B, F, pas A qui ne rentre plus, D, pas C ni E qui ne rentrent plus.
@@ Ligne 67: / Ligne 67: @@
 ==== Principe ====
-L'approche dynamique consiste à étudier des sous-problèmes. Notre problème est constitué d'un sac de capacité $C$ et de 6 objets. On peut noter $sad_{i,c}$ la meilleur réponse  dans le problème de sac à dos avec un sac de capacité $c$ et avec les $i$ premiers objets.
+L'approche dynamique consiste à étudier des sous-problèmes. Notre problème est constitué d'un sac de capacité $C$ et de 6 objets. On peut noter $msad_{i,c}$ la meilleure réponse  dans le problème de sac à dos avec un sac de capacité $c$ et avec les $i$ premiers objets.
 <wrap important>Attention, a bien distinguer $c$ et $C$ !</wrap>
-Par exemple $sad_{2,8}$ consiste à résoudre le cas d'un sac de capacité 8 kg avec seulement les deux objets :
+Par exemple $msad_{2,8}$ consiste à résoudre le cas d'un sac de capacité 8 avec seulement les deux objets :
-^ Objet ^ Valeur ^ Poids ^
+^ Objet ^ Valeur ^ Encombrement ^
-| A     | 126    | 14    |
+| A     | 126    | 14           |
-| B     | 32     | 2     |
+| B     | 32     | 2            |
-Il devrait être évident que dans ce cas, le meilleur sac contient seulement B. On pourra dire que $sad_{2, 8} = \{ B \}$.
+Il devrait être évident que dans ce cas, le meilleur sac contient seulement B. On pourra dire que $msad_{2, 8} = \{ B \}$.
 Dans le cas de notre problème, on pourra prendre $0 \leqslant i \leqslant 6$ et $0 \leqslant c \leqslant C = 15$.
@@ Ligne 84: / Ligne 84: @@
 == Questions ==
-  - Que vaut $sad_{0,0}$ ?
+  - Que vaut $msad_{0,0}$ ?
-  - Plus généralement, que vaut $sad_{i, 0}$ pour tous les $i$ ?
+  - Plus généralement, que vaut $msad_{i, 0}$ pour tous les $i$ ?
-  - De même, que vaut $sad_{0,c}$ pour tous les $c$ ?
+  - De même, que vaut $msad_{0,c}$ pour tous les $c$ ?
-  - Pour quelle valeur de $i$ et $c$ faut-il trouver $sad_{i,c}$ pour répondre au problème posé au début ?
+  - Pour quelle valeur de $i$ et $c$ faut-il trouver $msad_{i,c}$ pour répondre au problème posé au début ?
 </WRAP>
-La méthode dynamique consiste à chercher $sad_{i,c}$ en considérant les valeurs de $sad{i',c'}$ avec $i' \leq i$ et $c' \leq c$. On cherche donc à remplir un tableau comme celui-ci :
+La méthode dynamique consiste à chercher $msad_{i,c}$ en considérant les valeurs de $msad_{i',c'}$ avec $i' \leq i$ et $c' \leq c$. On cherche donc à remplir un tableau comme celui-ci :
 |       ^ c = 0 ^ c = 1 ^ c = 2 ^ c = 3 ^ ...   ^ c = 14 ^ c = 15 ^
@@ Ligne 103: / Ligne 103: @@
 == Questions ==
-  - $sad(2,4)$ est le meilleur sac de capacité 4 kg avec un choix d'item parmi A, B. $sad(3,4)$ est le meilleur sac de capacité 4 kg avec un choix d'item parmi A, B, C.\\ Pourquoi puis-je affirmer que $sad(2,4) = sad(3,4)$ ?
+  - $msad_{2,4}$ est le meilleur sac de capacité 4 avec un choix d'item parmi A, B.\\ $msad_{3,4}$ est le meilleur sac de capacité 4 avec un choix d'item parmi A, B, C.\\ Pourquoi puis-je affirmer que $msad_{2,4} = msad_{3,4}$ ?
-  - $sad(3,7)$ est le meilleur sac de capacité 7 kg avec un choix d'item parmi A, B, C. Pourquoi puis-je affirmer que $sad(3,7)$ est le meilleur entre
+  - $msad_{3,7}$ est le meilleur sac de capacité 7 avec un choix d'item parmi A, B, C.\\ Pourquoi puis-je affirmer que $msad_{3,7}$ est le meilleur entre
-    * $sad(2,7)$, meilleur sac de capacité 7 kg avec un choix d'item parmi A, B,
+    * $msad_{2,7}$, meilleur sac de capacité 7 avec un choix d'item parmi A, B,
-    * $sad(2,2) \cup \{ C \}$, c'est à dire le meilleur sac de capacité 2 kg avec un choix d'item parmi A, B, auquel on aurait ajouté C.
+    * $msad_{2,2} \cup \{ C \}$, c'est à dire le meilleur sac de capacité 2 avec un choix d'item parmi A, B, auquel on aurait ajouté C.
 </WRAP>
-D'une façon générale, pour $0 < i$ et $0 < c$, on calcule $sad(i,c)$ en considérant le meilleur entre :
+D'une façon générale, pour $0 < i$ et $0 < c$, on calcule $msad_{i,c}$ en considérant le meilleur entre :
-  * le sac $sad(i-1, c)$ -- c'est à dire le sac de même capacité dans lequel **on ne prend pas** le ième item,
+  * le sac $msad_{i-1, c}$, c'est à dire le sac de même capacité dans lequel **on ne prend pas** le i<sup>ème</sup> item,
-  * le sac $sad(i-1, c-p_i) \cup {\text{ième item}\}$, où $p_i$ est le poids du ième item, à condition que $p_i \leqslant c$.
+  * le sac $msad_{i-1, c-p_i} \cup \{\text{i}^\text{ème}\text{ item}\}$, où $p_i$ est le poids du i<sup>ème</sup> item, à condition que $p_i \leqslant c$.
 ==== Implémentation ====
-Pour les besoins du programme, on stockera les objets dans un dictionnaire :
+Pour les besoins du programme, on stockera les objets dans un tableau :
 <code lang=python>
-objets = {
+objets = [
-    "A":(126, 14),
+    {"nom": "A", "valeur":126, "encombrement":14},
-    "B":(32, 2),
+    {"nom": "B", "valeur":32,  "encombrement":2},
-    "C":(20, 5),
+    {"nom": "C", "valeur":20,  "encombrement":5},
-    "D":(5, 1),
+    {"nom": "D", "valeur":5,   "encombrement":1},
-    "E":(18, 6),
+    {"nom": "E", "valeur":18,  "encombrement":6},
-    "F":(80, 8)
+    {"nom": "F", "valeur":80,  "encombrement":8}
-}
+]
 </code>
-Faites attention que, par exemple, les 3 premiers objets ont les indices 0 à 2.
 <WRAP box>
 == Questions ==
-  - Écrire une fonction ''valeur(objets, contenu)''.\\ ''objets'' est la liste des objets, données plus haut.\\ ''contenu'' est un tableau contenant des indices d'items, par exemple ''%%[0, 2]%%'' ce qui correspond au contenu $\{A, C\}$.\\ La fonction renvoie la valeur du sac.\\ //Remarque : on autorise le calcul de la valeur d'un sac indépendamment de la contrainte de capacité.//<code lang=python>
+  - Écrire une fonction ''valeur(objets, contenu)''.\\ ''objets'' est la liste des objets, données plus haut.\\ ''contenu'' est un tableau contenant des **indices** d'items, par exemple ''%%[0, 2]%%'' ce qui correspond au contenu $\{A, C\}$.\\ La fonction renvoie la valeur du sac.\\ //Remarque : on autorise le calcul de la valeur d'un sac indépendamment de la contrainte de capacité.//<code lang=python>
 >>> valeur(objets, [0, 2])
 </code>
-  - Écrire une fonction ''poids(objets, contenu)''\\ Les arguments sont les mêmes que pour la fonction précédente. Maintenant la fonction renvoie le poids.<code lang=python>
+  - Écrire une fonction ''encombrement(objets, contenu)''\\ Les arguments sont les mêmes que pour la fonction précédente. Maintenant la fonction renvoie la masse.<code lang=python>
->>> poids(objets, [0, 2])
+>>> encombrement(objets, [0, 2])
 </code>
 </WRAP>
-On va maintenant réaliser une fonction ''sacados(objets, capacite)'' et qui renvoie le meilleur sac à dos avec ces objets et cette capacité. Dans cette fonction, nous utiliserons un tableau à deux dimensions ''sad'' contenant le tableau présenté précédemment et que l'on souhaite compléter.
+On va maintenant réaliser une fonction ''sacados(objets, capacite)'' et qui renvoie le meilleur sac à dos avec ces objets et cette capacité. Dans cette fonction, nous utiliserons un tableau à deux dimensions ''msad'' contenant le tableau présenté précédemment et que l'on souhaite compléter.
-''%%sad[i][c]%%'' représentera la liste des indices du meilleur sac à dos en considérant les ''i'' premiers items et une capacité ''c''.
+''%%msad[i][c]%%'' représentera la liste des indices du meilleur sac à dos en considérant les ''i'' premiers items et une capacité ''c''.
-Il faudra d'abord initialiser ''sad'' connaissant ses dimensions, sa première ligne et sa première colonne, comme vu avant. Il faudra ensuite parcourir les lignes et colonnes pour le compléter de proche en proche en utilisant la règle énoncée plus haut.
+Il faudra d'abord initialiser ''msad'' connaissant ses dimensions, sa première ligne et sa première colonne, comme vu avant. Il faudra ensuite parcourir les lignes et colonnes pour le compléter de proche en proche en utilisant la règle énoncée plus haut.
 <WRAP box>
@@ Ligne 155: / Ligne 152: @@
   - Testez et vérifiez que l'on obtient, pour notre problème, un meilleur sac à dos qu'avec l'algorithme glouton.
   - Évaluez la complexité temporel de cet algorithme.
+  - On vous fournit les objets sous forme d'un fichier csv {{ :nsi:terminales:liste.csv |}}. Dans ce fichier les encombrements sont exprimés en %, c'est à dire que le sac a une capacité 100.\\ Écrire la fonction ''sacados_from_file(filename)'' qui charge le fichier et renvoie la liste des items à prendre pour produire le meilleur sac à dos.
 </WRAP>