------------------------------------------------------------------------------------ -- Fichier : concours.adb -- Auteur : Nicolas Seriot -- Date de création : 17.7.2003 -- -- But : Lire des couples valeur/poids dans des fichiers, -- choisir certains de ces couples de manière à maximiser -- la valeur totale, sous la contrainte de ne pas dépasser -- un poids maximal autorisé et à ce que la solution -- soit la plus légère possible. -- La résponse est donnée sous la forme d'une série de -- nombres ; N désigne la Nième boite lue dans les fichiers. -- -- Remarque(s) : - L'implémentation met l'accent sur la rapidité d'exécution, -- le programme n'indique qu'une seule solution optimale, -- meme s'il en existe d'autres de meme poids. -- - La complexité de l'algorithme est linéaire : O(kn). -- - Les bizarreries d'écriture sont pour la plupart justifiées -- par le fait que ce qui compte ici est la vitesse -- d'exécution. -- - sur ma machine et avec les données du concours : -- % time ./concours > resultats.txt -- 0.000u 0.000s 0:00.01 0.0% 0+0k 0+0io 0pf+0w -- % cat resultats.txt -- Pour maximiser la valeur sans dépasser 80 Kg, -- Monsieur X doit choisir les boites suivantes : -- 15 14 16 24 23 19 38 6 12 34 36 8 32 -- Valeur : 583 -- Poids : 80 -- - les résultats ont été vérifiés avec de nombreux jeux de -- données, autrement plus pervers que ceux du concours, -- pour lequel un simple algorithme glouton donne la solution, -- dont le poids est égal à la contrainte poids max. -- - les boites données dans la solution ne sont pas triées -- pour gagner du temps et car cela n'est pas demandé. -- -- Compilateur utilisé : gnat 3.15p -- ------------------------------------------------------------------------------------ with Ada.Text_Io, Ada.Integer_Text_Io; use Ada.Text_Io, Ada.Integer_Text_Io; procedure Concours is pragma Suppress(All_Checks); -- ne fait pratiquement pas gagner de temps -- du moins sur le jeu de données du concours Poids_Max : constant Positive := 80; -- le poids de M. X type T_Boite is record Num : Natural; Val : Natural; Pds : Natural; Rat : Float; end record; -- pour stocker les boites type T_Tab_Boite is array (Positive range <>) of T_Boite; -- pour conserver les solutions des sous-problèmes type T_Tab_Sol is array (Positive range <>, Positive range <>) of Boolean; -- pour effectuer les calculs par itérations successives -- un tableau à une dimension suffit type T_Calcul is array (0..Poids_Max) of Natural; --------------------------------------------------------------------------------- function Lecture_Boites return T_Tab_Boite is -- ++ -- Description: -- Lis les données dans les fichiers qui les contiennent, -- les renvoie sous la forme d'un tableau d'éléments numérotés. -- Chaque cellule contient aussi son rapport Valeur/Poids. -- Calcule au passage le ration valeur/poids pour chaque boite. -- -- Remarque(s): -- Néant. -- -- Paramètre(s): -- Néant. -- -- Exception(s): -- Fichiers_Incompatibles : levée si le nombre d'éléments annoncé dans -- chacun des fichiers n'est pas le meme. -- -- Fichiers_Incompatibles : exception; Nb_Boites : Positive; Argent : File_Type; Poids : File_Type; begin -- Lecture_Boites Open (File => Argent, Mode => In_File, Name => "Argent.txt"); Get(Argent, Nb_Boites); --- declare Tab_Boites : T_Tab_Boite(1..Nb_Boites); I : Positive := 1; -- l'indice du tableau, pour savoir ou ranger la boite begin while not End_Of_File(Argent) loop while not End_Of_Line(Argent) loop Tab_Boites(I).Num := I; -- numérotation par ordre d'apparition Get(Argent, Tab_Boites(I).Val); I := I + 1; end loop; Skip_Line(Argent); end loop; Close(Argent); -- lecture du second fichier Open (File => Poids, Mode => In_File, Name => "Poids.txt"); Get(Poids, Nb_Boites); if Nb_Boites /= Tab_Boites'Last then raise Fichiers_Incompatibles; end if; I := 1; -- on replace l'indice au début du tableau while not End_Of_File(Poids) loop while not End_Of_Line(Poids) loop Get(Poids, Tab_Boites(I).Pds); -- calcul du ratio valeur/poids Tab_Boites(I).Rat := Float(Tab_Boites(I).Val) / Float(Tab_Boites(I).Pds); I := I + 1; end loop; Skip_Line(Poids); end loop; Close(Poids); return Tab_Boites; end; --- end Lecture_Boites; --------------------------------------------------------------------------------- procedure Trier (Tab : in out T_Tab_Boite) is -- ++ -- Description: -- Trie le tableau de boites dans l'ordre décroissant de leur ratio, -- puis en cas d'égalité dans l'ordre croissant de leur poids. -- -- Remarque(s): -- L'algorithme utilisé est le tri par sélection. -- -- Paramètre(s): -- Tab : le tableau de boites à trier. -- -- Exception(s): -- Néant -- -- Imax : Positive; -- repère la pos. du plus grand élément encore non trié Temp : T_Boite; begin -- Trier for I in Tab'First..Tab'Last - 1 loop Imax := I; -- position initiale de l'élément min for J in I + 1..Tab'Last loop if Tab(J).Rat > Tab(Imax).Rat then Imax := J; -- pos élément courant -- si le ratio est le meme, la boite la plus légère est prioritaire elsif Tab(J).Rat = Tab(Imax).Rat then if Tab(J).Pds < Tab(Imax).Pds then Imax := J; end if; end if; end loop; -- permutation Temp := Tab(I); Tab(I) := Tab(Imax); Tab(Imax) := Temp; end loop; end Trier; --------------------------------------------------------------------------------- Boites : T_Tab_Boite := Lecture_Boites; type T_Tab_Opt is array (0..Boites'Length) of Natural; Tab_Sol : T_Tab_Sol(Boites'Range, 1..Poids_Max); Nouv : Natural; -- la nouvelle valeur totale pour un élément donné Tab_Opt : T_Tab_Opt := (others => 0); -- l'optimum après boite d'indice I Calcul : T_Calcul := (others => 0); -- val max connue pour chaque poids Poids : Integer := Poids_Max; -- pour remonter dans la solution Curseur : Integer := Boites'Length; -- pour remonter dans la solution Valeur_Totale : Integer := Calcul(Poids_Max); -- valeur totale optimale VT : Natural := 0; -- valeur totale jusqu'à présent PT : Natural := 0; -- poids total jusqu'à présent begin -- Concours Put("Pour maximiser la valeur sans dépasser" & Integer'Image(Poids_Max) & " Kg, "); Trier(Boites); for I in Boites'Range loop for J in reverse 1..Poids_Max loop if Boites(I).Pds <= J then Nouv := Calcul(J - Boites(I).Pds) + Boites(I).Val; -- si la boite améliore la marque if Nouv > Calcul(J) then Calcul(J) := Nouv; Tab_Sol(I, J) := True; else Tab_Sol(I, J) := False; end if; end if; end loop; -- si la valeur opt a changé if Tab_Sol(I, Poids_Max) then -- mettre la nouvelle valeur opt dans Tab_Opt Tab_Opt(I) := Tab_Opt(I - 1) + Boites(I).Val; else Tab_Opt(I) := Tab_Opt(I); end if; end loop; -- pas besoin de commencer avant while Tab_Opt(Curseur) > Valeur_Totale loop Curseur := Curseur - 1; end loop; Put_Line("Monsieur X doit choisir les boites suivantes : "); --Put_Line("Num Val Pds Rat"); for I in reverse 1..Curseur loop if Tab_Sol(I, Poids) then Put(Boites(I).Num, 3); -- Put(Boites(I).Val, 5); -- si on veut afficher les caractéristiques -- Put(Boites(I).Pds, 5); -- des boites... -- Put(Boites(I).Rat, 3, 3, 0); Poids := Poids - Boites(I).Pds; VT := VT + Boites(I).Val; PT := PT + Boites(I).Pds; --New_Line; end if; end loop; New_Line; Put_Line("Valeur : " & Integer'Image(VT) & " [Frs]"); Put_Line("Poids : " & Integer'Image(PT) & " [Kg]"); end Concours;