Probleme – Le rendu de monnaie : quand le glouton est-il optimal ?

1. Le calcul exact. On note $d(k)$ le nombre minimal de pièces pour rendre $k$.

(* Nombre minimal de pièces pour rendre s, ou None si c'est impossible.
   Précondition : pièces > 0, s >= 0. Complexité : Theta(s * |pièces|).
   INVARIANT : après le tour k, d.(j) est exact pour tout j <= k. *)
let optimum pieces s =
  let d = Array.make (s + 1) max_int in
  d.(0) <- 0;
  for k = 1 to s do
    List.iter (fun c ->
      if c <= k && d.(k - c) <> max_int && d.(k - c) + 1 < d.(k)
      then d.(k) <- d.(k - c) + 1) pieces
  done;
  if d.(s) = max_int then None else Some d.(s)

Correction : toute solution optimale pour $k$ emploie au moins une pièce $c$, et le reste $k-c$ est rendu de façon optimale — sans quoi on l'améliorerait. D'où $d(k)=1+{\min }_{c\le k}d(k-c)$, ce que la boucle calcule. C'est la sous-structure optimale du chapitre chap:dynamique.

2. Le test de canonicité. Un système est canonique si le glouton donne l'optimum pour toute somme. Le test consiste donc à comparer les deux fonctions :

(* Nombre de pièces rendues par le glouton, ou None s'il se bloque.
   Précondition : pièces > 0, s >= 0. Complexité : Theta(|pièces| log |pièces| + s). *)
let glouton_monnaie pieces s =
  let p = Array.of_list (List.sort (fun a b -> compare b a) pieces) in
  let reste = ref s and n = ref 0 in
  Array.iter (fun c -> while !reste >= c do reste := !reste - c; incr n done) p;
  if !reste = 0 then Some !n else None

(* Vrai si le glouton est optimal pour toute somme de 1 à borne. *)
let canonique_jusqua pieces borne =
  let ok = ref true in
  for s = 1 to borne do
    if glouton_monnaie pieces s <> optimum pieces s then ok := false done;
  !ok

Mesuré, avec la borne $c_k+c_{k-1}$ où $c_k$ et $c_{k-1}$ sont les deux plus grosses pièces :

Aucun système n'a jamais échoué au-delà de sa borne : les recherches ont été poussées jusqu'à $S=3000$.

3. Pourquoi une borne suffit. C'est le théorème de Kozen et Zaks : si un système n'est pas canonique, son plus petit contre-exemple est strictement inférieur à $c_k+c_{k-1}$. L'idée en est la suivante — soit $S$ le plus petit contre-exemple. Si $S\ge c_k+c_{k-1}$, alors le glouton et l'optimum emploient tous deux au moins une pièce $c_k$ : on peut la retirer des deux et obtenir un contre-exemple plus petit, contradiction. Le cas $S<c_k+c_{k-1}$ est le seul possible.

Ce que ce théorème change. Sans lui, « le glouton est-il optimal sur ce système ? » est une question sur une infinité de sommes, donc indécidable par simple essai. Avec lui, elle se tranche par un calcul fini, en $\Theta ((c_k+c_{k-1})\cdot |\text{pieˋces}|)$ — quelques microsecondes pour un système monétaire réel.

Et c'est la bonne façon de conclure le chapitre. Le cours dit : « un glouton se démontre, ou ne s'emploie pas ». Ce problème montre le troisième terme de l'alternative, souvent le plus utile en pratique : on peut parfois décider mécaniquement si un glouton est correct, sans le démontrer à la main ni se contenter d'un essai. C'est le meilleur des trois mondes, et cela ne s'obtient qu'en démontrant, une fois, un théorème sur le problème lui-même.