Rendu de monnaie

• Avec $\{1,2,5,10\}$, le glouton est optimal sur ces exemples : $18=10+5+2+1$ ($4$ pièces), $27=10+10+5+2$ ($4$), $39=10+10+10+5+2+2$ ($6$). Avec $\{1,3,4\}$ et $S=6$, il rend $4+1+1$ ($3$ pièces) alors que $3+3$ suffit ; pour $S=10$, il rend $4+4+1+1$ ($4$ pièces) au lieu de $4+3+3$ ($3$).
• La dernière pièce rendue est l'une des $p_i\le s$ ; le reste, $s-p_i$, est rendu avec un nombre minimum de pièces. Base : $N(0)=0$. Hérédité : $\forall s,1\le s<S+1$,

$$N(s)=1+\min \{N(s-p_i):0\le i<n,p_i\le s\},$$

avec $N(s)=+\infty$ si aucune pièce ne convient. C'est un sac avec répétitions où l'on minimise le nombre d'objets sous la contrainte d'une taille exactement égale à $s$. -

static int[] monnaie(int[] P, int S) {
    int[] N = new int[S + 1];                       // base : N[0] = 0
    for (int s = 1; s < S + 1; s++) {              // hérédité, s croissants
        N[s] = INF;
        for (int p : P)
            if (p <= s && N[s - p] + 1 < N[s]) N[s] = N[s - p] + 1;
    }
    return N;
}
static void apieces(int[] N, int[] P, int s) {
    // affiche une façon optimale de rendre s (précondition : N[s] < INF)
    if (s == 0) return;                             // rien à rendre
    for (int p : P)
        if (p <= s && N[s - p] + 1 == N[s]) {       // p peut être la dernière pièce
            apieces(N, P, s - p);                   // s - p a été rendu
            System.out.print(" " + p);              // puis p : s a été rendu
            return;
        }
}

pieces [1, 3, 4], S = 6 : glouton 3 piece(s), optimum 2 : 3 3
pieces [1, 3, 4], S = 10 : glouton 4 piece(s), optimum 3 : 4 3 3

nom : N
valeurs : 0 1 2 1 1 2 2 2 2 3 3
colorier : 10
vert : 0 4 7
fleches : 0->4:+4 4->7:+3 7->10:+3
legende : pièces 1, 3, 4 : N(10) = 3 avec 10 = 4 + 3 + 3

Le calcul est en $\Theta (nS)$, l'affichage en $\Theta (nS)$ au pire (au plus $S$ pièces, $n$ essais chacune).