Reconstruire les pièces du rendu

let pieces_du_rendu pieces montant =
  let infini = montant + 1 in
  let m = Array.make (montant + 1) infini in
  let choix = Array.make (montant + 1) (-1) in   (* pièce choisie pour la somme s *)
  m.(0) <- 0;
  for s = 1 to montant do
    List.iter (fun p ->
      if p <= s && m.(s - p) + 1 < m.(s) then begin
        m.(s) <- m.(s - p) + 1;
        choix.(s) <- p
      end
    ) pieces
  done;
  if m.(montant) = infini then None
  else
    let rec remonte s = if s = 0 then [] else choix.(s) :: remonte (s - choix.(s)) in
    Some (remonte montant)

On mémorise, pour chaque somme s, la pièce choix.(s) qui a réalisé l'optimum. La reconstruction part de montant et soustrait à chaque étape la pièce choisie, jusqu'à 0. C'est le schéma général : une table annexe des choix permet de retracer la solution.