Correction Algorithmes gloutons

Le rendu de monnaie

Rendu à la main

Pour rendre 7€ :
- 1+1+1+1+1+1+1
- 2+1+1+1+1+1
- 2+2+1+1+1
- 2+2+2+1
- 5+1+1
- 5+2
La solution optimale est 5+2.

Pour rendre 263€ : 100 + 100 + 50 + 10 + 2 + 1
Pour rendre 264€ : 100 + 100 + 50 + 10 + 2 + 2

Algorithme

Le premier billet à rendre est celui de plus grande valeur.
il faut que :
- le billet doit avoir la plus grande valeur possible,
- la valeur du billet doit être plus petite que la somme restant à rendre.
une fois le billet rendu, on soustrait sa valeur à la somme restante.
le rendu est terminé quand la somme restante est devenue nulle
tant que la somme à rendre n'est pas nulle :
- prendre le billet de plus haute valeur possible
- si sa valeur est plus petite ( ou égale ! ) que la somme restant à rendre :
  - l'ajouter à la liste des billets à rendre
  - soustraire sa valeur à la somme restant à rendre
- sinon, passer au billet de valeur immédiatement inférieure.

Implémentation Python

On voit donc l'intérêt d'avoir la liste des billets et pièces triée dans l'ordre de valeur décroissante : ceux de plus grande valeur se trouvent donc en premier dans cette liste.

Pour "garder la trace" du billet/de la pièce en cours d'utilisation, on utilise une variable i qui contiendra l'indice de ce billet dans le tableau :

cette variable sera initialisée à 0, car on commence avec le billet le plus grand, donc le premier dans le tableau;
i n'est pas modifiée si on doit encore utiliser le même billet au rendu suivant;
on incrémente donc i uniquement lorsqu'il faut passer à un billet de plus petite valeur.


def rendu_glouton(monnaie, somme):
    """
    Fonction qui applique l'algorithme glouton de rendu de monnaie.
    Entrées :
        monnaie = le tableau des différents pièces et billets possibles (list)
        somme = la valeur de la somme à rendre (int)
    Sortie :
        le tableau de pièces et billets à rendre (list)
    """
    i = 0                             # indice dans le tableau du billet/de la pièce de plus grande valeur en cours d'utilisation
    rendu = []                        # tableau des billets et pièces à rendre
    while somme > 0:                  # tant que la somme à rendre n'est pas nulle,
        if monnaie[i] <= somme:       # si la valeur du billet/de la pièce courant(e) est plus petite ou égale à la somme restant à rendre,
            somme -= monnaie[i]       # alors on soustrait sa valeur de la somme à rendre,
            rendu.append(monnaie[i])  # et on ajoute ce billet/cette pièce à la liste du rendu.
        else:
            i += 1                    # sinon, on passe au billet/à la pièce suivant(e).
    return rendu

systeme = [100, 50, 20, 10, 5, 2, 1]

print(rendu_glouton(systeme, 7))    # [5, 2]
print(rendu_glouton(systeme, 263))  # [100, 100, 50, 10, 2, 1]
print(rendu_glouton(systeme, 264))  #[100, 100, 50, 10, 2, 2]

Approche alternative

Pour chaque billet et pièce en commençant par le plus grand, combien de chaque sont à rendre; pour déterminer ce nombre, une simple opération mathématique ( calcul du quotient, ou division euclidienne ) suffit.
Le calcul continue ensuite sur le reste de la somme à rendre :


def rendu_glouton_v2(monnaie, somme):
    rendu = []    
    for piece in monnaie:   
        nombre = somme // piece  # nombre de piece
        rendu += [piece]*nombre
        somme = somme % piece    # reste à rendre
    return rendu

Principes des algorithmes gloutons

Pour rendre 6€ avec le système [4, 3, 1] : avec l'algorithme glouton, on doit rendre [4, 1, 1], alors que le rendu optimal est [3, 3].
Pour rendre 8€ avec le système [10, 5, 2] : d'après l'algorithme glouton, on devrait d'abord rendre 5€, puis 2€ et on serait alors bloqué, le rendu n'aboutirait pas...
Il faudrait en fait rendre [2, 2, 2, 2], ce que ne donne pas l'algorithme glouton.

Un algorithme glouton ne donne donc pas toujours la solution optimale...cependant, dans le cas du rendu de monnaie, le système de billets et de pièces est généralement fait pour qu'il le soit !

Le problème du sac à dos

Résolution par force brute à la main

4 objets : 1 + 2 + 3 + 4 : 43kg, 1700€ NON
3 objets :
- 1+2+3 : 33kg, 1400€ NON
- 1+2+4 : 35kg, 1400€ NON
- 2+3+4 : 30kg, 1000€ OUI
2 objets :
- 1+2 : 25kg, 1100€ OUI
- 1+3 : 21kg, 1000€ OUI
- 1+4 : 23kg, 1000€ OUI
- 2+3 : 20kg, 700€ OUI
- 2+4 : 22kg, 700€ OUI
- 3+4 : 18kg, 600€ OUI
1 objet :
- 1 : 13kg, 700€ OUI
- 2 : 12kg, 400€ OUI
- 3 : 8kg, 300€ OUI
- 4 : 10kg, 300€ OUI

Le chargement optimal est donc 1 + 2 avec une valeur de 1100€.

Avec 40 objets :

2⁴⁰ = 1 x 10¹²
durée nécessaire : 1 x 10¹² x 10^-3 = 10⁹s, soit 10⁹/(365*24*3600) = 32 ans !

Il est donc effectivement inenvisageable d'étudier TOUTES les possibilités afin de trouver la solution optimale...

Implémentation Python

Calcul de la valeur massique


def calcule_gain(L):
    """
    Complète une liste d'objets avec la valeur massique de chacun des objets de la liste.
    Entrée :
        L = la liste des objets sous la forme d'un tableau de dictionnaires [{nom, masse, valeur, None}] ( list de dict)
    Sortie :
        la liste complétée avec la valeur massique calculée de chaque objet : [{nom, masse, valeur, valeur_massique}] (list de dict)
    """
    for objet in L:
        objet["val_mas"] = objet["valeur"]/objet["masse"]
    return L

liste_objets = [
    {"nom": "objet1", "masse": 13, "valeur": 700, "val_mas": None},
    {"nom": "objet2", "masse": 12, "valeur": 400, "val_mas": None},
    {"nom": "objet3", "masse": 8, "valeur": 300, "val_mas": None},
    {"nom": "objet4", "masse": 10, "valeur": 300, "val_mas": None}
    ]
    
liste_objets = calcule_gain(liste_objets)

Tri de la liste d'objets


def cle_tri(objet):
    return objet["val_mas"]

liste_objets.sort(key = cle_tri, reverse = True) # on trie par ordre de valeur massique DÉCROISSANTE

Application de l'algorithme


def sac_a_dos(Lobjets, msac):
    """
    Fonction qui implémente l'algorithme de résolution du problème du sac à dos.
    Entrée :
        Lobjets = liste des objets triés par valeur massique décroissante (list de dict)
        msac = masse maximale du sac (int)
    Sortie:
        la liste des objets à sélectionner, la somme totale de ces objets, et la masse totale du sac.
    """
    masse = 0      # masse totale
    somme = 0      # somme totale
    selection = [] # liste des objets à sélectionner

    for objet in Lobjets:
        if masse + objet["masse"] <= msac:
            masse += objet["masse"]
            somme += objet["valeur"]
            selection.append(objet["nom"])
    return selection, masse, somme
    
print(sac_a_dos(liste_objets, 30) # ["objet1", "objet2"], 25, 1100

Analyse de l'efficacité de l'algorithme

Une possibilité pour prendre l'algorithme en défaut :

objet 1 : masse = 1kg, valeur = 30€, valeur massique = 30/1 = 30€/kg
objet 2 : masse = 30kg, valeur = 300€, valeur massique = 300/30 = 10€/kg

Dans cette situation, l'algorithme choisirait l'objet 1, ce qui n'est pas la solution optimale.

Dans le cas du problème du sac à dos, l'algorithme glouton ne donne donc pas (forcément) la solution optimale, il faut en passer par d'autres méthodes pour obtenir celle-ci.

Planning de films

Tri des séances


def debut(seance): # tri par heure de début
    return seance[1]

def fin(seance):   # tri par heure de fin
    return seance[2]

def cle_duree(seance): # tri par durée
    return seance[2]-seance[1]			
   
# Exemples de tri : 
seances.sort(key=fin)               # par heure de fin croissante ( donc, fin le plus tôt )
seances.sort(key=fin, reverse=True) # par heure de fin décroissante ( donc, fin le plus tard )

Implémentation de l'algorithme


def planning(tab):
    planning = [tab[0]]
    t = tab[0][2]
    for i in range(1, len(tab)):
        if tab[i][1] >= t:
            planning.append(tab[i])
            t = tab[i][2]
    return planning


print("Fin le plus tôt :")
seances.sort(key = fin)
t1 = planning(seances)
affiche_intervalles(t1)

print("Début le plus tôt :")
seances.sort(key = debut)
t2 = planning(seances)
affiche_intervalles(t2)

print("Durée la plus courte :")
seances.sort(key = duree)
t3 = planning(seances)
affiche_intervalles(t3)

print("Fin le plus tard :")
seances.sort(key = fin, reverse = True)
t1 = planning(seances)
affiche_intervalles(t1)

print("Début le plus tard :")
seances.sort(key = debut, reverse = True)
t2 = planning(seances)
affiche_intervalles(t2)

print("Durée la plus longue :")
seances.sort(key = duree, reverse = True)
t3 = planning(seances)
affiche_intervalles(t3)

Résultat :


Fin le plus tôt :
t	:1   5    10   15   20  24
s8	:#
s4	: #
s2	:  ###
s5	:     #
s3	:      ##

Début le plus tôt :
t	:1   5    10   15   20  24
s8	:#
s4	: #
s2	:  ###
s5	:     #
s3	:      ##

Durée la plus courte :
t	:1   5    10   15   20  24
s8	:#
s4	: #
s11	:    #
s5	:     #
s3	:      ##

Fin le plus tard :
t	:1   5    10   15   20  24
s3	:      ##

Début le plus tard :
t	:1   5    10   15   20  24
s3	:      ##

Durée la plus longue :
t	:1   5    10   15   20  24
s1	:#######

On peut donc éliminer toutes les stratégies "le plus tard" ( on s'en doutait un peu...)

Stratégie optimale

Avec une liste de 15 séances :


Fin le plus tôt :
t	:1   5    10   15   20  24
s10	:   ###
s8	:         ##
s4	:            #
s14	:             #
s11	:                ####
s7	:                      #

Début le plus tôt :
t	:1   5    10   15   20  24
s10	:   ###
s2	:       ########
s9	:               #########

Durée la plus courte :
t	:1   5    10   15   20  24
s4	:            #
s14	:             #
s7	:                      #

→ la meilleure stratégie est donc de choisir les séances par heure de fin le plus tôt.