Objectifs

Trouver des solutions à des problèmes donnés grâce à l'approche gloutonne.

Activité 1 - Algorithmes gloutons

Définition

Un algorithme glouton (ou greedy algorithm en anglais) est une approche algorithmique qui fait des choix successifs en sélectionnant à chaque étape l'option optimale locale, dans l'espoir d'obtenir une solution optimale globale.

Les algorithmes gloutons sont souvent utilisés pour résoudre des problèmes d'optimisation combinatoire, bien qu'ils ne garantissent pas toujours d'obtenir la solution optimale.

Il suit généralement les étapes suivantes :

1. Définir un critère de sélection : on choisit l'élément qui semble le plus avantageux localement ;
2. Effectuer un choix : on sélectionne cet élément selon le critère établi ;
3. Vérifier la faisabilité : on s'assure que le choix respecte les contraintes du problème ;
4. Répétition du processus jusqu'à ce qu'une solution complète soit obtenue.

Les problèmes les plus couramment rencontrés sont le rendu de monnaie et le problème du sac à dos.

Le rendu de monnaie

Problème

On cherche à écrire une solution algorithmique permettant de rendre de la monnaie, tout en minimisant le nombre de pièces à rendre.

On donne les pièces (en €) suivantes : 1, 2, 5, 10, 20, 50, 100, 200, disponibles en quantité illimitée dans le cadre de l'activité.

Voici un exemple de rendu de monnaie sur le montant 13€ avec un algorithme dit glouton :

Localement, le plus avantageux pour rendre 13€ est de rendre 10€.

Il reste 3€.

Localement, le plus avantageux pour rendre 3€ est de rendre 2€.

Il reste 1€.

Localement, le plus avantageux pour rendre 1€ est de rendre 1€.

Il reste 0€.

L'algorithme s'arrête, on a donc rendu 3 pièces : 10€, 2€ et 1€.

Compréhension du problème

1. En reprenant l'exemple de l'algorithme glouton de l'énoncé, et le système monétaire (en €) suivant : 1, 2, 5, 10, 20, 50, 100, 200, calculer le nombre de pièces à rendre avec un montant de 28€.
2. Nous ne disposons plus de pièces de 1€. Calculer le nombre de pièces à rendre avec un montant de 36€. Que se passe-t-il ?

Programmation

On souhaite mettre au point un programme nous indiquant la liste des pièces à rendre, à partir d'un montant donné.

1. Définir une variable pieces qui contient la liste de l'ensemble des pièces du système monétaire français (sans les centimes), triées de la plus petite à la plus grande.
2. Définir une variable somme qui contient une somme à rendre, saisie au clavier. On rappelle que la fonction :

   int(input(texte))
   permet de saisir un nombre entier au clavier.

On donne l'algorithme à trous suivant, déterminant le mode de fonctionnement de l'algorithme du rendu de monnaie, où montant est l'entier saisi préalablement, et pieces la liste des pièces :

fonction rendu_monnaie(montant, pieces) :
    listePieceRendue ← ...
    indice ← ...
    tant que montant ... faire :
        si montant >= ... alors :
            ... ← ... - pieces[...]
            Ajouter dans listePieceRendue la valeur ...
        sinon :
            ... ← ... - 1
    retourner ...

3. Expliquer en quelques mots ce qu'est censé faire ce programme.
4. Recopier et compléter les trous manquants de l'algorithme.
5. Traduire la fonction en une fonction python.
6. Tester la fonction python avec un montant de 53€.
7. Modifier le programme pour qu'il puisse prendre en compte les centimes.
8. Tester la fonction avec un montant de 53€30. Que se passe-t-il ?

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.

9. Modifier la liste des pièces en multipliant toutes les valeurs par 100, sans le faire manuellement.
10. Lors de la saisie du montant, multiplier la variable par 100. Faire un nouveau test.

Nous ne disposons plus de pièces de 20 centimes.

11. Supprimer la valeur dans la liste, et faire un nouveau test avec le montant 53€30. Comment le programme s'est-il adapté pour fournir un résultat ?

Cette fois-ci, nous ne disposons plus de pièces de 1 centime.

12. Tester le rendu de monnaie sur 53€36. Que se passe-t-il ?
13. Expliquer en quoi la solution gloutonne pourrait poser problème dans certains cas.
14. Modifier le programme pour qu'il puisse également afficher le nombre de pièces rendus.

Problème du sac à dos

Définition

Le problème du sac à dos est un problème d'optimisation combinatoire. Il consiste à sélectionner des objets parmi un ensemble donné, de manière à maximiser une valeur totale, tout en respectant une contrainte de poids maximal que peut contenir un sac.

Dans notre cas, chaque objet a un poids et une valeur. L'objectif est de remplir le sac de manière optimale en choisissant les objets selon une stratégie gloutonne.

Dans l'univers du jeu vidéo League Of Legends, les joueurs combattent leurs adversaires en s'aidant d'objets permettant d'augmenter les caractéristiques de leur champion. Les objets s'achètent dans une boutique grâce à des pièces d'or obtenues de diverses façons durant la partie.

Il existe plusieurs types d'objets. Nous allons nous concentrer sur les objets permettant d'augmenter les dégâts d'un champion.
On donne une liste non exhaustive d'objets dans le tableau suivant :

Nom	Valeur	Dégât
Lame	50	8
Abatteur	45	7
Épée longue	35	9
Dague dentelée	110	30
Glaive	230	50
Faucille	40	5

L'objectif de ce TP va être d'essayer de déterminer quels objets prendre pour maximiser les dégâts, avec un certain nombre de pièces d'or données. Nous ne sommes pas obligés de dépenser toutes les pièces.

Compréhension du problème

1. On dispose de 300 pièces d'or. Énumérer 5 listes différentes d'objets à acheter avec ce montant.
2. Déterminer la valeur des dégâts que représente l'ensemble des objets de chacune des listes.
3. En utilisant le concept de l'algorithme glouton (on prend la plus grande valeur en premier), à quoi ressemblerait notre liste d'objets ? Est-ce la meilleure solution pour maximiser les dégâts ?
4. Déterminer une solution meilleure que celle trouvée précedemment.

Modélisation du problème

On souhaite modéliser sur python un début de solution.

1. En utilisant un dictionnaire, représenter les données du tableau plus haut. La clé sera le nom de l'objet, et la valeur une liste contenant leur coût et dégats.
2. Écrire une fonction glouton_objet(dico_objet, pieces) qui prend en paramètres dico_objet, le dictionnaire des objets, et pieces, le montant des pièces que le joueur possède. Cette fonction devra renvoyer une liste contenant la liste des objets à acheter en utilisant le principe de l'algorithme glouton.
   Aide

   Vous créerez dans cette fonction 3 listes correspondant aux noms des objets, à leur coût, et leur dégât. Concrètement, vous séparerez les informations pour avoir une liste nom, une liste coût, une liste dégât. Cette étape sera importante pour plus tard.

Plus grosse aide

Solution un peu meilleure

Ratio

Nous avons vu plus haut que l'algorithme glouton en l'état n'est pas suffisant pour maximiser les dégâts.
Une solution consiste à calculer un ratio dégât/coût pour déterminer quel objet serait le plus susceptible de maximiser les dégât à moindre coût.

1. Ecrire une fonction ratio(dico_objets) qui prend un dictionnaire d'objets en paramètre, et ajoute dans la liste de chaque objet de ce dictionnaire la valeur du ratio calculé.
2. En appliquant la fonction ratio sur votre dictionnaire, quel est l'objet avec le plus gros ratio ? Quel est celui avec le plus faible ratio ?
3. En appliquant l'algorithme glouton avec les ratios des objets, déterminer la solution optimale de maximisation des dégâts avec 300 pièces d'or.
4. Modifier le programme de l'algorithme glouton pour qu'il prenne en compte les ratios, et qu'il calcule les objets à prendre en fonction des ratios.