N.S.I. WorkSpace Compétence,Notions,P-Th-G,Première G5 – Algorithmes gloutons

G5 – Algorithmes gloutons

Le problème du sac à dos

On dispose d’une liste d’objets (lo), ayant chacun une masse (m) et une valeur pécuniaire (v).
On veut remplir un sac à dos avec ces objets sachant qu’il supporte une charge maximale (c).
On considère que la masse totale des objets de la liste est supérieure à la charge maximale supportée par le sac à dos. Il n’est donc pas possible de mettre dans le sac à dos la totalité des objets de la liste : il faut donc opérer à un choix des objets.

Pour remplir le sac à dos, on procède de la manière suivante :
on prend un objet de la liste et on compare sa masse avec la charge que peut encore supporter le sac à dos. En effet à chaque ajout d’un objet la charge du sac à dos augmente. Si la masse de l’objet est inférieure ou égale à la charge que peut encore supporter le sac à dos, alors on le met dans le sac à dos ;
quand un objet a été placé dans le sac à dos, on ne remet jamais en question ce choix. On s’interdit donc de retirer un objet préalablement placé dans le sac à dos pour le remplacer par un autre.
on réitère les opérations précédentes jusqu’à ce qu’on ne puisse plus mettre aucun objet dans le sac à dos sans dépasser sa charge maximale.

On considère que le remplissage optimal du sac à dos est celui pour lequel :
d’abord la masse totale des objets est égale ou très légèrement inférieure à la charge maximale du sac à dos ;
ensuite la valeur pécuniaire totale des objets placés dans le sac à dos est la plus élevée dans le cas où il y a plusieurs combinaisons d’objets pour lesquelles la masse totale des objets est identique et égale ou très légèrement inférieure à la charge maximale du sac à dos.

Pour remplir le sac à dos, une personne A procède au choix des objets de la façon implicitement décrite dans le programme qui suit :

from random import randint
from random import shuffle

def sac_a_dos_1(lo, c):
    # lo : liste d'objets ; liste de listes.
    #      Chaque sous-liste comporte 3 éléments :
    #      lo[0] : nom de l'objet (str)
    #      lo[1] : masse de l'objet (int)
    #      lo[2] : valeur pécuniaire de l'objet (int)

    # c : charge maximale supportée par le sac à dos (int)

    # mélange des objets de la liste
    shuffle(lo)

    # s  : contenu du sac à dos (list)
    # s[0] : liste des objets placés dans le sac à dos (list of str)
    # s[1] : masse totale de ces objets (int)
    # s[2] : valeur pécuniaire totale de ces objets (int)
    s = [[], 0, 0]

    while lo != []:
        # no : nombre d'objets restant dans la liste
        no = len(lo)

        # id : index d'un objet choisi dans la liste
        id = randint(0, no - 1)

        # Vérification : est-il possible de mettre l'objet choisi dans le sac ?
        if lo[id][1] <= c - s[1]:

            # Oui : donc on le met
            s[0].append(lo[id][0])
            s[1] += lo[id][1]
            s[2] += lo[id][2]

        # On retire l'objet de la liste
        del(lo[id])

    # renvoi du résultat
    return s

Lien de téléchargement

D’après les instructions de ce programme, indiquer de quelle façon la personne A procède au choix des objets qu’elle met dans le sac à dos. Discuter ce choix par rapport au but d’un remplissage optimal du sac à dos.

Pour choisir les objets qu’elle va mettre dans le sac à dos, une personne B décide de mettre en œuvre une méthode « gloutonne » : elle commence par trier les objets de la liste par ordre croissant de masse, puis elle place dans le sac à dos les objets en partant du moins lourd jusqu’à atteindre la charge maximale supportée par le sac.

Compléter les instructions écrites en langage Python de la fonction qui permet de mettre en œuvre la stratégie « gloutonne » de remplissage du sac à dos proposée par la personne B.
Télécharger, éditer et remplacer dans le code qui suit les ??? par ce qui convient.

Lien de téléchargement

def sac_a_dos_2(lo, c):
    # lo : liste d'objets ; liste de listes.
    #      Chaque sous-liste comporte 3 éléments :
    #      lo[0] : nom de l'objet (str)
    #      lo[1] : masse de l'objet (int)
    #      lo[2] : valeur pécuniaire de l'objet (int)

    # c : charge maximale supportée par le sac à dos (int)

    # tri des objets de la liste par ordre croissant de masse
    lo.sort(key = lambda x:x[???])

    # s  : contenu du sac à dos (list)
    # s[0] : liste des objets placés dans le sac à dos (list of str)
    # s[1] : masse totale de ces objets (int)
    # s[2] : valeur pécuniaire totale de ces objets (int)
    s = [[], 0, 0]

    for objet in lo :

        # Vérification : est-il possible de mettre l'objet choisi dans le sac ?
        if objet[1] ??? c - s[???]:

            # Oui : donc on le met
            s[0].append(objet[???])
            s[1] += objet[???]
            s[2] += objet[???]

        else :
            break

    # renvoi du résultat
    return s
Pour choisir les objets qu’elle va mettre dans le sac à dos, une personne C décide de mettre en œuvre une méthode « gloutonne » : elle commence par trier les objets de la liste par ordre décroissant de valeur pécuniaire, puis elle place dans le sac à dos les objets en partant du plus cher jusqu’à atteindre la charge maximale supportée par le sac.

Pour choisir les objets qu’elle va mettre dans le sac à dos, une personne D décide de mettre en œuvre une méthode « gloutonne » : elle commence par trier les objets de la liste par ordre décroissant du rapport entre la valeur pécuniaire et la masse, puis elle place dans le sac à dos les objets en partant de celui qui possède le rapport valeur pécuniaire/masse le plus élevé jusqu’à atteindre la charge maximale supportée par le sac.

Ecrire en langage Python les instructions de deux fonctions qui permettent de mettre en œuvre ces deux stratégies « gloutonnes » de remplissage du sac à dos.
S’appuyer sur la fonction qui met en œuvre la stratégie gloutonne de la Personne A.

En utilisant une même liste d’objets et une même charge maximale pour le sac à dos, déterminer et comparer les solutions apportées par chacune des stratégies de remplissage définies précédemment.
Laquelle des solutions apportées par ces stratégies paraît-elle être meilleure que les autres ?
Vérifier ssi la solution proposée par cette stratégie s’avère être toujours la meilleure, en modifiant soit la liste d’objets, soit la charge maximale du sac à dos.
Utiliser par exemple les données qui suivent.

lo = [['Objet_01', 26, 146],
      ['Objet_02', 28, 117],
      ['Objet_03', 23, 276],
      ['Objet_04', 19, 230],
      ['Objet_05', 22, 276],
      ['Objet_06', 30, 104],
      ['Objet_07', 22, 216],
      ['Objet_08', 30, 154],
      ['Objet_09', 19, 290],
      ['Objet_10', 29, 243],
      ['Objet_11', 24, 246],
      ['Objet_12', 12, 195],
      ['Objet_13', 19, 158],
      ['Objet_14', 26, 211],
      ['Objet_15', 10, 169],
      ['Objet_16', 28, 281],
      ['Objet_17', 13, 206],
      ['Objet_18', 11, 137],
      ['Objet_19', 19, 128],
      ['Objet_20', 19, 174]]
c = 90

Avec les données ci-dessus, la solution optimale est la suivante :
liste des objets : ‘Objet_05’, ‘Objet_09’, ‘Objet_11’, ‘Objet_12’, ‘Objet_17’ ;
masse totale : 90
valeur pécuniaire totale : 1213.
Cette solution figure-t-elle parmi celles proposées par les stratégies précédentes ?


Article sous licence << Cliquez pour plus d’informations <<