Dans ce billet, j’ai eu l’envie de vous partager mon implémentation Java du très célèbre problème du rendu de monnaie dont voici l’énoncé : étant donné un système de monnaie, comment rendre de façon optimale une somme donnée, c’est-à-dire avec le nombre minimal de pièces et de billets ?
Par exemple, dans le système monétaire de l’Euro, la manière la plus optimale de rendre 6 euros consiste à rendre un billet de 5 € et une pièce de 1 €, même si d’autres combinaisons existent (ex : 3 x 2 € ou 6 x 1 €).

Dans le cas d’un système monétaire non canonique, utiliser un algorithme glouton ne donnera pas nécessairement un résultat optimal. Il est nécessaire de passer par la méthode algorithmique dite de programmation dynamique. Continuer la lecture →