Option info - TP 5 Sac à Dos

let b = 1000;;

let p = [|15;87;321;4897;20;1;12;45;50;100;3;48;29;71428;310;147;199;351|];;
let u = [|1;8;7;9;3;1;4;5;78;8;89;2;2;1;45;56;6;9|];;

let qua_prix u p =
let n = Array.length u in
let t = Array.make n 0.0 in
    for i=0 to n-1 do
    t.(i) <- float_of_int(u.(i))/.float_of_int(p.(i))
    done;
t;;
qua_prix u p;;

let rec pas_dans_liste a liste = match liste with
|[] -> true
|h::t -> if a<>h then pas_dans_liste a t
            else false;;


let randonneur_glouton b u p =
let n = Array.length u in
let porte_monnaie = ref b in
let qp = qua_prix u p in

let last_indice = ref (-1) in

let current_indice = ref 0 in
let current_max = ref (-1.0) in

let liste_indice = ref [] in

let condition_de_sortie = ref 0 in

let somme_prix = ref 0 in

while !condition_de_sortie < n do
    current_indice := 0 ;
    condition_de_sortie := 0 ;
    current_max:= (-1.0) ;
    for i=0 to n-1 do
    if (qp.(i)>= !current_max
        && !porte_monnaie >= p.(i)
        && (pas_dans_liste i !liste_indice)) then
                begin
                current_max:=qp.(i);
                current_indice:=i;
                end;
    if !porte_monnaie<p.(i) then incr condition_de_sortie;
    done;
    condition_de_sortie := !condition_de_sortie + List.length(!liste_indice);
    if !condition_de_sortie < n then
    begin
    last_indice:=!current_indice;
    somme_prix := !somme_prix + p.(!current_indice);
    liste_indice:=(!current_indice :: !liste_indice);
    porte_monnaie:=!porte_monnaie - p.(!current_indice);
    end
    done;
!liste_indice;;

randonneur_glouton 3 u p;;

(* 2. a. m(b,k) est l'utilité maximale
que l'on peut obtenir pour les objets de 0 à k avec un budget de b

m(b,0) = utilité maximale pour l'objet 0.
m(b,0) = 0 si p(0) > b
             u(0) si p(0)<=b *)


let randonneur_max b u p =

let n = Array.length u in
let m = Array.make_matrix (b+1) n 0 in

for k=0 to (n-1) do

    for price=0 to b do
    (* Relation m(b,0) = u(0) si p(0) <= b, l'autre cas donne 0 *)
    if (k=0 && p.(0)<=price) then m.(price).(0) <- u.(0)
    else if k>0 then
        (* première "étage" de la relation *)
        if p.(k)>price then m.(price).(k) <- m.(price).(k-1)
        (* deuxième "étage" de la relation *)
        else m.(price).(k) <- max (m.(price).(k-1)) (u.(k) + m.(price-p.(k)).(k-1));
        done;
        done;
        m.(b).(n-1);;

randonneur_max 5 [|100000;1|] [|4;2|];;



let randonneur_max_objets b u p =

let n = Array.length u in
let m = Array.make_matrix (b+1) n 0 in
let obj = Array.make_matrix (b+1) n [] in

for k=0 to (n-1) do

    for price=0 to b do
    (* Relation m(b,0) = u(0) si p(0) <= b, l'autre cas donne 0 *)
    (* L'objet 0 est achetable *)
    if (k=0 && p.(0)<=price) then   begin
                                                m.(price).(0) <- u.(0);
                                                obj.(price).(0) <- [0];
                                                end
    else if k>0 then
        (* première "étage" de la relation *)
        if p.(k)>price then
        begin
        m.(price).(k) <- m.(price).(k-1);
        obj.(price).(k) <- obj.(price).(k-1);
        end
        (* deuxième "étage" de la relation *)
        else
            (* L'objet k est pas rentable *)
            if (m.(price).(k-1)) > (u.(k) + m.(price-p.(k)).(k-1)) then
                begin
                m.(price).(k) <- m.(price).(k-1);
                obj.(price).(k) <- obj.(price).(k-1);
                end
            (* L'objet k est rentable *)
            else
                begin
                m.(price).(k) <- u.(k) + m.(price-p.(k)).(k-1);
                obj.(price).(k) <- (k::(obj.(price-p.(k)).(k-1)))
                end
        done;
        done;
        (m.(b).(n-1),List.rev(obj.(b).(n-1)));;
randonneur_max_objets 9 [|71;82;88;80;97;49;81;83;88;91|] [|3;1;6;2;1;2;2;5;2;5|];;