Différences

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

--- nsi:terminales:sac_a_dos [2021/04/13 15:25] – créée goupillwiki
+++ nsi:terminales:sac_a_dos [2023/02/03 12:08] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
-<markdown>
+====== Problème du sac à dos ======
-# 13. Problème du sac à dos
-## Qu'est-ce ?
+**Version programmation dynamique**
-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.
+===== Qu'est-ce ? =====
-**Exemple :** On dispose d'un sac d'une capacité de C = 15 kg et de la liste d'objets suivants :
+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.
-| Objet | Valeur | Poids |
+<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>
-| ----- | ------ | ----- |
-| A     | 126    | 14    |
-| B     | 32     | 2     |
-| C     | 20     | 5     |
-| D     | 5      | 1     |
-| E     | 18     | 6     |
-| F     | 80     | 8     |
-## Vu en première : L'algorithme glouton
+**Exemple :** On dispose d'un sac d'une capacité de $C = 15$ et de la liste d'objets suivants :
-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 puis on remplit le sac en prenant les objets dans l'ordre.
+^ Objet ^ Valeur ^ Encombrement ^
+| A     | 126    | 14           |
+| B     | 32     | 2            |
+| C     | 20     | 5            |
+| D     | 5      | 1            |
+| E     | 18     | 6            |
+| F     | 80     | 8            |
-Par exemple, si on choisit de trier par valeur décroissante, on obtient :
+===== Vu en première : L'algorithme glouton =====
-| Objet | Valeur | Poids |
+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** puis on remplit le sac en prenant les objets dans l'ordre.
-| ----- | ------ | ----- |
-| A     | 126    | 14    |
-| F     | 80     | 8     |
-| B     | 32     | 2     |
-| C     | 20     | 5     |
-| E     | 18     | 6     |
-| D     | 5      | 1     |
-Puis on complète le sac. On prend A en premier. Il ne reste alors que 1 kg de place disponible. On ne peut donc pas prendre les items suivants sauf le D.
+<WRAP tip>Avec la méthode gloutonne, c'est le tri qui prend le plus de temps : les tris les plus rapides, pour un tableau de taille $n$, sont en $n\log(n)$. La suite de l'algorithme glouton ne nécessite qu'un parcours simple de la liste et est donc en $n$. Globalement, l'algorithme glouton est donc en $n\log(n)$.
+C'est à dire qu'une liste de taille 100 prend consomme de l'ordre de 200, taille 1000 consomme 3000, 10000 consomme 40000, etc.</WRAP>
+== Tri par valeur décroissante ==
+Par exemple, si on choisit de trier par **valeur décroissante**, on obtient :
+^ Objet ^ Valeur ^ Encombrement ^
+| A     | 126    | 14           |
+| F     | 80     | 8            |
+| B     | 32     | 2            |
+| C     | 20     | 5            |
+| E     | 18     | 6            |
+| D     | 5      | 1            |
+Puis on complète le sac :
+  * On prend A en premier,
+  * il ne reste alors que 1 kg de place disponible. On ne peut donc pas prendre les items F, B, ...
+  * on prend D.
 Le sac contiendra A et D totalisant une valeur de 131
-On aurait aussi pu trier selon le meilleur rapport valeur / poids
+== Tri par valeur / poids décroissant ==
-| Objet | Valeur | Poids | rapport V/P |
+On aurait aussi pu trier par **rapport valeur / encombrement décroissant**
-| ----- | ------ | ----- | ----------- |
-| B     | 32     | 2     | 16          |
+^ Objet ^ Valeur ^ Encombrement ^ rapport V/E ^
-| F     | 80     | 8     | 10          |
+| B     | 32     | 2            | 16          |
-| A     | 126    | 14    | 9           |
+| F     | 80     | 8            | 10          |
-| D     | 5      | 1     | 5           |
+| A     | 126    | 14           | 9           |
-| C     | 20     | 5     | 4           |
+| D     | 5      | 1            | 5           |
-| E     | 18     | 6     | 3           |
+| C     | 20     | 5            | 4           |
+| 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 51: / Ligne 61: @@
 Ce sac contenant B, F, D totalise une valeur de 117.
-La stratégie précédent était meilleure mais ce n'est pas vrai en général.
+<WRAP important>L'approche gloutonne donne une bonne solution en un temps très court. Mais elle ne donne aucune garantie d'obtenir la meilleure solution. On ne peut pas non plus prévoir quel tri sera le meilleur. Ici, le tri par valeur était meilleur. Avec une autre liste d'objets, le tri par rapport décroissant aurait pu être meilleur.</WRAP>
-## Programmation dynamique
+===== Programmation dynamique =====
-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 valeur optimale obtenue dans le problème du sac à dos avec un sac de capacité `c` et avec les `i` premiers objets.
+==== Principe ====
-Par exemple `SaD[2,8]` consiste à résoudre le cas d'un sac de capacité 8 kg avec seulement les deux 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.
-| Objet | Valeur | Poids |
+<wrap important>Attention, a bien distinguer $c$ et $C$ !</wrap>
-| ----- | ------ | ----- |
-| A     | 126    | 14    |
-| B     | 32     | 2     |
-Dans le cas de notre problème initial, on pourra prendre $0 \leqslant i \leqslant 6$ et $0 \leqslant c \leqslant C = 15$ .
+Par exemple $msad_{2,8}$ consiste à résoudre le cas d'un sac de capacité 8 avec seulement les deux objets :
-La notation `SaD[i][c]` avec des crochets est choisis car nous souhaitons stocker tous les résultats intermédiaires dans un tableau.
+^ Objet ^ Valeur ^ Encombrement ^
+| A     | 126    | 14           |
+| B     | 32     | 2            |
-Pour les besoins du programme, on stockera les objets dans un tableau :
+Il devrait être évident que dans ce cas, le meilleur sac contient seulement B. On pourra dire que $msad_{2, 8} = \{ B \}$.
-```python
+Dans le cas de notre problème, on pourra prendre $0 \leqslant i \leqslant 6$ et $0 \leqslant c \leqslant C = 15$.
-objets = [
-    ('A', 126, 14),
-    ('B', 32, 2),
-    ('C', 20, 5),
-    ('D', 5, 1),
-    ('E', 18, 6),
-    ('F', 80, 8)
-]
-```
-Faites attention que l'objet numéro 3 est l'objet d'indice 2.
+<WRAP box>
+== Questions ==
-**Questions :**
+  - Que vaut $msad_{0,0}$ ?
+  - Plus généralement, que vaut $msad_{i, 0}$ pour tous les $i$ ?
+  - De même, que vaut $msad_{0,c}$ pour tous les $c$ ?
+  - Pour quelle valeur de $i$ et $c$ faut-il trouver $msad_{i,c}$ pour répondre au problème posé au début ?
+</WRAP>
-. Quelles sont les valeurs de `i` et `c` pour lesquelles `SaD[i][c]` est la réponse au problème initial ?
+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 :
-. Que peut-on dire de `SaD[i][0]` pour tous les `i` ?
+|       ^ c = 0 ^ c = 1 ^ c = 2 ^ c = 3 ^ ...   ^ c = 14 ^ c = 15 ^
+^ i = 0 | $\varnothing$ | $\varnothing$ | $\varnothing$ | $\varnothing$ | ...   | $\varnothing$ | $\varnothing$ |
+^ i = 1 | $\varnothing$ |       |       |       |       |        |        |
+^ ...   | $\varnothing$ |       |       |       |       |        |        |
+^ i = 6 | $\varnothing$ |       |       |       |       |        |    ??? |
-. Que peut-on dire de `SaD[0][c]` pour tous les `c` ?
+Maintenant, nous devons réfléchir à la façon de progresser dans ce tableau.
-. On en arrive au point délicat. On va commencez avec deux cas particulier avant de généraliser.
+<WRAP box>
+== Questions ==
-   * Je me demande quelle la plus haute valeur totale d'un sac de capacité 4 kg avec choix parmi A, B, C.
+  - $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}$ ?
+  - $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
+    * $msad_{2,7}$, meilleur sac de capacité 7 avec un choix d'item parmi A, B,
+    * $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>
-     Pourquoi puis-je affirmer que la réponse est la même que pour le cas 4 kg avec choix parmi A, B ?
+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 $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 $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 tableau :
+<code lang=python>
+objets = [
+    {"nom": "A", "valeur":126, "encombrement":14},
+    {"nom": "B", "valeur":32,  "encombrement":2},
+    {"nom": "C", "valeur":20,  "encombrement":5},
+    {"nom": "D", "valeur":5,   "encombrement":1},
+    {"nom": "E", "valeur":18,  "encombrement":6},
+    {"nom": "F", "valeur":80,  "encombrement":8}
+]
+</code>
-   * Je me demande quelle la plus haute valeur totale d'un sac de capacité 7 kg avec choix parmi A, B, C.
+<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>
+>>> valeur(objets, [0, 2])
+
+</code>
+  - É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>
+>>> encombrement(objets, [0, 2])
+
+</code>
+</WRAP>
-     Pourquoi puis-je affirmer que le meilleur choix possible sera :
+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.
-     * soit le meilleur sac de 7 kg avec choix parmi A, B,
+''%%msad[i][c]%%'' représentera la liste des indices du meilleur sac à dos en considérant les ''i'' premiers items et une capacité ''c''.
-     * soit le meilleur sac de 2 kg avec choix parmi A, B et contenant l'objet C
-. Généralisation. Pour `i > 0`, notons `p_i` le poids de l'objet numéro `i` et `v_i` sa valeur. Justifiez que :
+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.
-   * si `c < p_i`, alors  `SaD[i][c] = SaD[i-1][c]`
+<WRAP box>
-   * sinon, `SaD[i][c] = max(SaD[i-1][c], SaD[i-1][c - p_i] + v_i)`
+== Questions ==
-. Réalisez la fonction Python `sacados`prenant un tableau d'objets et la capacité totale en argument et renvoyant la plus haute valeur d'un tel sac.
+  - Écrire la fonction ''sacados''
+  - 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>
-   Testez et constatez que le résultat est meilleur que celui obtenu avec l'algorithme glouton. Ce choix est optimal.
-</markdown>