Correction Algorithmes gloutons

Le rendu de monnaie

Rendu à la main

1. 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
2. La solution optimale est 5+2.

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

Algorithme

1. Le premier billet à rendre est celui de plus grande valeur.
2. 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.
3. une fois le billet rendu, on soustrait sa valeur à la somme restante.
4. le rendu est terminé quand la somme restante est devenue nulle
5. 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]			
			

Principes des algorithmes gloutons

1. 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].
2. 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.

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