Algorithmes gloutons

let rec rendu pieces montant =
  match pieces with
  | [] -> if montant = 0 then [] else failwith "rendu impossible"
  | p :: reste ->
      if p <= montant then p :: rendu pieces (montant - p)
      else rendu reste montant

rendu [50;20;10;5;2;1] 67 $=$ [50; 10; 5; 2], soit quatre pièces ($50+10+5+2=67$).

let rec nb_pieces pieces montant =
  match pieces with
  | [] -> if montant = 0 then 0 else failwith "rendu impossible"
  | p :: reste ->
      if p <= montant then 1 + nb_pieces pieces (montant - p)
      else nb_pieces reste montant

Même structure que rendu, mais on compte au lieu d'accumuler. nb_pieces [50;20;10;5;2;1] 67 $=4$.

let compatibles a b = a.fin <= b.debut || b.fin <= a.debut

Deux activités sont compatibles si l'une finit avant que l'autre commence (dans un sens ou dans l'autre). On adopte la convention « fin $\le$ début » : une activité qui finit à l'instant où une autre commence ne la chevauche pas.

let rec tri_fin l =
  let rec insere a l =
    match l with
    | [] -> [a]
    | b :: reste -> if a.fin <= b.fin then a :: l else b :: insere a reste
  in
  match l with
  | [] -> []
  | a :: reste -> insere a (tri_fin reste)

C'est le tri par insertion du chapitre 9, mais comparant le champ fin des enregistrements (un tri générique < les comparerait par debut d'abord, ce qu'on ne veut pas). Trier par fin est l'étape clé du glouton.

let selection activites =
  match tri_fin activites with
  | [] -> []
  | premiere :: reste ->
      let rec choisir fin_courante l =
        match l with
        | [] -> []
        | a :: r ->
            if a.debut >= fin_courante then a :: choisir a.fin r
            else choisir fin_courante r
      in
      premiere :: choisir premiere.fin reste

On retient la première (celle qui finit le plus tôt), puis on parcourt les suivantes : chaque activité dont le debut est $\ge$ à la fin_courante est retenue (et devient la nouvelle référence) ; les autres sont écartées.

let rec longueur l =
  match l with [] -> 0 | _ :: r -> 1 + longueur r

let nombre_max activites = longueur (selection activites)

On réutilise selection et l'on compte. Le glouton « fin la plus tôt » garantit que ce nombre est maximal (cf. l'argument d'échange).

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).

nb_pieces [4;3;1] 6 : le glouton prend 4 (reste 2), puis 1 + 1 → 3 pièces. rendu_min [4;3;1] 6 : le minimum est 3 + 3 → 2 pièces. Le glouton échoue car son premier choix (la grosse pièce 4) bloque la meilleure combinaison. Sur un système non canonique, seule une méthode exhaustive (ou la programmation dynamique) garantit l'optimum. C'est la limite fondamentale du glouton.

type objet = { valeur : float; poids : float }

let rec tri_ratio l =          (* tri décroissant par valeur/poids *)
  let rec insere o l =
    match l with
    | [] -> [o]
    | x :: reste ->
        if o.valeur /. o.poids >= x.valeur /. x.poids then o :: l
        else x :: insere o reste
  in
  match l with
  | [] -> [] | o :: reste -> insere o (tri_ratio reste)

let sac_fractionnaire objets capacite =
  let rec prendre l reste =
    match l with
    | [] -> 0.0
    | o :: suite ->
        if o.poids <= reste then o.valeur +. prendre suite (reste -. o.poids)
        else o.valeur *. (reste /. o.poids)   (* fraction du dernier objet *)
  in
  prendre (tri_ratio objets) capacite

On trie par rapport valeur/poids décroissant et on remplit : objets entiers tant qu'ils tiennent, puis une fraction du suivant. Le glouton est ici optimal (on peut couper). Attention : pour le sac à dos « 0/1 » (objets indivisibles), ce glouton n'est plus optimal — il faut la programmation dynamique.

Le nombre minimal de salles égale le nombre maximal d'activités simultanées. On trie séparément les débuts et les fins (tri_fusion du chapitre 9 sur des entiers) et l'on balaie le temps :

let salles activites =
  let debuts = tri_fusion (List.map (fun a -> a.debut) activites) in
  let fins = tri_fusion (List.map (fun a -> a.fin) activites) in
  let rec balayage debuts fins courant maxi =
    match debuts, fins with
    | [], _ -> maxi
    | d :: rd, f :: rf ->
        if d < f then
          let c = courant + 1 in
          balayage rd fins c (if c > maxi then c else maxi)
        else
          balayage debuts rf (courant - 1) maxi
    | _ -> maxi
  in
  balayage debuts fins 0 0

On avance dans le temps : un début avant la prochaine fin fait monter le nombre d'activités en cours (courant) — on note le pic maxi ; une fin le fait baisser. Le pic est le nombre de salles nécessaires. (d < f : une activité qui finit pile quand une autre commence libère la salle à temps.)