Inspiré du TP de ELIAS BERRABAH sur Capytale

Lui-même inspiré du document d'accompagnement

I. Énoncé du problème

Votre téléphone est déjà bien rempli et il ne reste que 5 GO de libre. Vous souhaitez copier dessus des fichiers vidéo pour un voyage. Chaque fichier vidéo possède une taille en GO et une durée en minutes. La durée n’est pas proportionnelle à la taille car les fichiers sont de format différents, certaines vidéos sont de grande qualité (en 4K par exemple et donc prennent beaucoup de place) et d’autres ont été compressées.
Le tableau qui suit présente les fichiers vidéo que vous possédez.

Il est impossible d'emporter tous les fichiers vidéo (la somme des tailles de ces 7 vidéos dépasse les 5GO), mais vous souhaitez maximiser la durée totale des vidéos emportées (pour vous occuper le plus longtemps possible).

Ainsi, on préfèrera par exemple ne garder que la vidéo 1 seule (dont la durée est de 114 minutes) plutôt que de garder les vidéos 2 et 3 (dont la durée totale est de 32+20 = 52 minutes) etc…

On est donc face à un problème d’optimisation : maximiser la durée totale des vidéos (peu importe le nombre de vidéos) avec la contrainte que la somme de leur taille doit être inférieure ou égale à 5GO.

II. Structure de données choisie pour l’implémentation en Python

Chaque fichier sera représenté par un tuple à 3 éléments contenant son nom, sa durée en minutes et sa taille en GO (par exemple 630 MO = 0.63 GO). L’ensemble des vidéos est donc une liste de tuples. Dans le cas de l'exemple, l’ensemble des vidéos sera représenté par la variable suivante :

ensemble_videos_exemple = [
    ('Vidéo 1', 114, 4.57),
    ('Vidéo 2', 32, 0.630),
    ('Vidéo 3', 20, 1.65),
    ('Vidéo 4', 4, 0.085),
    ('Vidéo 5', 18, 2.15),
    ('Vidéo 6', 80, 2.71),
    ('Vidéo 7', 5, 0.320)]

III. Résolution par des algorithmes gloutons

Il existe plusieurs algorithmes gloutons pour résoudre ce problème.

Pour chacune de ces méthode, on a besoin de séléctionner la vidéo qui a "le plus" ou "le moins" d'un certain critère. Une bonne façon de faire ça, est de trier les données. Ça tombe bien, on a vu des algorithmes de tri en cours !

Pour utilisez cette fonction, on peut construire, pour chaque algorithme, une nouvelle liste de couples, avec pour chaque élément

• la valeur selon laquelle on séléctionne les vidéos dans l'algorithme
• le triplet représentant la vidéo

Pour l'algorithme A, dans l'exemple du début d'énoncé, cela donne :

videos_algoA = [
    (-114, ('Vidéo 1', 114, 4.57)),
    (-32, ('Vidéo 2', 32, 0.630)),
    (-20, ('Vidéo 3', 20, 1.65)),
    (-4, ('Vidéo 4', 4, 0.085)),
    (-18, ('Vidéo 5', 18, 2.15)),
    (-80, ('Vidéo 6', 80, 2.71)),
    (-5, ('Vidéo 7', 5, 0.320))]

(les valeurs sont négatives car on souhaite prendre la vidéo la plus longue d'abord, mais on a une fonction qui trie dans l'ordre croissant)

Pour les algorithmes gloutons, il faudra écrire des fonction qui

• créent la liste décrite ci-dessus avec le bon critère
• trient la liste en question
• tentent de mettre chaque élémént dans l'ordre, et vérifier si ça rentre encore
• renvoyer la dernière combinaison qui rentre trouvée.

IV. Résolution par force brute

Une première façon de résoudre ce problème est la force brute : c’est-à-dire que l’on teste toutes les associations possibles de vidéos et pour chacune d’entre elle, on calcule la durée totale et la taille totale. Si la taille totale dépasse 5GO, on ignore cette association, dans le cas contraire, on mémorise la durée trouvée et on continue ainsi en sélectionnant l’association qui aboutira à une durée maximale. Par exemple, pour l’association Vidéo 1, Vidéo 2, Vidéo 6, la taille totale en GO est 4.57+0.63+2.71 = 7.91, c’est supérieur à 5GO donc cette association ne sera pas retenue.

Ensuite, par exemple pour l’association Vidéo 2, Vidéo 4, Vidéo 6, la taille totale en GO est 0.63+0.085+2.71 = 3.425 GO. Cette taille est inférieure à 5GO, la contrainte est respectée, on peut calculer la durée totale qui ici vaut : 32+4+80 = 116 minutes. C’est potentiellement l’association optimale, on la retient jusqu’à trouver encore meilleur. Il y a encore meilleur par exemple avec l’association Vidéo 1, Vidéo 4 dont la taille ne dépasse pas 5GO et la durée vaut 114+4=118 minutes etc…. En testant toutes les associations possibles, on est sûr de trouver la durée maximale.

On souhaite désormais réaliser une fonction force_brute(videos) permettant de tester toutes les vidéos. Pour cela, on va commencer par une fonction combinaisons(videos) qui renvoie une liste de toutes les combinaisons possibles d'éléments de videos.

V. Un dernier exemple avec beaucoup plus de vidéos

Sarah possède bien plus de vidéos dans son ordinateur, elle en possède 80 et il ne lui reste aussi que 5GO dans sa clé. L’ensemble des informations sur tous ses fichiers vidéo est disponible dans le fichier CSV ensemble_videos_Sarah.csv. Voici la variable associée (mais vous auriez pu importer ces données vous-même grâce au module csv) :

ensemble_videos_Sarah =[('Video 1', 47, 0.71), ('Video 2', 90, 15.4), ('Video 3', 58, 1.1), ('Video 4', 119, 13.0),
 ('Video 5', 125, 3.96), ('Video 6', 170, 8.36), ('Video 7', 98, 0.81), ('Video 8', 124, 0.97),
 ('Video 9', 95, 0.73), ('Video 10', 111, 0.57), ('Video 11', 14, 0.34), ('Video 12', 132, 19.5),
 ('Video 13', 39, 11.3), ('Video 14', 119, 1.4), ('Video 15', 39, 15.2), ('Video 16', 84, 0.67),
 ('Video 17', 42, 0.64), ('Video 18', 48, 0.45), ('Video 19', 19, 9.09), ('Video 20', 82, 3.12),
 ('Video 21', 45, 0.77), ('Video 22', 164, 6.82), ('Video 23', 36, 0.66), ('Video 24', 145, 2.53),
 ('Video 25', 27, 4.27), ('Video 26', 79, 5.09), ('Video 27', 124, 19.1), ('Video 28', 62, 7.85),
 ('Video 29', 49, 4.07), ('Video 30', 63, 12.4), ('Video 31', 20, 6.8), ('Video 32', 93, 0.56),
 ('Video 33', 66, 17.3), ('Video 34', 152, 17.6), ('Video 35', 70, 7.79), ('Video 36', 21, 0.65),
 ('Video 37', 162, 11.9), ('Video 38', 136, 6.38), ('Video 39', 122, 0.64), ('Video 40', 119, 12.5),
 ('Video 41', 25, 0.9), ('Video 42', 172, 12.1), ('Video 43', 66, 4.47), ('Video 44', 114, 12.7),
 ('Video 45', 1, 0.34), ('Video 46', 4, 0.24), ('Video 47', 128, 16.3), ('Video 48', 173, 0.93),
 ('Video 49', 64, 0.43), ('Video 50', 113, 6.91), ('Video 51', 44, 15.7), ('Video 52', 1, 0.04),
 ('Video 53', 96, 2.37), ('Video 54', 97, 2.96), ('Video 55', 25, 10.7), ('Video 56', 166, 19.2),
 ('Video 57', 35, 11.2), ('Video 58', 56, 0.7), ('Video 59', 119, 13.3), ('Video 60', 6, 16.4),
 ('Video 61', 93, 15.9), ('Video 62', 17, 8.97), ('Video 63', 120, 0.3), ('Video 64', 63, 2.34),
 ('Video 65', 95, 0.97), ('Video 66', 176, 1.47), ('Video 67', 48, 18.7), ('Video 68', 26, 6.62),
 ('Video 69', 97, 0.76), ('Video 70', 175, 13.8), ('Video 71', 24, 6.81), ('Video 72', 107, 0.76),
 ('Video 73', 55, 14.7), ('Video 74', 164, 16.1), ('Video 75', 40, 0.69), ('Video 76', 80, 0.01),
 ('Video 77', 150, 14.9), ('Video 78', 93, 18.5), ('Video 79', 34, 0.38), ('Video 80', 101, 2.8)]

Entrez le code donné en cours pour accéder à la solution :