(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) (* Programmation dynamique Rendu de monnaie : étant donné un système monétaire `coins`, par exemple `coins = { 1, 2, 5, 10, 20, 50 }`, quel est le plus petit nombre de billets et de pièces pour former la somme `s` ? *) (* version récursive, exponentielle *) let change_rec (coins: int array) (s: int) : int = if coins = [||] || coins.(0) <> 1 then invalid_arg "change_rec"; let rec change i s = if i = 0 then s else if coins.(i) > s then change (i-1) s else min (change (i-1) s) (1 + change i (s - coins.(i))) in change (Array.length coins - 1) s (* calcul par mémoïsation *) let change_memo (coins: int array) (s: int) : int = if coins = [||] || coins.(0) <> 1 then invalid_arg "change_memo"; let memo = Hashtbl.create 16 in let rec change i s = try Hashtbl.find memo (i, s) with Not_found -> let v = if i = 0 then s else if coins.(i) > s then change (i-1) s else min (change (i-1) s) (1 + change i (s - coins.(i))) in Hashtbl.add memo (i, s) v; v in change (Array.length coins - 1) s (* calcul de bas en haut *) let change_dp (coins: int array) (s: int) : int = if coins = [||] || coins.(0) <> 1 then invalid_arg "change_dp"; let n = Array.length coins in let m = Array.make_matrix n (1 + s) 0 in for s' = 1 to s do m.(0).(s') <- s' done; for i = 1 to n - 1 do for s' = 1 to s do m.(i).(s') <- if coins.(i) > s' then m.(i-1).(s') else min m.(i-1).(s') (1 + m.(i).(s' - coins.(i))) done; done; m.(n-1).(s) (* avec la solution, c'est-à-dire le tableau des pièces utilisées *) let change_sol (coins: int array) (s: int) : int array = if coins = [||] || coins.(0) <> 1 then invalid_arg "change_sol"; let n = Array.length coins in (* on commence exactement comme dans change_dp *) let m = Array.make_matrix n (1 + s) 0 in for s' = 1 to s do m.(0).(s') <- s' done; for i = 1 to n - 1 do for s' = 1 to s do m.(i).(s') <- if coins.(i) > s' then m.(i-1).(s') else min m.(i-1).(s') (1 + m.(i).(s'-coins.(i))) done; done; (* puis on reconstruit la solution à partir de m *) let sol = Array.make n 0 in let i = ref (n-1) in let s' = ref s in while !s' > 0 do if m.(!i).(!s') = m.(!i-1).(!s') then decr i else ( sol.(!i) <- 1 + sol.(!i); s' := !s' - coins.(!i) ) done; sol