Trouver, pour le système [6, 4, 1] , toutes les sommes de 1 à 50 pour…

Il faut d'abord savoir ce qu'est l'optimum — donc écrire une résolution exhaustive, qui essaie toutes les décompositions :

def optimal(somme, pieces):
    """Nombre MINIMAL de pieces, par exploration exhaustive."""
    meilleur = [None]

    def explorer(reste, i, n):
        if reste == 0:
            if meilleur[0] is None or n < meilleur[0]:
                meilleur[0] = n
            return
        if i >= len(pieces) or (meilleur[0] is not None and n >= meilleur[0]):
            return                       # elagage : cette branche ne peut plus gagner
        p = pieces[i]
        for k in range(reste // p, -1, -1):
            explorer(reste - k * p, i + 1, n + k)

    explorer(somme, 0, 0)
    return meilleur[0]

Le résultat, mesuré.

BIZARRE = [6, 4, 1]
manques = [s for s in range(1, 51)
           if len(rendu_monnaie(s, BIZARRE)) > optimal(s, BIZARRE)]
assert manques == [8, 9, 14, 15, 20, 21, 26, 27, 32, 33, 38, 39, 44, 45, 50]
assert len(manques) == 15

Quinze sommes sur cinquante — c'est le chiffre annoncé par la figure du cours, retrouvé ici par le calcul. Et la régularité saute aux yeux : les défauts vont par paires $(8,9)$, $(14,15)$, $(20,21)$, …, espacées de $6$. Les écarts successifs sont $1,5,1,5,1,5,\dots$

ecarts = [manques[i + 1] - manques[i] for i in range(len(manques) - 1)]
assert ecarts == [1, 5, 1, 5, 1, 5, 1, 5, 1, 5, 1, 5, 1, 5]

Pourquoi cette période $6$. Le glouton prend une pièce de $6$ dès que la somme l'atteint ; il se trompe exactement quand deux pièces de $4$ auraient mieux valu, c'est-à-dire pour $8=4+4$ et $9=4+4+1$ — puis pour ces mêmes sommes augmentées d'un multiple de $6$, où l'erreur se reproduit à l'identique après les pièces de $6$ prises au début.

Le système européen, lui, est canonique.

euro_manques = [s for s in range(1, 201)
                if len(rendu_monnaie(s, EURO)) > optimal(s, EURO)]
assert euro_manques == []

Aucun défaut sur les deux cents premières sommes. C'est une propriété du jeu de valeurs, pas de l'algorithme — et c'est bien pour cela que le glouton du rendu de monnaie « marche » dans la vie courante : les pièces ont été choisies pour, non l'inverse.