Implémentation Java de l’algorithme de rendu de monnaie par programmation dynamique

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.

Voici l’implémentation Java récursive par programmation dynamique de rendu de monnaie :

Le test unitaire JUnit associé valide différents cas de tests et documente son utilisation :

Plus le système monétaire est dense et plus le montant à rendre est élevé, plus il y’a de chance que la récursivité provoque des débordements de pile d’appel (je vous invite à tester le test annoté avec @Ignore). Passer par une impléemntation itérative permettrait de résoudre ce problème.

Pour complexifier le problème, on pourrait tenir compte du nombre de pièces disponibles dans la caisse et adapter le rendu de monnaie en conséquences. La mise en cache des résultats intermédiaires ne serait alors plus possible.

Références :

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *