Algorithmes gloutons
Exercice 1:
On dispose d’un ensemble d’objets dont on connaît, pour chacun, la masse.
On souhaite ranger l’ensemble de ces objets dans des boites identiques de telle manière que la somme des masses des objets contenus dans une boîte ne dépasse pas la capacité c de la boîte.
On souhaite utiliser le moins de boîtes possibles pour ranger cet ensemble d’objets.
Pour résoudre ce problème, on utilisera un algorithme glouton consistant à placer chacun
des objets dans la première boîte où cela est possible.
Par exemple, pour ranger dans des boîtes de capacité c = 5 un ensemble de trois objets
dont les masses sont représentées en Python par la liste [1, 5, 2], on procède de la
façon suivante :
• Le premier objet, de masse 1, va dans une première boite.
• Le deuxième objet, de masse 5, ne peut pas aller dans la même boite que le premier
objet car cela dépasserait la capacité de la boite. On place donc cet objet dans une
deuxième boîte.
• Le troisième objet, de masse 2, va dans la première boîte.
On a donc utilisé deux boîtes de capacité c = 5 pour ranger les 3 objets.
Compléter la fonction Python empaqueter(liste_masses, c) suivante pour qu’elle
renvoie le nombre de boîtes de capacité c nécessaires pour empaqueter un ensemble
d’objets dont les masses sont contenues dans la liste liste_masses.
On supposera que toutes les masses sont inférieures ou égales à c.
def empaqueter(liste_masses, c):
"""Renvoie le nombre minimal de boîtes nécessaires pour
empaqueter les objets de la liste liste_masses, sachant
que chaque boîte peut contenir au maximum c kilogrammes"""
n = len(liste_masses)
nb_boites = 0
boites = [ 0 for _ in range(n) ]
for masse in ...:
i = 0
while i < nb_boites and boites[i] + ... > c:
i = i + 1
if i == nb_boites:
...
boites[i] = ...
return ...
Exercice 2:
La fonction rendu_monnaie prend en paramètres deux nombres entiers positifs somme_due et somme_versee et elle permet de procéder au rendu de monnaie de la différence somme_versee – somme_due pour des achats effectués avec le système de pièces et billets de la zone Euro.
On utilise un algorithme glouton qui commence par rendre le maximum de pièces de plus grandes valeurs et ainsi de suite.
La fonction rendu_monnaie renvoie un tableau de type list contenant les pièces et billets qui composent le rendu.
Les valeurs possibles pour les pièces et billets sont [1, 2, 5, 10, 20, 50, 100, 200].
Ainsi, l’instruction rendu_monnaie(452, 500) renvoie le tableau [20, 20, 5, 2, 1].
En effet, la somme à rendre est de 48 euros soit 20 + 20 + 5 + 2 + 1.
Le code de la fonction rendu_monnaie est donné ci-dessous :
def rendu_monnaie(somme_due, somme_versee):
pieces = [1, 2, 5, 10, 20, 50, 100, 200]
rendu = ...
a_rendre = ...
i = len(pieces) - 1
while a_rendre > ... :
if pieces[i] <= a_rendre :
rendu.append(...)
a_rendre = ...
else :
i = ...
return rendu
Exemples:
>>> rendu_monnaie(700,700)
[]
>>> rendu_monnaie(102,500)
[200, 100, 50, 20, 20, 5, 2, 1]
Exercice 3:
Dans cet exercice on va montrer les limites d'un algorithme glouton, on cherche à obtenir 58 et on n’a droit qu’aux nombres 7, 14 et 23.
3.1 Écrire un algorithme glouton qui obtient ou se rapproche de cette somme en utilisant le moins de nombres possibles, l'algorithme devra renvoyer sa solution qui sera la solution exacte ou sa solution optimale (valeur inférieure la plus proche).
3.2 Votre algorithme glouton trouve-t-il la solution exacte?
3.3 Montrer ( avec un calcul manuel ) qu'il est possible d'obtenir la solution exacte avec les nombres 7, 14 et 23
Créé avec HelpNDoc Personal Edition: Avantages d'un outil de création d'aide