Aller au contenu

23 Exos Algorithmes gloutons

Principe de la variante fractionnaire⚓︎

À partir d’une liste, dont les éléments sont des triplets [numéro, valeur, poids], on va remplir le sac à dos jusqu’à saturation. Plaçons-nous dans le cadre du tri par rapports valeur/poids. Voici les différentes étapes de l’algorithme :

  1. Calculer les rapports valeur/poids de chaque objet et, dans la liste, ajouter ce rapport à chaque objet.
  2. Trier la liste par ordre décroissant de rapports.
  3. Parcourir tous les éléments de la liste et ajouter au sac à dos ceux dont le poids, cumulé au poids des objets déjà dans le sac, est inférieur ou égal à la capacité totale du sac.
  4. Lorsque la capacité totale est dépassée, cela signifie, soit que le sac est plein, soit que l’objet est trop lourd pour être inséré intégralement dans le sac.
  5. Dans ce dernier cas, ajouter la fraction de l’objet nécessaire pour atteindre la capacité maximale du sac.
  6. Retourner la liste finale des objets se trouvant dans le sac ainsi que la valeur totale de ces objets.

Exercice 1⚓︎

  1. Programmer l’algorithme précédent en Python puis le tester sur la liste d’objets précédente (vous pouvez compléter la trame proposée ci-dessous). On décide ici d'utiliser les listes ['nom', valeur, poids] pour représenter les objets. On pourrait aussi utiliser des dictionnaires...
  2. Prouver que ce programme termine.
  3. Déterminer la complexité temporelle de ce programme.
  4. Déterminer la complexité en mémoire de ce programme.
🐍 Script Python
def sac_a_dos_frac(poidsmax, objets):
    """ La fonction a deux paramètres : le poids maximal que peut supporter le sac à dos et une liste d'objets. Chaque objet a un nom, une valeur, un poids et est donc représenté par une liste de longueur 3. Cette fonction renvoie la liste des objets correspondant à la valeur maximale et ne dépassant pas le poids maximal que peut supporter le sac."""

    assert type(poidsmax) == int or type(poidsmax) == float, "Le poids maximal du sac à dos doit être un nombre"
    assert type(objets) == list, "Entrer les objets sous forme d'une liste de listes [[objet 1, valeur1, poids1], [objet2, valeur2, poids2], ..., [,,]]"

    # on calcule le rapport (valeur/poids) pour chaque objet et on met à jour la liste de départ en lui ajoutant cette nouvelle donnée pour chaque objet (qui devient désormais une liste de longueur 4 du type ['nom', valeur, poids, rapport])
    for objet in objets:
        rapport = #... À compléter
        objet.append(rapport)

    # on range cette liste par ordre décroissant des rapports
    objets.sort(key = lambda x: x[3], reverse = True)

    # on initialise trois variables
    poidsactuel = 0 # représente le poids du sac après insertion d'un nouvel objet
    valeuractuelle = 0 # représente la valeur contenue dans le sac après insertion d'un nouvel objet
    solution = [] # représente la liste des objets insérés dans le sac

    # on parcourt un par un les objets de la liste triée
    for objet in objets:
        if poidsactuel + objet[2] < poidsmax: # on teste si le nouvel objet a un poids lui permettant d'être inséré dans le sac à dos
            #... À compléter # si c'est le cas, on met à jour le poids du sac
            #... À compléter # on met à jour la valeur totale
            #... À compléter # et on l'insère dans le sac
        elif poidsactuel + objet[2] == poidsmax: # on teste si le nouvel objet a un poids lui permettant d'être inséré dans le sac à dos
            #... À compléter # si c'est le cas, on met à jour le poids du sac
            #... À compléter # on met à jour la valeur totale
            #... À compléter # et on l'insère dans le sac
            break # on ne passe pas à l'objet suivant car le sac à dos a atteint son poids maximal
        else: # le poids du nouvel objet dépasse le poids restant : on va en prendre une fraction pour atteindre exactement le poids maximal du sac
            valeur_frac_dernier_objet = #... À compléter
            poids_frac_dernier_objet = #... À compléter
            valeuractuelle += #... À compléter
            solution.append([objet[0], valeur_frac_dernier_objet, poids_frac_dernier_objet, objet[3]])
            break # on ne passe pas à l'objet suivant car le sac à dos a atteint son poids maximal

    # on renvoie la liste des objets dérobés par le voleur et la valeur totale correspondante
    return solution, valeuractuelle


# Testons notre fonction sur l'exemple du cours
p = 30
objets = [["A", 700, 13], ["B", 400, 12], ["C", 300, 6], ["D", 300, 10], ["E", 500, 12], ["F", 200, 14]]
objets_derobes, valeur_derobee = sac_a_dos_frac(p, objets)
print("La liste des objets dérobés est la suivante : \n" + str(objets_derobes))
print("Pour une valeur total de : " + "{:,}".format(valeur_derobee).replace(',', ' ') + " euros.")

Exercice 2⚓︎

  1. Adapter le programme ci-dessus à la variante entière du problème du sac à dos (on pourra compléter la trame proposée ci-dessous).
  2. Quelle solution nous donne-t-il sur l’exemple précédent ?
  3. Le tester pour la liste d’objets [['A', 165, 3], ['B', 100, 2], ['C', 100, 2]] et un poids maximal de \(4\) kg. La solution renvoyée est-elle optimale ?
🐍 Script Python
def sac_a_dos_0_1(poidsmax, objets):

    for objet in objets:
       #... À compléter
       #... À compléter

    objets.sort(key = lambda x: x[3], reverse = True)

    poidsactuel = 0
    valeuractuelle = 0
    solution = []

    for objet in objets:
        if #... À compléter:
            #... À compléter
            #... À compléter
            #... À compléter

    return solution, valeuractuelle

# Testons notre fonction sur l'exemple du cours
print("Exemple du cours : ")
p = 30
objets = [["A", 700, 13], ["B", 400, 12], ["C", 300, 6], ["D", 300, 10], ["E", 500, 12], ["F", 200, 14]]
objets_derobes, valeur_derobee = sac_a_dos_0_1(p, objets)
print("La liste des objets dérobés est la suivante : \n" + str(objets_derobes))
print("Pour une valeur total de : " + "{:,}".format(valeur_derobee).replace(',', ' ') + " euros.")

# Testons notre fonction sur l'exemple de la question 3
print("Exemple de la question 3 : ")
p = 4
objets = [['A', 165, 3], ['B', 100, 2], ['C', 100, 2]]
objets_derobes, valeur_derobee = sac_a_dos_0_1(p, objets)
print("La liste des objets dérobés est la suivante : \n" + str(objets_derobes))
print("Pour une valeur total de : " + "{:,}".format(valeur_derobee).replace(',', ' ') + " euros.")

Exercice 3⚓︎

En vous inspirant de ce TP, écrire un algorithme glouton permettant de résoudre le problème suivant, dit du « rendu de monnaie ».

Étant donné le système monétaire suivant [200, 100, 50, 20, 10, 5, 2, 1] où chacun des nombres de la liste est une pièce exprimée en centimes d’euros, comment rendre la monnaie de \(6,78\) euros de façon optimale, c’est-à-dire avec le nombre minimal de pièces ?