SHARE
TWEET

Option info - TP 5 Sac à Dos

csmine May 24th, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. let b = 1000;;
  2.  
  3. let p = [|15;87;321;4897;20;1;12;45;50;100;3;48;29;71428;310;147;199;351|];;
  4. let u = [|1;8;7;9;3;1;4;5;78;8;89;2;2;1;45;56;6;9|];;
  5.  
  6. let qua_prix u p =
  7. let n = Array.length u in
  8. let t = Array.make n 0.0 in
  9.     for i=0 to n-1 do
  10.     t.(i) <- float_of_int(u.(i))/.float_of_int(p.(i))
  11.     done;
  12. t;;
  13. qua_prix u p;;
  14.  
  15. let rec pas_dans_liste a liste = match liste with
  16. |[] -> true
  17. |h::t -> if a<>h then pas_dans_liste a t
  18.             else false;;
  19.  
  20.  
  21. let randonneur_glouton b u p =
  22. let n = Array.length u in
  23. let porte_monnaie = ref b in
  24. let qp = qua_prix u p in
  25.  
  26. let last_indice = ref (-1) in
  27.  
  28. let current_indice = ref 0 in
  29. let current_max = ref (-1.0) in
  30.  
  31. let liste_indice = ref [] in
  32.  
  33. let condition_de_sortie = ref 0 in
  34.  
  35. let somme_prix = ref 0 in
  36.  
  37. while !condition_de_sortie < n do
  38.     current_indice := 0 ;
  39.     condition_de_sortie := 0 ;
  40.     current_max:= (-1.0) ;
  41.     for i=0 to n-1 do
  42.     if (qp.(i)>= !current_max
  43.         && !porte_monnaie >= p.(i)
  44.         && (pas_dans_liste i !liste_indice)) then
  45.                 begin
  46.                 current_max:=qp.(i);
  47.                 current_indice:=i;
  48.                 end;
  49.     if !porte_monnaie<p.(i) then incr condition_de_sortie;
  50.     done;
  51.     condition_de_sortie := !condition_de_sortie + List.length(!liste_indice);
  52.     if !condition_de_sortie < n then
  53.     begin
  54.     last_indice:=!current_indice;
  55.     somme_prix := !somme_prix + p.(!current_indice);
  56.     liste_indice:=(!current_indice :: !liste_indice);
  57.     porte_monnaie:=!porte_monnaie - p.(!current_indice);
  58.     end
  59.     done;
  60. !liste_indice;;
  61.  
  62. randonneur_glouton 3 u p;;
  63.  
  64. (* 2. a. m(b,k) est l'utilité maximale
  65. que l'on peut obtenir pour les objets de 0 à k avec un budget de b
  66.  
  67. m(b,0) = utilité maximale pour l'objet 0.
  68. m(b,0) = 0 si p(0) > b
  69.              u(0) si p(0)<=b *)
  70.              
  71.  
  72. let randonneur_max b u p =
  73.  
  74. let n = Array.length u in
  75. let m = Array.make_matrix (b+1) n 0 in
  76.  
  77. for k=0 to (n-1) do
  78.  
  79.     for price=0 to b do
  80.     (* Relation m(b,0) = u(0) si p(0) <= b, l'autre cas donne 0 *)
  81.     if (k=0 && p.(0)<=price) then m.(price).(0) <- u.(0)
  82.     else if k>0 then
  83.         (* première "étage" de la relation *)
  84.         if p.(k)>price then m.(price).(k) <- m.(price).(k-1)
  85.         (* deuxième "étage" de la relation *)
  86.         else m.(price).(k) <- max (m.(price).(k-1)) (u.(k) + m.(price-p.(k)).(k-1));
  87.         done;
  88.         done;
  89.         m.(b).(n-1);;
  90.  
  91. randonneur_max 5 [|100000;1|] [|4;2|];;
  92.  
  93.  
  94.  
  95. let randonneur_max_objets b u p =
  96.  
  97. let n = Array.length u in
  98. let m = Array.make_matrix (b+1) n 0 in
  99. let obj = Array.make_matrix (b+1) n [] in
  100.  
  101. for k=0 to (n-1) do
  102.  
  103.     for price=0 to b do
  104.     (* Relation m(b,0) = u(0) si p(0) <= b, l'autre cas donne 0 *)
  105.     (* L'objet 0 est achetable *)
  106.     if (k=0 && p.(0)<=price) then   begin
  107.                                                 m.(price).(0) <- u.(0);
  108.                                                 obj.(price).(0) <- [0];
  109.                                                 end
  110.     else if k>0 then
  111.         (* première "étage" de la relation *)
  112.         if p.(k)>price then
  113.         begin
  114.         m.(price).(k) <- m.(price).(k-1);
  115.         obj.(price).(k) <- obj.(price).(k-1);
  116.         end
  117.         (* deuxième "étage" de la relation *)
  118.         else
  119.             (* L'objet k est pas rentable *)
  120.             if (m.(price).(k-1)) > (u.(k) + m.(price-p.(k)).(k-1)) then
  121.                 begin
  122.                 m.(price).(k) <- m.(price).(k-1);
  123.                 obj.(price).(k) <- obj.(price).(k-1);
  124.                 end
  125.             (* L'objet k est rentable *)
  126.             else
  127.                 begin
  128.                 m.(price).(k) <- u.(k) + m.(price-p.(k)).(k-1);
  129.                 obj.(price).(k) <- (k::(obj.(price-p.(k)).(k-1)))
  130.                 end
  131.         done;
  132.         done;
  133.         (m.(b).(n-1),List.rev(obj.(b).(n-1)));;
  134. randonneur_max_objets 9 [|71;82;88;80;97;49;81;83;88;91|] [|3;1;6;2;1;2;2;5;2;5|];;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top