Algorithmes gloutons

Système monétaire

Définition

Un système monétaire est un tableau trié dans l'ordre croissant dont le premier élément est 1. L'unité 1 correspond à la plus petite division du système (pour le système monétaire euro, c'est le centime). Réaliser une somme dans un système monétaire, c'est trouver des pièces et des billets pour faire cette somme.

Réalisation d'une somme

Expliquer pourquoi une somme d'argent peut toujours être réalisée dans un système monétaire.

Le système Euro

Nous travaillerons avec ces systèmes:

• Les Euros actuels (en centimes)
• L'ancien système monétaire du royaume uni (en pence) définitivement abandonné le lundi 15 février 1971, jour baptisé Decimal Day.
  • 12 pence correspondaient à une pièce de 1 shilling.
  • 24 pence correspondaient à une pièce de 2 shilling.
  • 30 pence correspondait à une pièce de 1 half-crown.

EUROS = [1, 2, 5, 10, 20, 50, 1_00, 2_00, 5_00, 10_00, 20_00, 50_00]
RU_VIEUX = [1, 3, 6, 12, 24, 30]

Le problème du rendu de monnaie - CMP

Définition

Le problème CMP (Change-Making Problem) est celui de la réalisation d'une somme monétaire avec le nombre minimum de pièces (ou de billets).

Avant que cet algorithme soit intégré aux caisses enregistreuses, les caissières exécutaient tous les jours l'algorithme glouton permettant de rendre optimalement une somme d'argent avec le moins de pièces possibles.

Algorithme glouton

Définition

Un algorithme glouton est un procédé qui, à chaque étape, choisit la décision localement optimale et ne la remet jamais en question.

L'usage veut que le terme 'glouton' ne s'applique qu'aux problèmes d'optimisation.

Il est important de noter que, bien que les algorithmes gloutons soient simples et rapides, ils ne garantissent pas toujours la meilleure solution globale pour un problème d'optimisation donné. Cependant, dans de nombreux cas, ils fournissent une solution approchée suffisamment bonne dans un temps raisonnable.

Résolution gloutonne du CMP

Voici le choix optimal local par la méthode gloutonne:

Tant qu'on peut encore rendre, on rend toujours la plus grosse pièce qu'on peut rendre.

Complétez la fonction suivante en conséquence

SYSTEME = EUROS

def realiser_somme_glouton(somme: int, sys: list[int]) -> list[int]:
    """
    >>> realiser_somme_glouton(37, EUROS)
    [200, 20, 10, 5, 2]
    """
    assert 1 in sys

    res = []
    while ...:
        ...instructions...

    return res

Optimal?

Essayez de rendre 48 avec l'approche gloutonne dans le vieux système du royaume-uni.

• La solution renvoyée est-elle la solution optimale?
• Quelle est la solution optimale dans ce système?

Système monétaire canonique

On appelle canonique un système monétaire si et seulement si l'approche gloutonne renvoie la décomposition minimum de toute somme. Le système Euros est canonique. L'autre système ne l'est pas (il suffisait d'un contre-exemple pour le prouver).

Il existe des façons de résoudre CMP, que le système soit canonique ou non, que nous verrons l'année prochaine.

---

TODO: Ajouter Fractional Knapsack (FKP)