Exemple d'utilisation
Exercices - Algorithmes Gloutons
Niveaux de difficulté : ⭐ Facile | ⭐⭐ Moyen | ⭐⭐⭐ Difficile
Exercice 1 ⭐⭐ : Achat de V-Bucks (Fortnite)
Dans Fortnite, on peut acheter des V-Bucks avec les packs suivants : {500, 1000, 2800, 5000, 13500} V-Bucks.
Tu veux acheter exactement 8000 V-Bucks en utilisant le moins de packs possible.
- Appliquer l'algorithme glouton à la main pour obtenir 8000 V-Bucks. Combien de packs sont nécessaires ?
- Existe-t-il une meilleure solution ?
- Ce système est-il canonique (le glouton donne-t-il toujours l'optimal) ?
Voir la correction
**Question 1 : Algorithme glouton** - On prend 5000 (le plus grand ≤ 8000) : reste 3000 - On prend 2800 : reste 200 - 200 < 500, on ne peut plus rien prendre ! L'algorithme glouton **échoue** à donner exactement 8000. **Question 2 : Meilleure solution** - 8000 = 5000 + 1000 + 1000 + 1000 = **4 packs** - Ou : 8000 = 2800 + 2800 + 1000 + 1000 + 500 - 100... non ça ne marche pas non plus facilement. En fait, 8000 = 5000 + 1000 × 3 = **4 packs** est la solution. **Question 3 :** Non, ce système n'est pas canonique. L'algorithme glouton ne fonctionne pas toujours car les valeurs ne sont pas des multiples les unes des autres.Exercice 2 ⭐ : Playlist Spotify optimale
Tu prépares une playlist pour un trajet de 60 minutes. Tu veux y mettre le maximum de sons parmi tes favoris :
| Titre | Artiste | Durée (min) |
|---|---|---|
| Alibi | Sevdaliza | 4 |
| La Kiffance | Naps | 3 |
| Bande organisée | Jul & SCH | 6 |
| Mood | 24kGoldn | 2 |
| Fever | Dua Lipa | 3 |
| Blinding Lights | The Weeknd | 3 |
| Peaches | Justin Bieber | 3 |
| Heat Waves | Glass Animals | 4 |
| Iko Iko | Justin Wellington | 3 |
| Astronaut in the Ocean | Masked Wolf | 2 |
Objectif : Maximiser le nombre de titres dans la playlist sans dépasser 60 minutes.
- Quelle stratégie gloutonne proposez-vous ?
- Appliquer cette stratégie. Combien de titres obtenez-vous ?
- Quelle est la durée totale de la playlist ?
Voir la correction
**Question 1 : Stratégie gloutonne** Pour maximiser le **nombre** de titres, on prend les titres **les plus courts en premier**. **Question 2 : Application** Tri par durée croissante : - Mood (2 min) → total = 2 - Astronaut in the Ocean (2 min) → total = 4 - La Kiffance (3 min) → total = 7 - Fever (3 min) → total = 10 - Blinding Lights (3 min) → total = 13 - Peaches (3 min) → total = 16 - Iko Iko (3 min) → total = 19 - Alibi (4 min) → total = 23 - Heat Waves (4 min) → total = 27 - Bande organisée (6 min) → total = 33 **Tous les 10 titres** rentrent dans 60 minutes ! **Question 3 :** Durée totale : **33 minutes** *Note : Dans ce cas, la contrainte de 60 min n'était pas limitante. On aurait pu ajouter d'autres titres.*Exercice 3 ⭐⭐ : Inventaire Minecraft
Tu joues à Minecraft et ton inventaire peut contenir 64 objets maximum. Tu veux maximiser la valeur totale des objets pour le commerce avec les villageois.
| Objet | Quantité dispo | Valeur (émeraudes) | Poids (slots) |
|---|---|---|---|
| Diamant | 10 | 8 | 1 |
| Lingot d'or | 20 | 3 | 1 |
| Fer | 50 | 1 | 1 |
| Livre enchanté | 5 | 15 | 1 |
| Émeraude | 30 | 1 | 1 |
Chaque objet prend 1 slot, mais tu ne peux pas dépasser 64 slots au total.
- Calculer le ratio valeur/slot pour chaque objet.
- Appliquer l'algorithme glouton (meilleur ratio d'abord).
- Quelle est la valeur totale obtenue ?
Voir la correction
**Question 1 : Ratios valeur/slot** | Objet | Valeur | Ratio | |-------|--------|-------| | Livre enchanté | 15 | 15.0 | | Diamant | 8 | 8.0 | | Lingot d'or | 3 | 3.0 | | Émeraude | 1 | 1.0 | | Fer | 1 | 1.0 | **Question 2 : Algorithme glouton** Tri par ratio décroissant, on prend dans l'ordre : - Livre enchanté : 5 objets → slots = 5, valeur = 75 - Diamant : 10 objets → slots = 15, valeur = 75 + 80 = 155 - Lingot d'or : 20 objets → slots = 35, valeur = 155 + 60 = 215 - Émeraude : 29 objets (64-35=29) → slots = 64, valeur = 215 + 29 = 244 **Question 3 : Valeur totale** **244 émeraudes** avec 64 slots utilisés.Exercice 4 ⭐⭐⭐ : Planning de stream Twitch
Tu es streamer et tu dois planifier tes lives pour demain. Plusieurs marques te proposent des partenariats avec des créneaux imposés :
| Sponsor | Début | Fin | Rémunération |
|---|---|---|---|
| Red Bull | 14h | 17h | 200€ |
| Logitech | 15h | 18h | 180€ |
| Samsung | 17h | 19h | 150€ |
| Razer | 18h | 20h | 120€ |
| Discord | 19h | 21h | 100€ |
| NordVPN | 20h | 22h | 90€ |
Objectif : Maximiser le nombre de partenariats (pas de chevauchement possible).
- Quelle stratégie gloutonne permet de maximiser le nombre de streams ?
- Appliquer cette stratégie. Quels sponsors sélectionnez-vous ?
- Implémenter l'algorithme en Python.
Voir la correction
**Question 1 : Stratégie** Pour maximiser le nombre d'activités, on trie par **heure de fin croissante** et on prend chaque activité compatible. **Question 2 : Application** Tri par heure de fin : Red Bull (17h), Logitech (18h), Samsung (19h), Razer (20h), Discord (21h), NordVPN (22h) - Red Bull (14h-17h) : OK - Logitech (15h-18h) : chevauche Red Bull, refusé - Samsung (17h-19h) : commence à 17h, Red Bull finit à 17h, OK - Razer (18h-20h) : chevauche Samsung, refusé - Discord (19h-21h) : commence à 19h, Samsung finit à 19h, OK - NordVPN (20h-22h) : chevauche Discord, refusé **Sponsors sélectionnés : Red Bull, Samsung, Discord** = 3 streams Rémunération totale : 200 + 150 + 100 = **450€** **Question 3 : Code Python**def planning_stream(sponsors):
"""
sponsors : liste de tuples (nom, debut, fin, remuneration)
Retourne la liste des sponsors sélectionnés
"""
# Trier par heure de fin croissante
sponsors_tries = sorted(sponsors, key=lambda x: x[2])
selection = []
derniere_fin = 0
for nom, debut, fin, remuneration in sponsors_tries:
if debut >= derniere_fin:
selection.append((nom, debut, fin, remuneration))
derniere_fin = fin
return selection
# Exemple d'utilisation
sponsors = [
('Red Bull', 14, 17, 200),
('Logitech', 15, 18, 180),
('Samsung', 17, 19, 150),
('Razer', 18, 20, 120),
('Discord', 19, 21, 100),
('NordVPN', 20, 22, 90)
]
planning = planning_stream(sponsors)
total = sum(s[3] for s in planning)
print("Sponsors sélectionnés :")
for nom, debut, fin, remuneration in planning:
print(" ", nom, ":", debut, "h -", fin, "h (", remuneration, "€)")
print("Rémunération totale :", total, "€")
Exercice 5 ⭐⭐ : Réflexion
-
Dans l'exercice 4, on a maximisé le nombre de streams. Si on voulait maximiser la rémunération totale, l'algorithme glouton donnerait-il le même résultat ?
-
Parmi ces situations, lesquelles peuvent être résolues de manière optimale par un algorithme glouton ?
- Choisir les meilleurs joueurs pour une équipe FIFA (budget limité)
- Organiser l'ordre de visionnage de films sur Netflix (minimiser le temps total)
- Rendre la monnaie avec des pièces européennes
- Trouver le chemin le plus court dans Google Maps
Voir la correction
**Question 1 :** Non ! Pour maximiser la rémunération, l'algorithme glouton pourrait donner un résultat différent. Avec notre solution (Red Bull + Samsung + Discord) : 450€ Si on avait pris Red Bull (200€) + Razer (120€) + NordVPN (90€) : 410€ (moins bien) Mais que se passe-t-il si on prend Logitech (180€) + Discord (100€) = 280€ ? C'est pire. En fait, pour ce problème précis, la solution gloutonne par heure de fin est bonne, mais **maximiser la rémunération** est un problème différent (problème du sac à dos déguisé) qui ne se résout pas toujours de manière optimale avec un glouton. **Question 2 :** | Situation | Optimal avec glouton ? | |-----------|------------------------| | Équipe FIFA (budget) | Non (c'est un sac à dos) | | Ordre films Netflix | Ça dépend du critère... | | Monnaie européenne | Oui (système canonique) | | Google Maps | Non (Dijkstra n'est pas vraiment glouton au sens strict, mais utilise une approche similaire) |Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International