Le glouton et la dynamique ne rendent pas la même monnaie

Le glouton prend la plus grosse pièce possible tant qu'il peut : $6=4+1+1$, soit trois pièces.

L'optimum est $6=3+3$, soit deux pièces. Le glouton se trompe.

La récurrence est immédiate une fois le sous-problème posé. Soit $N[s]$ le nombre minimal de pièces pour rendre exactement la somme $s$ :

$$N[0]=0,N[s]=1+\underset{\begin{array}{c}p\in P\\ p\le s\end{array}}{\min }N[s-p](s\ge 1),$$

avec $N[s]=+\infty$ si aucune pièce ne convient.

/* Nombre minimal de pieces pour rendre s, ou -1 si c'est impossible.
   Preconditions : p[i] >= 1, k >= 1, s >= 0.
   Complexite : Theta(k*s) en temps, Theta(s) en memoire. */
int rendu(const int p[], int k, int s) {
    assert(k >= 1 && s >= 0);
    int n[s + 1];
    n[0] = 0;
    /* INVARIANT : pour tout t < c, n[t] est le minimum cherche
       (ou s+1, valeur sentinelle signifiant « impossible »). */
    for (int c = 1; c <= s; c = c + 1) {
        n[c] = s + 1;                            /* infini representable */
        for (int i = 0; i < k; i = i + 1) {
            if (p[i] <= c && n[c - p[i]] + 1 < n[c]) { n[c] = n[c - p[i]] + 1; }
        }
    }
    return (n[s] > s) ? -1 : n[s];
}

Mesure sur le système $\{1,3,4\}$, pour $s=0$ à $12$ :

s     0  1  2  3  4  5  6  7  8  9 10 11 12
N[s]  0  1  2  1  1  2  2  2  2  3  3  3  3

La ligne $s=6$ donne $2$, la ligne $s=10$ donne $3$ là où le glouton en donne $4$.

Le point de méthode. La sous-structure optimale tient ici : si une solution optimale pour $s$ utilise une pièce $p$, ce qu'elle fait du reste $s-p$ est nécessairement optimal (sinon on améliorerait le tout). Le glouton, lui, suppose davantage : que le premier choix local est celui d'une solution optimale. C'est vrai pour le système euro, c'est faux pour $\{1,3,4\}$. La dynamique n'a pas besoin de cette hypothèse, et c'est exactement ce qu'elle coûte plus cher : $\Theta (ks)$ au lieu de $\Theta (k)$.