GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:premiere:sac_a_dos

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
nsi:premiere:sac_a_dos [2021/05/10 11:23] – [Implémentation] goupillwikinsi:premiere:sac_a_dos [2022/05/09 20:00] (Version actuelle) – goupillwiki
Ligne 4: Ligne 4:
  
 Il s'agit d'un problème classique d'algorithmique. Il s'agit d'un problème classique d'algorithmique.
 +
 +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,   * On dispose d'un sac de capacité C,
Ligne 23: Ligne 27:
 L'algorithme glouton donne une réponse pas forcément optimale au problème posé mais il est simple : 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. Par exemple, trions le tableau par valeur décroissante.
Ligne 45: Ligne 49:
 Le sac contiendra A et D totalisant une valeur de 131. Le sac contiendra A et D totalisant une valeur de 131.
  
-== Poids croissant ==+=== Poids croissant ===
  
 C'est un autre choix possible. Il aboutira à un contenu de sac différent. C'est un autre choix possible. Il aboutira à un contenu de sac différent.
Ligne 76: Ligne 80:
 ===== Implémentation ===== ===== 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> <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>  </Code> 
  
-== Sac ==+=== Sac ===
  
 Le contenu du sac sera lui aussi représenté par un tableau. Par exemple : Le contenu du sac sera lui aussi représenté par un tableau. Par exemple :
  
 <Code python> <Code python>
-sac = [ +sac = ["A", "D"]
-  { "Nom":"A", "Valeur":126, "Poids":14 }, +
-  { "Nom":"D", "Valeur":5, "Poids":1 } +
-]+
 </Code> </Code>
  
-== fonctions utiles ==+=== fonctions utiles ===
  
 Nous avons besoin des fonctions suivantes : Nous avons besoin des fonctions suivantes :
-  - ajouter un objet dans un sac si c'est possible, 
   - trier les objets dans un ordre défini,   - trier les objets dans un ordre défini,
 +  - calculer le poids total d'un sac,
   - calculer la valeur 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** puis **à exécuter** : 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 False +
-     +
-def tri(objets, critere): +
-    ''' +
-    objets: tableau des objets disponibles à trier +
-    critere: fonction qui pour un un objet donné renvoie sa valeur dans le tri +
-      exemple : si on tri par valeur décroissante, critere(objet) doit renvoyer la valeur de l'objet +
-    trie les objets selon le critère, toujours par ordre décroissant +
-    ne renvoie rien, trie objets en place+
     '''     '''
     return     return
  
-def valeur_sac(sac):+ 
 +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: sac dont on veut la valeur+    sac: tableau des noms des objets contenus dans le sac
     renvoie la valeur totale de ce sac.     renvoie la valeur totale de ce sac.
     '''     '''
     return 0     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 glouton(objets, critere):+ 
 +def ajouter_objet_dans_sac(nom, sac):
     '''     '''
-    objets: tableau des objets que l'on peut mettre dans le sac+    nom: nom de l'objet que l'on souhaite ajouter 
 +    sac: tableau des noms des objets contenus dans le sac 
 +    modifie sac en y ajoutant nom 
 +    ''' 
 +    return 
 +     
 + 
 +def glouton(C, critere): 
 +    ''' 
 +    C: capacité max du sac
     critere: fonction utilisée dans le tri     critere: fonction utilisée dans le tri
     renvoie le sac obtenu par l'algorithme glouton suivant le critère défini     renvoie le sac obtenu par l'algorithme glouton suivant le critère défini
Ligne 148: Ligne 167:
     return []     return []
          
-if __name__ == '__main__': +# démonstration 
-    # tests +C = 15 
-    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 } 
-    ] +} 
-     + 
-    def critere_valeur(objet): +# exemple de critère     
-        return objet["Valeur"]+def critere_valeur(nom): 
 +    obj = objets[nom] 
 +    return obj["valeur"]
          
-    sac = glouton(objets, critere_valeur) +sac = glouton(C, critere_valeur) 
-    print(sac) +print(sac) 
-</file>+print(valeur(sac)) 
 +</code>
  
-== Fonction lambda ==+=== 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. 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 $objet \mapsto objet[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 ''%%objet%%'' et que l'image est ''%%objet["Valeur"]%%''.+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 : Il existe une notation pour cela en Python :
  
-<Code python> +<code python> 
-lambda objet: objet["Valeur"] +lambda nom: objets[nom]['valeur'] 
-</Code>+</code>
  
-C'est une fonction anonyme prenant comme argument (//antécédent//) ''%%objet%%'' et renvoie (//image//) ''%%objet["Valeur"]%%''.+C'est une fonction anonyme prenant comme argument (//antécédent//) ''%%nom%%'' et renvoie (//image//) ''%%objets[nom]['Valeur']%%''.
  
 Alors nous pouvons remplacer : Alors nous pouvons remplacer :
-<Code python> +<code python> 
-# code actuel, dans les tests +# code actuel 
-def critere_valeur(objet): +def critere_valeur(nom): 
-    return objet["Valeur"]+    return objets[nom]['valeur']
 sac = glouton(objets, critere_valeur) sac = glouton(objets, critere_valeur)
  
 # en utilisant lambda # en utilisant lambda
-sac = glouton(objets, lambda objet: objet["Valeur"])  +sac = glouton(objets, lambda nom: objets[nom]['valeur'])  
-</Code>+</code>
  
 Le résultat est le même. Le résultat est le même.
  
-== autre critères ==+=== Autre critères ===
  
 Exécutez le programme avec d'autres critères : Exécutez le programme avec d'autres critères :
   * rapport valeur / poids décroissant,   * 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 !)+  * 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%%''. Essayez de le faire en utilisant ''%%lambda%%''.
  
  
nsi/premiere/sac_a_dos.1620638639.txt.gz · Dernière modification : de goupillwiki