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 €.

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.

systeme_monnaie_europeen = [500,200,100,50,20,10,5,2,1]

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_pieces = [] # liste des pièces à rendre
    i = 0 # indice de la pièce à rendre dans la liste systeme_monnaie
    while somme_a_rendre > 0: # tant qu'il reste quelque chose à rendre
        valeur = systeme_monnaie[i] # valeur de la pièce à rendre
        if valeur > somme_a_rendre: # la pièce a une valeur trop élevée
            i += 1 # on avance alors dans la liste
        else: # la pièce peut être rendue
            ... # on ajoute la pièce dans la liste des pièces à rendre
            ... # on met à jour la somme à 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.

rendu(7,systeme_monnaie_europeen)

rendu(463,systeme_monnaie_europeen)

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 ?

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 :

Max = 10 # contenance maximale du sac
liste_noms = ["A","B","C","D","E","F"] # liste des noms des objets
liste_masses = [7,6,4,3,2,1] # liste des masses des objets
liste_valeurs = [9100,6000,4800,2700,2800,200] # liste des valeurs des objets

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.

Question 6 : Exécuter la cellule ci-dessous pour trier la liste de l’objet le plus “efficace” à l’objet le moins “efficace”.

L_triee=sorted(L,reverse=True)

Question 7 : Le code ci-dessous met en œuvre l’algorithme glouton. Compléter les lignes en pointillés.

liste_objets = [] # liste des noms des objets rangés dans le sac
Somme_masses = 0 # somme des masses des objets déjà rangés
for i in range(len(L_triee)):
    if Max >= ... : # l'objet d'indice i peut être rangé
        liste_objets.append(...) # on range l'objet d'indice i
        Somme_masses += ... # on met à jour la somme des masses

Question 8: : En déduire la combinaison fournie par l’algorithme glouton et la masse totale de cette combinaison.

Question 9 : Modifier le code précédent afin de déterminer également la valeur totale de la combinaison trouvée.