(* Exercice 1 *)

(* Q1 *)

(* À chaque position i entre 1 et n-1, on choisit si on découpe ou non.
 * Donc 2^{n-1} découpes possibles.
 *
 * Si on avait essayé de compter en éliminant les doublons, on serait ramené à
 * compter ce qu'on appelle le nombre de partitions d'un entier n, qui est un
 * problème beaucoup plus compliqué :
 * https://fr.wikipedia.org/wiki/Partition_d%27un_entier *)

(* Q2 *)

(* Tout d'abord : r_0 = 0 
 * Ensuite, si on note i l'endroit de la première découpe, le revenu maximal
 * vaudra alors p_i + r_{n-i}. 
 * Il faut prendre le max de ces valeurs, d'où :
 * r_n = max { p_i + r_{n-i} | 0 < i <= n } *)

(* Q3 *)

(* r va être un tableau stockant des couples (r_n,im) où im est la valeur de i
 * où le max est atteind dans la formule d'avant, ce qui va être utile pour
 * renvoyer la découpe associée *)

let calculeR p =
  let n = Array.length p in
  let r = Array.make (n+1) (0,0) in
  for k=1 to n do
    let m = ref 0 in (* on cherche le max *)
    let im = ref 0 in (* et l'indice associé *)
    for i=1 to k do
      let x = (p.(i-1) + fst r.(k-i)) in
      if !m < x then
        begin
          m := x ;
          im := i
        end
    done ;
    r.(k) <- (!m,!im)
  done ;
  (* on cherche maintenant la découpe associée *)
  let rec decoupe k acc = match snd r.(k) with
    | i when i=k -> i::acc (* c'est la dernière découpe *)
    | i -> decoupe (k-i) (i::acc)
  in fst r.(n), decoupe n []
;;

calculeR [|1;5;8;9;10;15;17|] ;;

(* Q4 *)

(* Complexité temporelle : O(n^2) pour le calcul de r, puis O(n) pour decoupe,
 * soit O(n^2) au total.
 * Complexité spatiale : O(n) *)

(* Exercice 2 *)

(* Q1 *)

let monnaie_glouton p x =
  let n = Array.length p in
  let rec monnaie x i acc = (* on essaye de rendre x avec la i-ème pièce *)
    match x with 
    | 0 -> acc
    | _ when x>=p.(i) -> monnaie (x-p.(i)) i (p.(i)::acc)
    | _ -> monnaie x (i-1) acc
  in monnaie x (n-1) []
;;

monnaie_glouton [|1;2;5;10;20;50|] 139 ;;

(* Q2 *)

(* Soit on utilise la i-ème pièce, soit on ne le fait pas *)

(* Q3/4 *)

let monnaie_dyna p x =
  let n = Array.length p in
  let s = Array.make_matrix n (x+1) 0 in 
  for k=1 to x do
    if k-p.(0)>=0 then
      s.(0).(k) <- 1 + s.(0).(k-p.(0))
    else
      s.(0).(k) <- max_int (* c'est le plus grand entier représentable en OCaml *)
  done ;
  for i=1 to (n-1) do
    for k=1 to x do
      if k-p.(i)<0 then 
        s.(i).(k) <- s.(i-1).(k)
      else
      s.(i).(k) <- min (1 + s.(i).(k-p.(i))) s.(i-1).(k)
    done ;
  done ;
  (* pour Q3, renvoyer s.(n-1).(x) *)
  let rec remonte i k acc = match k-p.(i) with
    | _ when k=0 -> acc
    | k' when k'<0 -> remonte (i-1) k acc
    | k' when i=0 -> remonte i k' (p.(i)::acc)
    | k' when s.(i-1).(k) < 1+s.(i).(k') -> remonte (i-1) k acc
    | k' -> remonte i k' (p.(i)::acc)
  in remonte (n-1) x []
;;

monnaie_dyna [|1;3;4|] 6 ;;

(* Exercice 3 *)

(* Q1 *)

(* la partie qui n'est pas immédiate est l'inégalité triangulaire.
 * Si on a 3 mots u, v et w, et s'il faut d(u,v) modifs pour faire u -> v, et
 * d(v,w) modifs pour faire v -> w, alors en faisant toutes ces modifs bout à
 * bout, on va faire u -> v -> w en d(u,v) + d(v,w) étapes.
 * D'où d(u,w) <= d(u,v) + d(v,w) *)

(* Q2 *)

(* cas de base :
 * si i=0, il faut focément faire j insertions, donc d(0,j) = j
 * de même, d(i,0) = i
 * récurrence. Pour obtenir d(i,j) on peut :
 * * * partir des modifs pour d(i-1,j) et gérer la dernière lettre --> d(i-1,j)+1
 * * * partir des modifs pour d(i,j-1) et gérer la dernière lettre --> d(i,j-1)+1
 * * * partir des modifs pour d(i-1,j-1) et :
 * * * * * ne rien faire si les dernières lettres sont les mêmes --> d(i-1,j-1)
 * * * * * gérer la dernière lettre sinon --> d(i-1,j-1)+1
 * Il faut alors prendre le min de ces 3 cas *)

(* Q3 *)

let levenshtein u v =
  let lu = String.length u in
  let lv = String.length v in
  let d = Array.make_matrix (lu+1) (lv+1) 0 in
  for i=1 to lu do
    d.(i).(0) <- i
  done ;
  for j=1 to lv do
    d.(0).(j) <- j
  done ;
  for i=1 to lu do
    for j=1 to lv do
      let d1 = d.(i-1).(j)+1 in
      let d2 = d.(i).(j-1)+1 in
      let d3 = d.(i-1).(j-1) + if u.[i-1]=v.[j-1] then 0 else 1 in
      d.(i).(j) <- min d1 (min d2 d3)
    done ;
  done ;
  d.(lu).(lv)
;;

levenshtein "niche" "chiens" ;;

(* Exercice 4 *)

(* Q1 *)

type item = {v: int ; w: int } ;;

(* Q2 *)

let rec somme items = match items with
  | [] -> (0,0)
  | it::q -> let (v,w) = somme q in (v+it.v,w+it.w)
;;

(* Q3 *)

(* on définit un ordre sur les objets *)
let compare_item a b = 
  if a.v < b.v then 1
  else if a.v = b.v then 0
  else -1
;;

let sac_a_dos_glouton items cm =
  Array.sort compare_item items ;
  let n = Array.length items in
  let rec ajout i c sac = match i<n with
    | false -> sac
    | true when items.(i).w + c <= cm -> ajout (i+1) (items.(i).w + c) (items.(i)::sac)
    | _ -> ajout (i+1) c sac
  in
  let sac = ajout 0 0 [] in
  let v,w = somme sac in
  (v,w,sac)
;;

let items =
  [|
    {v = 8 ; w = 10};
    {v = 16 ; w = 6};
    {v = 20 ; w = 14};
  |] ;;

sac_a_dos_glouton items 19 ;;

(* Q4 *)

(* soit on utilise l'objet numéro i, soit non *)

(* Q5 *)

let calcul_kp items cm =
  let n = Array.length items in
  let kp = Array.make_matrix (n+1) (cm+1) 0 in
  for i=1 to n do
    for c=0 to cm do
      let vi,wi = items.(i-1).v,items.(i-1).w in
      if c<wi then kp.(i).(c) <- kp.(i-1).(c)
      else kp.(i).(c) <- max kp.(i-1).(c) (kp.(i-1).(c-wi)+vi)
    done ;
  done ;
  kp
;;

calcul_kp items 19 ;;

(* Q6 *)

let sac_a_dos_dyna items cm =
  let n = Array.length items in
  let kp = calcul_kp items cm in
  let rec ajout i c sac =
    match i with
    | 0 -> sac
    | _ when c<items.(i-1).w -> ajout (i-1) c sac
    | _ when kp.(i-1).(c)>(kp.(i-1).(c-items.(i-1).w)+items.(i-1).v) -> ajout (i-1) c sac
    | _ -> ajout (i-1) (c-items.(i-1).w) (items.(i-1)::sac)
  in
  let sac = ajout n cm [] in
  let v,w = somme sac in
  (v,w,sac)
;;

sac_a_dos_dyna items 19 ;;