Problème du sac à dos

Dans un jeu vidéo, le héros dispose d’un sac à dos lui permettant de porter les objets collectés au cours de sa quête. Le sac à dos a une capacité maximale de 10 kg. Le héros doit maximiser la valeur en pièces d’or des objets contenus dans son sac à dos. On donne pour chaque objet collecté par le héros sa masse en kg et sa valeur en pièces d’or.

• une cape d’invisibilité valant 15 pièces d’or et pesant 1 kg;

• une horloge valant 16 pièces d’or et pesant 4 kg;

• un miroir valant 12 pièces d’or et pesant 4 kg;

• un antidote valant 8 pièces d’or et pesant 1 kg;

• une baguette magique valant 10 pièces d’or et pesant 1 kg;

• un diadème valant 30 pièces d’or et pesant 4 kg;

• une épée valant 10 pièces d’or et pesant 6 kg.

Recherche d’un algorithme

1. Afin de remplir le sac, on peut tester toutes les possibilités et choisir la meilleure d’entre elles. Écrire un tel algorithme, qualifié de naïf, qui donne toutes les combinaisons possible et renvoie la solution optimale.

2. En observant que le choix de chaque objet est binaire (choisi ou non), combien de possibilités différentes pourrait-on dénombrer avec 7 objets possibles ? Et avec 30 objets ? Conclure sur la complexité d’un tel algorithme naïf.

3. Un algorithme glouton peut également être utilisé.

   1. Comment se déroule alors cet algorithme glouton ?

   2. Préciser la différence majeure entre l’algorithme naïf et l’algorithme glouton.

Algorithmes gloutons

1. On applique un algorithme glouton en minimisant la masse des objets à choisir.

   1. Quelle est la composition du sac ?

   2. Calculer la valeur en pièces d’or du contenu du sac.

2. On applique un algorithme glouton en maximisant la valeur des objets sans dépasser la masse maximale du sac.

   1. Quelle est la composition du sac dans ce cas?

   2. Quelle est la valeur obtenue en pièces d’or?

3. On peut appliquer l’algorithme glouton en utilisant la valeur massique de chaque objet, c’est à dire la valeur d’1 kg en pièces d’or.

   1. Calculer la valeur massique de chaque objet en pièces d’or par kilogramme.

   2. Comment choisir les objets à mettre dans le sac à dos ?

   3. Déterminer la composition du sac à dos en indiquant les objets choisis, leur ordre de choix ainsi que la valeur en pièces d’or et la masse en kilogramme du sac à dos.

Programmation en Python

1. Écrire, en Python, un algorithme glouton répondant au problème posé. On définira chaque objet par un dictionnaire que l’on rassemblera dans un tableau.

   # on construit un dictionnaire pour chaque objet contenant son nom, sa valeur en pièces d'or et sa masse
   # tous les objets sont réunis dans une même liste objets
   cape = {"nom":'cape',"masse":2,"valeur":15}
   horloge = {"nom":'horloge',"masse":4,"valeur":16}
   miroir = {"nom":'miroir',"masse":4,"valeur":12}
   baguette = {"nom":'baguette magique',"masse":1,"valeur":10}
   antidote = {'nom':"antidote","masse":1,"valeur":8}
   epee = {"nom":'épée',"masse":6,"valeur":10}
   diademe = {"nom":"diadème","masse":4,"valeur":30}
   
   # Tableau contenant les différents objets collectés par le héros
   objets = [cape, horloge, miroir, baguette, antidote, epee, diademe]
   

2. Exécuter votre programme puis en déduire la solution du problème.