Exercice : Le problème du sac à dos
Ce problème consiste à remplir un sac à dos avec des affaires ayant un poids et une valeur marchande. Comment remplir ce sac avec les affaires les plus chères sans pour autant dépasser un poids maximum.
Nous sommes ici devant un problème d'optimisation où l'on doit faire des choix.
Objet | B1 | B2 | B3 | B4 | B5 |
|---|---|---|---|---|---|
masse en Kg | 4 | 12 | 1 | 2 | 1 |
valeur en € | 10 | 4 | 2 | 2 | 1 |
Question
Quelle est la meilleure stratégie à adopter pour obtenir un gain maximum ?
Construire cet algorithme.
Indice
Une des approches par un algorithme glouton va consister à prendre toujours l'objet ayant la "valeur massique" c'est à dire un rapport valeur/poids maximum dans la liste sans toutefois dépasser le poids maximum. Sachant que l'on cherche Commençer par établir un tableau nous donnant cette valeur massique pour chaque objet (pour chaque objet on divise sa valeur par sa masse) :
Objet | B1 | B2 | B3 | B4 | B5 |
|---|---|---|---|---|---|
valeur massique en €/Kg |
Solution
Voila à quoi peut ressembler l'algorithme implémentant cette stratégie
Fonction rempliSac(listeObjets,poidsMaxi)
Début
sac=vide
poids=0
TantQue poids < poidsMaxi et que la liste listeObjets est non vide faire
Prendre l'objet obj le plus interessant parmi la liste listeObjets
Si poids + le poids de obj < poidsMax alors
Ajouter l'objet obj dans sac
poids = poids + poids de obj
FinSi
Retirer obj de la liste listeObjet
FinTantQue
Retourner sac
Fin rempliSac