Rendu optimal exhaustif

let rec rendu_min pieces montant =
  if montant = 0 then 0
  else begin
    let infini = montant + 1 in     (* borne : jamais plus de 'montant' pièces (pièce 1) *)
    let meilleur = ref infini in
    let rec essaie l =
      match l with
      | [] -> ()
      | p :: reste ->
          if p <= montant then begin
            let r = rendu_min pieces (montant - p) in
            if 1 + r < !meilleur then meilleur := 1 + r
          end;
          essaie reste
    in
    essaie pieces;
    !meilleur
  end

On essaie chaque pièce comme premier choix, et l'on garde le meilleur sous-rendu : c'est l'optimum, mais au prix d'une explosion (le même montant est recalculé maintes fois — la mémoïsation du chapitre 8, ou la programmation dynamique du chapitre suivant, y remédient).