2-03. Programmation dynamique

On suppose donné un système monétaire. Un commerçant a à sa disposition un nombre illimité de pièces de ce système monétaire. Il doit rendre la monnaie à un client en utilisant un nombre minimal de pièces. Pour simplifier les choses, on suppose que les valeurs d'un système monétaire ainsi que la somme à rendre sont des entiers positifs.

Dans toute cette activité, on considèrera trois systèmes monétaires : le système européen, l'ancien système impérial britannique et un système imaginaire. Chacun de ces systèmes est représenté par une liste d'entiers, chacun de ces entiers correspondant à une valeur du système monétaire :

• euro = [50, 20, 10, 5, 2, 1]
• imperial = [30, 24, 12, 6, 3, 1]
• imaginaire = [9, 3, 2]

1. Approche gloutonne

On rappelle qu'une approche gloutonne une stratégie algorithmique qui consiste à trouver une solution à un problème en prenant le meilleur choix à chaque étape et sans revenir sur les choix précédents.

Dans le cas de l'algorithme du rendu de monnaie, on utilise la stratégie gloutonne suivante :

• on utilise la pièce qui a la plus grande valeur sans dépasser la somme à rendre,
• on actualise la somme à rendre en lui soustrayant cette valeur,
• on recommence ainsi jusqu'à ce que la somme à rendre soit égale à 0.

Implémentation

La fonction rendu_monnaie_glouton ci-dessous prend en paramètre un entier strictement positif somme_a_rendre correspondant à la somme à rendre et une liste systeme correspondant au système monétaire à utiliser pour rendre la monnaie. Elle renvoie une liste contenant la liste des valeurs à rendre en utilisant la stratégie gloutonne précédente.

		def rendu_monnaie_glouton(somme_a_rendre, systeme):
			rendu = []   # initialisation : la liste est vide
			for elem in systeme:  # parcours de la liste système
				while somme_à_rendre >= ...:
					somme_a_rendre = ...
					rendu.append(...)
			return rendu
	

Utiliser la fonction test_rendu_monnaie_glouton ci-dessous pour tester la validité de votre fonction.

		def test_rendu_monnaie_glouton:
			euro = [50, 20, 10, 5, 2, 1]
			imperial = [30, 24, 12, 6, 3, 1]
			imaginaire = [9, 3, 2]
			assert rendu_monnaie_glouton(49, euro) == [20, 20, 5, 2, 2]
			assert rendu_monnaie_glouton(49, imperial) == [30, 12, 6, 1]
			assert rendu_monnaie_glouton(49, imaginaire) == [9, 9, 9, 9, 9, 3]
			print("Tous les tests ont été réussis")
	

Analyse

On souhaite rendre la somme de 49 €.

1.1. La solution produite par l'algorithme glouton avec le système européen permet-elle de rendre cette somme ? Est-elle optimale ?

1.2. La solution produite par l'algorithme glouton avec l'ancien système impérial britannique permet-elle de rendre cette somme ? Est-elle optimale ?

1.3. La solution produite par l'algorithme glouton avec le système imaginaire permet-elle de rendre cette somme ? Est-elle optimale ?

2. Diviser pour régner

Pour obtenir la solution optimale, on peut utiliser un algorithme récursif qui explore toutes les sommes inférieures ou égales au rendu réalisables avec un ensemble de pièces donné et renvoie le nombre minimal de pièces (renvoie ∞ quand il n’y a pas de solution) :

		fonction rendu_monnaie_rec(somme_à_rendre, système)
			si somme_à_rendre = 0 : renvoyer 0
			nb ← +∞
			pour toute pièce p de système:
			|	si valeur de p ≤ somme_à_rendre:
			|	|	 nb ← minimum( nb, 1 + rendu_monnaie_rec(somme_à_rendre - p, système) )
			renvoyer nb
	

2.1. Décrire en quoi cette approche est une application de la méthode « diviser pour régner ».

Étude d’un exemple

La méthode proposé dans cette approche fonctionne en effectuant toutes les combinaisons possibles de pièces pour une certaine somme et à choisir celle qui comporte le moins de pièces. Examinons plus en détails les appels récursifs réalisés.

On considère le système de pièces imaginaire [9,3,2] et on fait fonctionner l'algorithme récursif précédent sur la somme 10.

2.2. Compléter l'arbre des appels récursifs de la fonction rendu_monnaie_rec ci-dessous.

2.3. Que constate-t-on en examinant cet arbre ?

3. Programmation dynamique

Comme on a pu le voir précédemment, la programmation récursive de la résolution du problème du rendu de monnaie permet d'obtenir la solution optimale mais elle nécessite de nombreux appels identiques. L'une des clés de la programmation dynamique est d'éviter ces calculs redondants.

Une idée pour éviter de recalculer plusieurs fois le même résultat est de mémoriser les résultats calculés dans un tableau dédié. On choisit de calculer tous les résultats des sous-problèmes, en commençant par les plus simples et en finissant par les plus compliqués, ce qui permet de supprimer la récursivité.

Dans notre exemple du rendu de monnaie pour la somme de 49 euros, il s'agit de calculer dans cet ordre toutes les solutions optimales pour les sommes allant de 0 à 49 € inclus.

On donne l'algorithme suivant :

		fonction rendu_monnaie_dyna(somme_à_rendre, système)
			nb ← tableau contenant les entiers de 0 à somme_à_rendre
			pour s allant de 1 à somme_à_rendre:
			|	pour toutes les pièces p du système:
			|	|	si p ≤ s:
			|	|	|	nb[s] ← minimum( nb[s], 1 + nb[s-p] )
			renvoyer nb[somme_à_rendre]
	

Un exemple « à la main »

On exécute l'instruction rendu_monnaie_dyna(5, [2, 1]).

3.1. Quel est la somme à rendre et quel est le système monétaire utilisé ?

3.2. Décrire les différentes étapes lors de l'exécution de cette instruction.

Implémentation en Python

3.3. Implémenter l’algorithme précédent en Python.

3.4. Exécuter l'instruction rendu_monnaie_dyna(10, [9, 3, 2]). La réponse est-elle correcte ? Pourquoi cela se produit-il ? Comment y remédier ?

Pour aller plus loin

La fonction précédente calcule le nombre de pièces correspondant à la solution optimale quand c’est possible, mais ne précise pas comment cette solution a été obtenue.

On propose ci-dessous une fonction permettant, non seulement de calculer le nombre de pièces utiles, mais aussi la combinaison des pièces à rendre et on gère également le cas où le rendu est impossible.

		def rendu_monnaie_dyna_combi(somme, systeme):
			'''
			Renvoie une liste minimale de pièces constituant la combinaison
			des pièces à rendre pour le rendu de la somme donnée avec le
			système de pièces donné.
			La fonction renvoie [-1] quand le rendu est impossible.
			'''
			combi = [[0 for k in range(s)] for s in range(0,somme+1)]
			for s in range(1,somme+1):
				for p in systeme:
					if p <= s:
						if len(combi[s]) > 1+len(combi[s-p]) or 0 in combi[s]:
							combi[s] = combi[s-p] + [p]
			if 0 in combi[somme]: # somme impossible à réaliser
				return [-1]
			return combi[somme]
	

3.5. Expliquer la ligne 8.

3.6. Expliquer le test de la ligne 11.

3.7. Que renvoie la fonction quand on l'exécute avec le système imaginaire et la somme 10 ? Expliquer.

			def rmd(somme, systeme):
				nb = [float('inf') for i in range(somme+1)]
				nb[0] = 0
				for s in range(1, somme+1):
					for p in systeme:
						if p <= s:
							nb[s] = min(nb[s], 1+nb[s-p])
				return nb[somme]