Sac à dos fractionnaire

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.