Le sac à dos fractionnaire : le même glouton, mais exact

Le problème fractionnaire. On peut prendre une fraction $x_i\in [0,1]$ de chaque objet, pour un gain $x_i{v}_i$ et un poids $x_i{p}_i$. On maximise $\sum x_i{v}_i$ sous la contrainte $\sum x_i{p}_i\le C$.

(* Valeur optimale du sac à dos FRACTIONNAIRE.
   Précondition : p.(i) > 0. Complexité : Theta(n log n), le tri.
   Postcondition : le résultat majore l'optimum du sac à dos entier. *)
let sac_fractionnaire p v c =
  let n = Array.length p in
  let idx = Array.init n (fun i -> i) in
  Array.sort (fun i j ->                                 (* rapport DÉCROISSANT *)
    compare (float_of_int v.(j) /. float_of_int p.(j))
            (float_of_int v.(i) /. float_of_int p.(i))) idx;
  let reste = ref (float_of_int c) and total = ref 0.0 in
  Array.iter (fun i ->
    let pris = min !reste (float_of_int p.(i)) in        (* on FRACTIONNE le dernier *)
    total := !total +. pris *. float_of_int v.(i) /. float_of_int p.(i);
    reste := !reste -. pris) idx;
  !total

La démonstration par échange. Soit $r_i=v_i/p_i$, et supposons les objets rangés par $r$ décroissant. Soit $X=(x_i)$ une solution optimale. Si $X$ n'est pas la solution gloutonne, il existe $i<j$ avec $x_i<1$ et $x_j>0$ : on a pris du $j$ alors qu'il restait du $i$, meilleur.

Transférons un poids $\delta =\min (p_i(1-x_i),p_j{x}_j)>0$ de $j$ vers $i$ : le poids total est inchangé, et la valeur varie de

$$\delta (r_i-r_j)\ge 0,$$

puisque $r_i\ge r_j$. La solution obtenue est donc encore optimale, et elle a une variable de moins hors de $\{0,1\}$ du côté glouton. En itérant — au plus $n$ fois — on aboutit à la solution gloutonne sans jamais perdre de valeur. Elle est donc optimale.

Pourquoi cet argument tombe sur le sac entier. Il repose entièrement sur la possibilité de transférer un morceau $\delta$. Avec $x_i\in \{0,1\}$, on ne peut plus transférer que des objets entiers, dont les poids ne coïncident pas — et il n'y a plus d'échange. Une seule hypothèse retirée, et la preuve entière s'effondre : c'est la marque des preuves de glouton, qui sont fragiles et doivent être refaites à chaque variante.

Ce que l'optimum fractionnaire vaut. Mesuré sur le contre-exemple du cours, avec $C=100$ et les objets $(p=1,v=2)$ et $(p=100,v=100)$ : le fractionnaire vaut $101,0$, l'entier $100$. Le fractionnaire majore toujours l'entier, puisque toute solution entière est une solution fractionnaire particulière.

C'est ce qui en fait la borne de la séparation et évaluation du chapitre chap:probabilistes : une borne optimiste, calculable en $\Theta (n\log n)$, et d'autant plus serrée que les objets sont petits devant $C$. Le glouton exact d'un problème relâché sert de borne à son problème d'origine — c'est un procédé général, et le programme le cite sous le nom de relaxation continue.