G5b – Problème du sac à dos

Implémentation en langage Python de deux fonctions qui mettent en œuvre la stratégie “gloutonne” d’une Personne B et d’une Personne C

def sac_a_dos_3(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[2], reverse = True)

    # 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[1]:

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

    # renvoi du résultat
    return s

Lien de téléchargement

def sac_a_dos_4(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[2]/x[1], reverse = True)

    # 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[1]:

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

    # renvoi du résultat
    return s

Lien de téléchargement