7 = 5 + 2 = 5 + 1 + 1 = 2 + 2 + 2 + 1 = 2 + 2 + 1 + 1 + 1 = 2 + 1 + 1+ 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 +1
7 = 5 + 2 : on n'utilise que deux pièces La solution optimale est
Exercice 1 : problème du rendu de monnaie
!!! info le problème Un achat en espèces se traduit par un échange de pièces et de billets. Dans la zone euro, le système en vigueur, en mettant de côté les centimes d’euros, met à disposition des pièces ou billets de 1 €, 2 €, 5 €, 10 €, 20 €, 50 €, 100 €, 200 €, 500 €. Le problème du rendu de monnaie s’énonce alors de la façon suivante : en supposant que nous avons à notre disposition un nombre illimité de ces pièces ou billets, comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces ou billets ? !!!
Question 1 : Supposons que la somme à rendre est de 7 €. Faire la liste de toutes les façons de rendre une telle somme. Quelle est la façon optimale ?
Sans s’en rendre compte, tout individu met généralement en œuvre un algorithme glouton. Il choisit d’abord la pièce ou le billet de valeur maximale qu’il peut rendre, sans rendre trop évidemment ! Puis il réitère cela tant qu’il reste quelque chose à rendre.
Question 2 : Appliquer cette méthode pour déterminer la façon optimale de rendre 463 €.
463 = 200 + 200 + 50 + 10 + 2 + 1
Pour mettre en œuvre cet algorithme glouton en Python, on définit tout d’abord le système de monnaie via une liste contenant les valeurs des pièces et billets du système par valeurs décroissantes. Pour le système européen, on écrit par exemple l’instruction suivante.
= [500,200,100,50,20,10,5,2,1] systeme_monnaie_europeen
On utilise également une variable de type entier somme_a_rendre
initialement égale à la somme à rendre.
L’algorithme consiste alors à parcourir la liste précédente de gauche à droite. Pour chaque élément de cette liste, on vérifie qu’il est bien plus petit que la somme à rendre, auquel cas on le soustrait de la somme à rendre et on le stocke dans la liste des pièces et billets à rendre, sinon on passe à l’élément suivant. On s’arrête enfin lorsque la somme à rendre est égale à zéro.
Nous mettons l’ensemble du code dans une fonction qui prend pour arguments la somme à rendre et le système de monnaie, puis renvoie la liste des pièces ou billets à rendre.
def rendu(somme_a_rendre, systeme_monnaie):
= [] # liste des pièces à rendre
liste_pieces = 0 # indice de la pièce à rendre dans la liste systeme_monnaie
i while somme_a_rendre > 0: # tant qu'il reste quelque chose à rendre
= systeme_monnaie[i] # valeur de la pièce à rendre
valeur if valeur > somme_a_rendre: # la pièce a une valeur trop élevée
+= 1 # on avance alors dans la liste
i else: # la pièce peut être rendue
# on ajoute la pièce dans la liste des pièces à rendre
liste_pieces.append(valeur) = somme_a_rendre - valeur # on met à jour la somme à rendre
somme_a_rendre return liste_pieces
Question 3 : Compléter les deux lignes en pointillés du code précédent, puis exécuter les cellules ci-dessous pour tester le code.
7,systeme_monnaie_europeen) rendu(
[5, 2]
463,systeme_monnaie_europeen) rendu(
[200, 200, 50, 10, 2, 1]
Exercice 2 : Problème du sac à dos
On dispose d’objets ayant chacun une masse et une valeur en euros, et d’un sac ne pouvant supporter plus d’une certaine masse. Il s’agit alors de remplir le sac en maximisant la valeur totale des objets et sans dépasser la masse maximale. Ce problème, malgré sa simplicité, est un problème majeur d’optimisation.
Supposons que l’on dispose d’un sac de contenance maximale 30 kg et quatre objets A, B, C et D dont les caractéristiques sont les suivantes :
Objet | A | B | C | D |
---|---|---|---|---|
Masse | 13 kg | 12 kg | 8 kg | 10 kg |
Valeur | 70 € | 40 € | 30 € | 30 € |
Question 4 : Calculer ci-dessous la liste des rapports Valeurs/Masse \(\frac{v_i}{m_i}\), appelés efficacité de chaque objet. L’algorithme glouton que nous proposons consiste alors à classer les objets dans l’ordre décroissant de leur efficacité. On remplit ensuite le sac en prenant les objets un à un dans cet ordre, tant que le sac peut encore les contenir. Déterminer la combinaison d’objets fournie par cet algorithme. Quel est la valeur totale de cette combinaison ?
70/13 = 5.4
A : 40/12 = 3.3
B : 30/8 = 3.75
C : 30/10 = 3
D :
> C > B > D
Classement : A
'objet A de masse 13 kg, la sac peut encore contenir 30 - 13 = 17 kg.
On choisit lOn choisit l'objet C de masse 8 kg, le sac peut encore contenir 17 - 8 = 9 kg.
'est terminé.
Les objets B et D sont trop lourds, cLa valeur totale de cette combinaison (A, C) est égale à 100 €.
Pour mettre en œuvre l’algorithme glouton que nous venons d’étudier pour le problème du sac à dos, nous créons tout d’abord une variable Max
contenant la capacité maximale (en kilogrammes) du sac. Nous créons ensuite trois listes liste_noms
, liste_masses
et liste_valeurs
qui contiennent respectivement les noms, masses et valeurs de chacun des objets.
Considérons un sac de contenance maximale 10 kg et des objets dont les caractéristiques sont les suivantes :
Objet | A | B | C | D | E | F |
---|---|---|---|---|---|---|
Masse | 7 kg | 6 kg | 4 kg | 3 kg | 2 kg | 1 kg |
Valeur | 9100 € | 6000 € | 4800 € | 2700 € | 2800 € | 200 e |
Nous écrivons alors les instructions suivantes :
= 10 # contenance maximale du sac
Max = ["A","B","C","D","E","F"] # liste des noms des objets
liste_noms = [7,6,4,3,2,1] # liste des masses des objets
liste_masses = [9100,6000,4800,2700,2800,200] # liste des valeurs des objets liste_valeurs
Question 5 : Créer une liste L
dont le i-ème élément est une liste contenant l’efficacité du i-ème élément, son nom, sa masse et sa valeur. Vérifier que L contient bien ce que l’on veut.
= [[liste_valeurs[i]/liste_masses[i], liste_noms[i], liste_masses[i], liste_valeurs[i]] for i in range(len(liste_noms))]
L print(L)
[[1300.0, 'A', 7, 9100], [1000.0, 'B', 6, 6000], [1200.0, 'C', 4, 4800], [900.0, 'D', 3, 2700], [1400.0, 'E', 2, 2800], [200.0, 'F', 1, 200]]
Question 6 : Exécuter la cellule ci-dessous pour trier la liste de l’objet le plus “efficace” à l’objet le moins “efficace”.
=sorted(L,reverse=True)
L_trieeprint(L_triee)
[[1400.0, 'E', 2, 2800], [1300.0, 'A', 7, 9100], [1200.0, 'C', 4, 4800], [1000.0, 'B', 6, 6000], [900.0, 'D', 3, 2700], [200.0, 'F', 1, 200]]
Question 7 : Le code ci-dessous met en œuvre l’algorithme glouton. Compléter les lignes en pointillés.
= [] # liste des noms des objets rangés dans le sac
liste_objets = 0 # somme des masses des objets déjà rangés
Somme_masses for i in range(len(L_triee)):
if Max >= Somme_masses : # l'objet d'indice i peut être rangé
1]) # on range l'objet d'indice i
liste_objets.append(L_triee[i][+= L_triee[i][2] # on met à jour la somme des masses Somme_masses
Question 8: : En déduire la combinaison fournie par l’algorithme glouton et la masse totale de cette combinaison.
print(liste_objets)
['E', 'A', 'C']
Question 9 : Modifier le code précédent afin de déterminer également la valeur totale de la combinaison trouvée.
= [] # liste des noms des objets rangés dans le sac
liste_objets = 0 # somme des masses des objets déjà rangés
Somme_masses = 0
valeur_totale for i in range(len(L_triee)):
if Max >= Somme_masses : # l'objet d'indice i peut être rangé
1]) # on range l'objet d'indice i
liste_objets.append(L_triee[i][+= L_triee[i][2] # on met à jour la somme des masses
Somme_masses = valeur_totale + L_triee[i][3]
valeur_totale
print("Liste des objets dans le sac : ", liste_objets)
print("Valeur totale de la combinaison trouvée : ", valeur_totale)
Liste des objets dans le sac : ['E', 'A', 'C']
Valeur totale de la combinaison trouvée : 16700