(* Mines 2002 *)
                             

  let n = 6 ;;
 
  let u = [|16;21;19;15;13;7|] ;;

  let p = [|15;22;20;17;15;9|] ;;
  
  let Q = 51 ;;
  
  let test_inégalites_1 () =                     (* version recursive *)
     let rec aux i =
        if i = n-1 then true 
        else (u.(i+1) * p.(i)<= p.(i+1) * u.(i))  && aux (i+1)
     in aux 0 ;;   

  let test_inegalite_2 () =                      (* version iterative *)
    let ok = ref(true) and i = ref 1 in
      while !ok  && !i < n do
          if u.(!i-1) * p.(!i) < p.(!i-1) * u.(!i) then ok := false;
          i := !i + 1;
      done;
      !ok ;;    
 
  let calcule_indice_1 () =                      (* version recursive *)
     let rec aux i s =
        if i = n then n
                 else if s >= Q then (i-1)
                                else aux (i+1) (s + p.(i))
  in aux 0 0;;                                
                        
     
  let calcule_indice_2 () =                      (* version iterative *)
    let s = ref 0 and i = ref 0 in
      while !s < Q && !i <n do
          s := !s + p.(!i);
          i := !i +1;
      done;
      if !s < Q then n else !i -1 ;;    
      

    let meilleur () =
     let rec aux  i m =
       if i = n-1 then if p.(i) <= m then ([1],u.(i)) else ([0],0)
       else
           begin
             let (l0,z0) = aux (i+1) m                    (* utile pour le cas où x.(i)=0 *)
             in if m <= p.(i) 
                then  (0::l0,z0)
                else let(l1,z1) = aux (i+1) (m-p.(i)) in  (* utile pour le cas où x.(i)=1 *)
                     if z1 + u.(i) > z0 
                     then (1::l1,z1+u.(i)) 
                     else (0::l0,z0)
           end
     in aux 0 Q ;;        
    
 
                                 (*********************)