Un algorithme Greedy ou Glouton est un algorithme qui suit le principe de réaliser, étape par étape, un choix optimal local, afin d'obtenir un résultat optimal global.
Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.
Suivant le système de pièces, l'algorithme glouton est optimal ou pas.
Dans le système de pièces européen (en centimes : 1, 2, 5, 10, 20, 50, 100, 200), où l'algorithme glouton donne la somme suivante pour 37 : 20+10+5+2, on peut montrer que l'algorithme glouton donne toujours une solution optimale.
Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal.
| Label |
Tags |
Date |
| 11. Container With Most Water |
Array, Two Pointers, Greedy |
18-04-2024 |
| 334. Increasing Triplet Subsequence |
Array, Greedy |
26-02-2024 |
| 452. Minimum Number of Arrows to Burst Balloons |
Array, Greedy, Sorting |
18-03-2024 |
| 649. Dota2 Senate |
String, Greedy, Queue |
18-04-2024 |
| 948. Bag of Tokens |
Array, Greedy, Two Pointers, Sorting |
04-03-2024 |
| 1382. Balance a Binary Search Tree |
Divide and Conquer, Greedy, Tree, Depth-First Search, Binary Search Tree, Binary Tree |
26-06-2024 |
| 2285. Maximum Total Importance of Roads |
Greedy, Graph, Sorting, Heap (Priority Queue) |
28-06-2024 |
| 2486. Append Characters to String to Make Subsequence |
Two Pointers, String, Greedy |
03-06-2024 |
| 3016. Minimum Number of Pushes to Type Word II |
Hash Table, String, Greedy, Sorting, Counting |
06-08-2024 |
| 3075. Maximize Happiness of Selected Children |
Array, Greedy, Sorting |
09-05-2024 |
| 3081. Replace Question Marks in String to Minimize Its Value |
Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting |
22-03-2024 |