Le problème du sac à dos

Plan de ce cours distanciel :

« Nous disposons d’une clé USB qui est déjà bien remplie et sur laquelle il ne reste que 5 Go de libre. Nous souhaitons copier sur cette clé des fichiers vidéos pour l’emporter en voyage. Chaque fichier a une taille et chaque vidéo a une durée. La durée n’est pas proportionnelle à la taille car les fichiers sont de format différents, certaines vidéos sont de grande qualité, d’autres sont très compressées. »

Angle d’attaque choisi :

  1. Représentation des données
  2. Révision du tri par insertion
  3. Un algorithme glouton
  4. Force brute
  5. Conclusion

 

Premier code :

  • Représentation des données
  • Révision du tri par insertion
  • Un algorithme glouton

 

##############################
# Représentation des données #
##############################

# une liste de triplets
# chaque triplet représente une vidéo
# (nom de la vidéo, durée (int), poids en Go (float))

videos = [('Video1', 114, 4.57), # ratio 114 / 4.57 = 24.95
          ('Video2', 32, 0.630), # ratio 32 / 0.63 = 50.8
          ('Video3', 20, 1.65),  # ratio 20 / 1.65 = 12.1212
          ('Video4', 4, 0.085),  # ratio 4 / 0.085 = 47.05
          ('Video5', 18, 2.15),  # ratio 18 / 2.15 = 8.37
          ('Video6', 80, 2.71),  # ratio 80 / 2.71 = 29.5
          ('Video7', 5, 0.320)]  # ratio 5 / 0.320 = 15.63

#########################
# Un algorithme glouton #
#########################

# tri par ratio pour commencer

# liste initiale
# [24.95, 50.8, 12.12, 47.05, 8.37, 29.5, 15.63]
# début puis insertion
# [50.8, 24.95, 12.12, 47.05, 8.37, 29.5, 15.63]
# [50.8, 24.95, 12.12, 47.05, 8.37, 29.5, 15.63]
# [50.8, 47.05, 24.95, 12.12, 8.37, 29.5, 15.63]
# [50.8, 47.05, 29.5, 24.95, 12.12, 8.37, 15.63]
# [50.8, 47.05, 29.5, 24.95, 15.63, 12.12, 8.37]

# soit 


def ratio(v): # on choisit ce critère comme choix
    return v[1] / v[2]
    
def tri_insertion_par_ratio(liste):
    # On insère la video de rang « rang » au fur et à mesure
    # on part du rang 1 car le rang zéro est déjà « trié »
    for rang in range(1, len(liste)):
        # quel est le ratio à classer ?
        ratio_a_classer = ratio(liste[rang])
        # pour ne pas perdre la video à replacer
        a_sauvegarder = liste[rang]

        i = rang # on part du rang et on « descend »

        # on regarde « à gauche » si c'est plus petit
        while i > 0 and ratio(liste[i - 1]) < ratio_a_classer:
            liste[i] = liste [i - 1] # on recopie vers la droite
            i -= 1  # on va à gauche

        # on pose la video ici
        liste[i] = a_sauvegarder

    # « return liste » est inutile ici : on a passé l'adresse de la liste
    # et on a donc modifié la liste « en place »


# tests avant la suite

# tri_insertion_par_ratio(videos)
# print(videos)


def sac_a_dos_glouton(videos, taille_max):
    # Je trie d'abord la liste
    tri_insertion_par_ratio(videos)

    # sac à dos vide
    sac_a_dos = []

    # des variables
    totale_duree = 0
    taille_totale = 0

    # on va le remplir en glouton
    i = 0
    
    while i < len(videos) and taille_totale < taille_max:

        # récupération des données
        nom, d, t = videos[i]
        
        # est-ce que je peux encore mettre la vidéo dans le sac ?
        if taille_totale + t <= taille_max: 
            # je mets dans le sac
            sac_a_dos.append(nom)
            taille_totale += t
            totale_duree += d

        # on continue à parcourir la liste
        i += 1

    return sac_a_dos, totale_duree

# appel de la fonction et récupération des résultats
reponse , tps_total = sac_a_dos_glouton(videos, 5)
        
print("Application de l'algorithme glouton :")
print("On aura ici", tps_total, "minutes de vidéos avec")
print(reponse)
Application de l'algorithme glouton :
On aura ici 121 minutes de vidéos avec
['Video2', 'Video4', 'Video6', 'Video7']
>>> 

Deuxième code :

Puisqu’il n’y a que sept vidéos, on peut utiliser un algorithme de « force brute » en testant toutes les 2^7 = 128 possibilités avec une astuce liée à l’écriture binaire. Exemples :

1 -> 0000000 -> aucune vidéo
2 -> 0000001 -> seule la vidéo 7

9 -> 0001001 -> la vidéo 4 et la vidéo 7

64 -> 1000000 -> seule la vidéo 1

127 -> 1111111 -> toutes les vidéos.

Il faut bien entendu vérifier que ça rentre dans le « sac à dos », c’est-à-dire la clé usb.

 

##############################
# Représentation des données #
##############################

# une liste de triplets
# chaque triplet représente une vidéo
# (nom de la vidéo, durée (int), poids en Go (float))

videos = [('Video1', 114, 4.57),
          ('Video2', 32, 0.630),
          ('Video3', 20, 1.65),
          ('Video4', 4, 0.085),
          ('Video5', 18, 2.15),
          ('Video6', 80, 2.71),
          ('Video7', 5, 0.320)]


###############
# Force brute #
###############

def temps_total(selection):
    t = 0
    for v in selection:
        t += v[1]
    return t

def taille_totale(selection):
    t = 0
    for v in selection:
        t += v[2]
    return t

def force_brute(videos, taille_max):
    nbre = len(videos)
    magouille = 2 ** nbre # 128
    reponse = []

    for cle in range(magouille): # il y a nombre possibilités de 0 à 127
        chaine = bin(cle)[2:]
        long = len(chaine)
        if long < nbre:
            chaine = (nbre - long) * '0' + chaine
        #print(chaine)
        combinaison = []
        for i in range(nbre):
            if chaine[i] == '1':
                combinaison.append(videos[i])
        if temps_total(combinaison) > temps_total(reponse):
            if taille_totale(combinaison) < taille_max:
                reponse = combinaison
                print("Trouvé mieux :")
                print(reponse)
                print("Ce qui fait", temps_total(reponse), "minutes")
                print("pour", taille_totale(combinaison), "Go")
        
print("Application de l'algorithme de force brute :")
force_brute(videos, 5)
Trouvé mieux :
[('Video2', 32, 0.63), ('Video3', 20, 1.65), ('Video6', 80, 2.71)]
Ce qui fait 132 minutes
pour 4.99 Go
>>> 

Conclusion

Ici la démarche gloutonne ne donne pas le résultat optimal en prenant le ratio comme critère.

C’est néanmoins un algorithme facile à mettre en œuvre (on n’est en plus pas obligé de trier par insertion mais on peut utiliser les tris de listes de python)

Enfin, la force brute a ici été possible car on n’a que très peu d’éléments dans la liste ! Le nombre de possibilités $latex 2^{\text{taille de la liste}} devient vite trop lourd à tester.

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.