Aller au contenu principal
Objectifs
  • Comprendre le principe d'un algorithme glouton.
  • Appliquer la stratégie gloutonne sur le problème du rendu de monnaie.
  • Modéliser et programmer le problème du sac à dos en Python.

Activité 1 - Algorithmes gloutons

Introduction​

Imagine que tu dois rendre la monnaie à un client le plus rapidement possible. Tu n'as pas le temps de chercher la combinaison parfaite : tu prends simplement la plus grosse pièce possible, puis la suivante, et ainsi de suite.

C'est exactement le principe d'un algorithme glouton : à chaque étape, on fait le meilleur choix possible à cet instant, sans se préoccuper de la suite.

Définition

Un algorithme glouton (greedy algorithm en anglais) est un algorithme qui résout un problème en faisant, à chaque étape, le choix qui semble localement optimal.

L'espoir est que l'enchaînement de bons choix locaux aboutisse à une solution globalement satisfaisante - mais ce n'est pas toujours garanti.

Un algorithme glouton suit toujours le même schéma :

  1. Choisir l'élément qui semble le plus avantageux à cet instant ;
  2. Vérifier que ce choix respecte les contraintes du problème ;
  3. Répéter jusqu'à obtenir une solution complète.

Les deux problèmes classiques abordés dans cette activité sont le rendu de monnaie et le problème du sac à dos.

Le rendu de monnaie​

Problème

On cherche à rendre une somme d'argent à un client en utilisant le moins de pièces possible.

On dispose des pièces suivantes (en €), disponibles en quantité illimitée : 1, 2, 5, 10, 20, 50, 100, 200.

Voici comment un algorithme glouton rend 13€ :

  • La plus grande pièce ≤ 13€ est 10€, Il reste 3€.
  • La plus grande pièce ≤ 3€ est 2€, Il reste 1€.
  • La plus grande pièce ≤ 1€ est 1€, Il reste 0€. On s'arrête.

Résultat : 3 pièces rendues - 10€, 2€ et 1€.

Compréhension du problème​

Exercices
  1. 1
    En appliquant le même algorithme glouton, déterminer les pièces à rendre pour un montant de 28€. Combien de pièces sont utilisées ?
  2. 2
    On suppose maintenant qu'il n'y a plus de pièce de 1€ dans la caisse. Appliquer l'algorithme glouton pour rendre 36€. Que se passe-t-il ?

Programmation​

On souhaite écrire une fonction Python qui retourne la liste des pièces à rendre pour un montant donné.

Exercices
  1. 1

    Définir une variable pieces contenant la liste des pièces du système monétaire français (sans les centimes), triées de la plus grande à la plus petite (à l'aide des méthodes de tris étudiées en cours). Pourquoi cet ordre est-il important pour l'algorithme glouton ?

  2. 2

    Définir une variable somme contenant un montant entier saisi au clavier, à l'aide d'un input.

On donne l'algorithme suivant, à trous, pour le rendu de monnaie :

fonction rendu_monnaie(montant, pieces) :
    listePieceRendue ← ...
    indice ← ...
    tant que montant ... faire :
        si montant >= ... alors :
            ... ← ... - pieces[...]
            Ajouter dans listePieceRendue la valeur ...
        sinon :
            ... ← ... - 1
    retourner ...
  1. 3
    Expliquer en une ou deux phrases ce que fait cet algorithme, sans utiliser de termes techniques.
  2. 4
    Recopier et compléter les trous de l'algorithme.
  3. 5
    Traduire cet algorithme en une fonction Python rendu_monnaie(montant, pieces).
  4. 6
    Tester la fonction avec un montant de 53€. Vérifier le résultat à la main.

On souhaite maintenant prendre en compte les centimes.

  1. 7
    Modifier la liste pieces pour inclure les centimes (1c, 2c, 5c, 10c, 20c, 50c) et adapter la saisie du montant pour accepter des valeurs décimales (float).
  2. 8
    Tester avec 53,30€. Que se passe-t-il ? Pourquoi obtient-on un résultat inattendu ?

Le programme a un problème à cause de la norme IEEE-754 (souvenirs ?). On ne peut pas soustraire des nombres flottants.
Pour palier à ce problème, nous allons multiplier toutes les valeurs par 100, pour ne plus avoir de nombre à virgule.

Pour contourner ce problème, on va tout convertir en centimes (multiplier par 100) pour ne travailler qu'avec des entiers.

  1. 9
    Modifier la liste pieces pour que toutes les valeurs soient exprimées en centimes (ex : 1€ → 100), sans le faire manuellement.
  2. 10
    Lors de la saisie, multiplier le montant par 100 pour le convertir en centimes. Tester à nouveau avec 53,30€ (soit 5330 centimes).

On suppose maintenant qu'il n'y a plus de pièce de 20 centimes.

  1. 11
    Retirer la valeur correspondante de la liste et tester avec 53,30€. Comment l'algorithme s'adapte-t-il ?

On suppose maintenant qu'il n'y a plus de pièce de 1 centime.

  1. 12
    Tester le rendu pour 53,36€ (soit 5336 centimes). Que se passe-t-il ? Pourquoi ?
  2. 13
    En s'appuyant sur les questions 2 et 12, expliquer dans quel cas un algorithme glouton peut échouer à trouver une solution.
  3. 14
    Modifier la fonction pour qu'elle affiche également le nombre total de pièces rendues.

Problème du sac à dos​

Définition

Le problème du sac à dos consiste à choisir des objets parmi un ensemble donné, de façon à maximiser une valeur totale tout en respectant une contrainte de poids (ou de coût) maximale.

Chaque objet possède un coût et une valeur. L'objectif est de remplir le sac de façon optimale.

Dans League of Legends, les joueurs achètent des objets pour améliorer leur champion grâce aux pièces d'or gagnées en partie. Parmi ces objets, certains augmentent les dégâts infligés.

On donne la liste suivante :

NomCoût (or)Dégâts
Lame508
Abatteur457
Épée longue359
Dague dentelée11030
Glaive23050
Faucille405

L'objectif est de maximiser les dégâts totaux avec un budget limité en or. On n'est pas obligé de tout dépenser.

Compréhension du problème​

Exercices
  1. 1
    On dispose de 300 pièces d'or. Proposer 3 combinaisons d'objets différentes respectant ce budget, et calculer les dégâts totaux de chacune.
  2. 2
    En appliquant la stratégie gloutonne par coût décroissant (on achète l'objet le plus cher possible en premier), déterminer la liste d'objets obtenue avec 300 or. Calculer les dégâts totaux.
  3. 3
    Est-ce la meilleure solution parmi celles trouvées en question 1 ? Proposer une combinaison qui fait plus de dégâts, et expliquer pourquoi la stratégie gloutonne brute n'est pas toujours optimale.

Modélisation du problème​

Exercices
  1. 1

    Représenter les données du tableau sous forme d'un dictionnaire Python. La clé sera le nom de l'objet, et la valeur une liste [coût, dégâts].

  2. 2

    Écrire une fonction glouton_objet(dico_objet, pieces) qui prend en paramètres le dictionnaire des objets et le budget disponible, et renvoie la liste des noms des objets achetés selon la stratégie gloutonne par coût décroissant.

    Aide

    Dans cette fonction, créer trois listes séparées : une pour les noms, une pour les coûts, une pour les dégâts. Cela facilitera le tri et la manipulation des données par la suite.

    def glouton_objet(dico_objet,pieces):
      liste_objet = ...
      noms = ...
      cout = ...
      for cle, valeur in dico_objet.... :
        noms.append(...)
        cout.append(...)
      while pieces != ... and cout != ... :
        plus_grosse_piece = max(...)
        indice = cout.index(...)
        if pieces >= ... :
          liste_objet.append(...)  
          pieces-= ...
        else :
          noms.pop(...)
          cout.pop(...)
      return ...

Une stratégie plus efficace : le ratio dégâts/coût​

Ratio

La stratégie gloutonne par coût seul ne maximise pas toujours les dégâts. Une meilleure approche consiste à calculer pour chaque objet son ratio dégâts/coût : plus ce ratio est élevé, plus l'objet est "rentable" par pièce d'or dépensée.

Exercices
  1. 1

    Calculer le ratio dégâts/coût de chaque objet du tableau. Quel objet est le plus rentable ? Le moins rentable ?

  2. 2

    Écrire une fonction ajouter_ratio(dico_objets) qui, pour chaque objet du dictionnaire, ajoute le ratio dégâts / coût à la fin de sa liste de valeurs. La fonction modifie le dictionnaire directement (pas de valeur de retour nécessaire).

  3. 3

    En appliquant la stratégie gloutonne par ratio décroissant, déterminer la liste d'objets à acheter avec 300 or. Comparer les dégâts totaux avec la stratégie par coût de la partie précédente.

  4. 4

    Modifier la fonction glouton_objet pour qu'elle utilise le ratio comme critère de sélection plutôt que le coût. Tester avec 300 or et afficher les dégâts totaux obtenus.