Favicon
NSI Premiรจre

Connexion รฉlรจves

Choisir le(s) module(s) ร  installer :

Algorithmes gloutons

Nous allons รฉtudier une grande "classe" d'algorithmes : Les algorithmes gloutons (ou "greedy algorithm" en anglais).
Mais avant de dรฉfinir les grandes lignes caractรฉrisant cette classe, nous allons nous intรฉresser ร  un exemple classique, de la vie courante, oรน vous utilisez un algorithme gloutons sans le savoir.

1. Un exemple : Le rendu de monnaie

1.1. Prรฉsentation du problรจme

Le rendu de monnaie est un problรจme du quotidien. la question est la suivante :
vous devez rendre 4,24โ‚ฌ avec un systรจme de piรจces et de billets donnรฉs en minimisant le nombre de piรจce ou billets rendus.
rendu de monnaie
Vous avez dรฉjร  rรฉsolu ce problรจme de nombreuses fois, en suivant un algorithme "instinctif".
Nous allons essayer d'analyser votre rรฉsolution de ce problรจme et tenter de gรฉnรฉraliser votre dรฉmarche ร  n'importe quelle somme et ร  n'importe quel systรจme de monnaie (ensemble de piรจces et de billets existants).
le problรจme du rendu de monnaie c'est :
  • Rendre une somme donnรฉe
  • A partir d'un systรจme de monnaie donnรฉ monnaie=[piรจce1, piรจce2, ..., billet1, billet2, ...]
  • En minimisant le nombre de piรจces et de billets rendus.

1.2. Quelques exemples

Pour bien comprendre la dรฉmarche ร  suivre nous allons commencer par rendre quelques sommes "ร  la main".
Nous allons considรฉrer notre systรจme de monnaie europรฉen (sans les centimes): [1, 2, 5, 10, 20, 50, 100, 200, 500].
  1. Trouver TOUTES les possibilitรฉs pour rendre 7โ‚ฌ (il y en a 6 diffรฉrentes ).
  2. Dรฉterminer la solution optimale pour rendre 7โ‚ฌ.

SOLUTION

Cette exemple est "trivial", nous allons donc nous intรฉresser ร  un exemple plus difficile...
  1. Nous allons tenter de rendre 263 โ‚ฌ, je ne vous demande pas de trouver toutes les solutions, puis de dรฉterminer celle qui est optimale mais de donner, d'aprรจs vous, la solution optimale.
  2. Rรฉalisez le mรชme raisonnement pour 264 โ‚ฌ.

SOLUTION

Une fois que vous avez rรฉalisรฉ ces deux exemples, nous allons nous orienter vers la formalisation de l'algorithme que vous utilisez instinctivement. Pour cela rรฉpondez aux questions suivantes :
  1. Quel est le premier billet ร  rendre dans les deux cas prรฉcรฉdents ?
  2. Quels sont les deux critรจres pour choisir ce premier billet ?
  3. Une fois que ce billet est choisit, quel est le nouveau problรจme qui se pose ร  vous ?

SOLUTION

1.3. Premier programme "glouton"

Si vous avez rรฉpondu correctement aux questions prรฉcรฉdentes, vous avez rรฉussi ร  cerner algorithme que vous appliquez naturellement pour rendre la monnaie. Nous allons tenter de programmer cet algorithme.
Vous allez devoir coder une fonction rรฉpondant aux caractรฉristiques suivantes :
  • La fonction prendra en paramรจtre :
    • Le systรจme de monnaie sous forme d'un tableau
    • La somme ร  rendre
    son entรชte sera donc def rendu_glouton(monnaie:list, somme:int):
  • La fonction affichera, dans un premier temps, la suite de billets et de piรจces ร  rendre
L'algorithme ร  suivre sera donc le suivant, d'aprรจs vos recherches prรฉcรฉdentes : 

tant que somme est positif
	si le premier billet est supรฉrieur ร  somme
		passer au billet suivant
	sinon:
		afficher le billet
		enlever le billet ร  somme
Vous pourrez tester votre fonction sur les appels suivants, que vous avez dรฉjร  rencontrรฉ : 

rendu_glouton([100,50,20,10,5,2,1],7)
rendu_glouton([100,50,20,10,5,2,1],4)
rendu_glouton([100,50,20,10,5,2,1],263)			
rendu_glouton([100,50,20,10,5,2,1],264)
def rendu_glouton(monnaie:list, somme:int):
ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Fichier(s) chargรฉ(s) :

SOLUTION

rendu de monnaie

2. Les grands principes des algorithmes gloutons

un glouton ou 'gulo gulo'
Si votre fonction fonctionne vous avez rรฉussi ร  programmer votre premier algorithme glouton, mais quelles sont les grand principes de cette classe d'algorithme ?

Un algorithme glouton est un algorithme qui fait un choix local optimal en espรฉrant que cela conduise ร  une solution globale optimale.
Dans l'exemple prรฉcรฉdent nous avons ร  chaque instant: Et dans notre cas CA MARCHE !!!.
Mais...les algorithmes gloutons ne "fonctionnent" pas toujours...
  1. Tentez de rendre 6โ‚ฌ avec le systรจme suivant : [4,3,1], en suivant votre algorithme. Est-ce optimal ?
  2. Tentez de rendre 8โ‚ฌ avec le systรจme suivant [10,5,2]

SOLUTION

Pour information, notre systรจme de monnaie europรฉen a รฉtรฉ mis au point pour que l'algorithme de rendu de monnaie glouton soit toujours optimal !

3. Bonus : Pour aller plus plus loin

Vous devez ici amรฉliorer votre fonction def rendu_glouton(monnaie:list, somme:int): en def rendu_glouton(monnaie:list, somme:int)->list:.
La fonction ne doit plus afficher les piรจces et billets ร  rendre mais renvoyer un tableau contenant les piรจces et les billets.
def rendu_glouton(monnaie:list, somme:int)->list:
ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Fichier(s) chargรฉ(s) :

SOLUTION

4. Le problรจme du sac ร  dos

Le problรจme du sac ร  dos est un problรจme d'optimisation classique de l'informatique que nous allons tenter de rรฉsoudre grรขce aux algorithmes gloutons.

4.1. Prรฉsentation du problรจme

Nous allons imaginer un voleur en train de dรฉvaliser un appartement.
  • Il ne peut pas porter un sac de plus de 30 kg
  • Il veut ramener un butin maximum
et il a devant lui une plusieurs objets :
  • objet 1 : poids 13 kg et valeur 700 โ‚ฌ
  • objet 2 : poids 12 kg et valeur 400 โ‚ฌ
  • objet 3 : poids 8 kg et valeur 300 โ‚ฌ
  • objet 4 : poids 10 kg et valeur 300 โ‚ฌ
Il doit donc optimiser le remplissage de son sac.
ยฉ Boulet

4.2. Un peu de force brute (ร  la main !)

Vous connaissez sรปrement cette expression informatique de "force brute". Elle consiste ร  attaquer un problรจme frontalement et ร  explorer toutes les possibilitรฉs en profitant de la force de calcul d'un ordinateur.
C'est une technique qui peut, par exemple, รชtre utilisรฉe pour trouver un mot de passe inconnu, en testant toutes les possibilitรฉs.
En considรฉrant la liste d'objets ci-dessus, rรฉpondre aux questions suivantes:
  1. Lister les chargements possibles du sac ร  dos sans se soucier du prix ou de la masse totale pour
    • 4 objets (1 solution c'est facile !)
    • 3 objets (4 solutions)
    • 2 objets (6 solutions)
    • 1 objet (4 solutions c'est facile !)
  2. En vous mettant par groupe de deux, calculer pour chaque chargement :
    • La masse du chargement en kg
    • Le gain du chargement
  3. ร‰liminez les sacs de plus de 30 kg
  4. Dรฉterminez les chargement optimaux

SOLUTION

On peut remarquer qu'avec 4 objets le problรจme est dรฉjร  assez complexe !
Mais dรจs que l'on dรฉpasse 40 objets, un ordinateur actuel est incapable de le rรฉsoudre raisonnablement de cette faรงon !
En effet la complexitรฉ de ce problรจme en en O(2n), oรน n est le nombre d'objets.
  1. Calculer 240
  2. Si une opรฉration sur l'ordinateur prend 1ยตs=10-6s, combien de temps prendront 240 opรฉrations ?

SOLUTION

4.3. Et l'algorithme glouton ?

Comme on vient de le voir il n'est pas envisageable de tester tous les cas, surtout si le nombre d'objets dรฉpasse 30 ou 40.
Nous allons donc tenter d'appliquer la technique de l'algorithme glouton ร  ce problรจme.
Mais comment faire ?
Faut-il choisir initialement le plus petit objet, ou celui qui rapporte le plus ?
Et bien il faut OPTIMISER.
Nous allons donc calculer pour chaque objet son "gain massique" c'est ร  dire ce que rapportera un kg de cet objet. Ainsi la liste prรฉcรฉdente sera agrรฉmentรฉe du gain massique :
  • objet 1 : poids 13 kg et valeur 700 โ‚ฌ, gain massique : 700/13=53,8 โ‚ฌ/kg
  • objet 2 : poids 12 kg et valeur 400 โ‚ฌ, gain massique : 400/12=33,3 โ‚ฌ/kg
  • objet 3 : poids 8 kg et valeur 300 โ‚ฌ, gain massique : 300/8=37,5 โ‚ฌ/kg
  • objet 4 : poids 10 kg et valeur 300 โ‚ฌ, gain massique : 300/10=30 โ‚ฌ/kg
Il ne reste plus qu'a trier cette liste d'objets et ร  commencer par celui qui rapporte le plus "au kg"...
  • Vรฉrifier que le sac n'est pas trop lourd si on l'ajoute
  • Enlever cet objet de la liste
  • ...et recommencer !

4.3.1. Structure de donnรฉes

Pour rรฉsoudre ce problรจme il faut d'abord penser ร  la structure de donnรฉes qui pourra contenir la liste d'objets.
Sachant que chaque objet a trois caractรฉristiques : Il va donc รชtre judicieux d'utiliser un tableau de tableau: 

objet1=[13,700,53.8]
objet2=[12,400,33.3]
objet3=[8,300,37.5]			
objet4=[10,300,30]
liste_objets=[objet1, objet2, objet3, objet4]
Mais, deux problรจmes se posent ร  nous : Nous verrons un peu plus tard dans l'annรฉe diffรฉrents algorithmes de tri, nous allons donc utiliser la mรฉthode sort() de python. Testez le programme ci-dessous : 

tab=[4,3,1,9]
tab.sort()
print(tab)
tab.sort(reverse=True)
print(tab)
Vous avez compris la syntaxe, mais nous voulons trier un tableau de tableaux en choisissant un รฉlรฉment particulier comme critรจre de prix (la valeur massique).
Testez le code ci-dessous : 

tab=[[4,100],[3,200],[1,300],[9,400]]
tab.sort(reverse=True)
print(tab)
  1. Au vu des tests que vous avez fait, quel est le critรจre utilisรฉ par la mรฉthode sort() pour trier des tableaux de tableaux
  2. Grรขce ร  cette remarque, comment doit รชtre modifiรฉe la structure de donnรฉes proposรฉe pour les objets

SOLUTION

4.3.2. Gรฉnรฉration de liste d'objets

Nous avons maintenant une structure de donnรฉes pour la liste des objets ร  mettre dans le cas ร  dos qui pourrait รชtre la suivante : 

obj_test=[[None,13,700],[None,12,400],[None,8,300],[None,10,300]]
None reprรฉsentant ici l'absence de valeurs, la valeur massique de chaque objet sera calculรฉe dans la fonction sacAdos.
Grรขce au tableau de tableaux obj_test nous allons pouvoir tester notre futur programme. Mais si l'on veut voir s'il "rรฉsiste" ร  une liste de 30 objets, il faudra gรฉnรฉrer automatiquement une telle liste.
Le code ci dessous est incomplet. Vous devez le complรฉter pour qu'il respecte la docstring.
from random import randint
def listeobj(n:int)->list:
'''
n est le nombre d'objets dans la liste
la fonction renvoie une liste d'objets alรฉatoire pour le probleme du sac a dos
'''
obj=[[None,randint(1,30), randint(10,100)]...]
....
ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Fichier(s) chargรฉ(s) :
vous pourrez tester ce code avec les deux appels suivants : 

print(listeobj(4))
print(listeobj(30))

SOLUTION

4.3.3. Le code sacAdos

Voici un code incomplet, complรฉtez le et testez le en suivant les questions ci-dessous.
def sacAdos(objets:list,msac:int)-> list:
'''
rรฉsolution du problรจme du sac ร  dos
objets est la liste d'objets
msac est la masse maximale du sac
la fonction renvoie la somme prรฉsente dans le sac et la masse du sac
'''
masse=0
somme=0
#parcours de la liste d'objet et calcul de la valeur massique
for i in range(len(objets)):
objets[i][0]=...
#tri de la liste d'objets du plus rentable au moins rentable
objets.sort(reverse=True)
#parcours de la liste d'objets et choix de ceux ร  mettre dans le sac
for element in objets:
if masse+element[1] < msac:
...
...
return ...
ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”ื”
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Fichier(s) chargรฉ(s) :
  1. Dans la premiรจre partie du programme, on calcule la valeur massique de chaque objet que l'on range ร  la case "0" du sous-tableau reprรฉsentant chaque objet. Complรฉter les pointillรฉs de la ligne 13 pour rรฉaliser cette fonction.
  2. Tester grรขce ร  un affichage cette partie du programme sur le tableau de tableau obj_test.
  3. Dans la deuxiรจme partie du programme, on parcourt chaque รฉlรฉment de la liste et on teste si il est possible de l'ajouter dans le sac ร  dos (lignes 19 et 20). Si cela est possible, deux opรฉrations sont ร  rรฉaliser avant de passer ร  l'objet suivant. Complรฉter les lignes 21 et 22.
  4. Complรฉter enfin la ligne 24 en respectant la docstring.
  5. Pour finir testez votre programme sur obj_test et sur une liste de 30 objets alรฉatoires

SOLUTION

4.3.4. Analyse de l'efficacitรฉ de l'algorithme glouton

Mais au fait, est-ce que notre algorithme glouton nous propose "LA" solution optimale ?
Dans le cas de la liste "test" que vous avez utilisรฉ pendant toute cette partie cela semble รชtre le cas.
Si l'on considรจre deux objets, l'un de 1kg et l'autre de 30kg.

Attribuez ร  chacun une valeur qui fera que notre algorithme glouton ne sera pas optimal.

SOLUTION

Comme on l'a dรฉjร  la "force brute" ne permet pas de trouver une solution quand il y a trop d'objets.
L'algorithme glouton lui proposera toujours une solution, elle sera "pas trop mauvaise" mais ne sera pas toujours optimale...
Il existe des solutions algorithmiques optimales ร  ce problรจme, mais elle sont totalement hors programme !
Elle peuvent faire appel, par exemple ร  la programmation dynamique.