Le problème du sac à dos en algorithmique (et son implémentation python) est intéressant et fait parti du programme de Sciences numériques et informatique de première.
Ce problème illustre les algorithmes gloutons qui énumèrent toutes les possibilités de résolution d’un problème pour trouver la meilleure solution.
Le problème du sac à dos algorithme python est un problème d’optimisation, c’est à dire une fonction que l’on doit maximiser ou minimiser et des contraintes qu’il faut satisfaire.
Le problème du sac à dos – algorithme Python
Pour un sac à dos de capacité maximale de P et N articles chacun avec son propre poids et une valeur définie, jetez les articles à l’intérieur du sac à dos de telle sorte que le contenu final ait la valeur maximale.
Exemple d’énoncé :
- Capacité maximum du sac à dos : 11 unités
- Nombre d’objet : 5
- Valeurs des objets : {10,50,20,30,60}
- Poids des objets : {1,5,3,2,4}
Quelles est la valeur maximum qu’il est possible de mettre dans le sac à dos en considérant la contrainte de capacité maximum du sac qui est de 11 ?
Algorithme glouton python
Une solution efficace consiste à utiliser un algorithme glouton. L’idée est de calculer le rapport valeur / poids pour chaque objet et de trier l’objet sur la base de ce rapport calculé .
On prends l’objet avec le ratio le plus élevé et on ajoute jusqu’à ce qu’on ne puisse plus en ajouter.
En version fractionnaire il est possible d’ajouter des fractions d’article au sac à dos.
Implémentation du problème du sac à dos Python – version non fractionnaire
Voici une implémentation du problème du sac à dos python en version non fractionnaire, c’est à dire qu’on ne peut pas ajouter de fraction d’un objet dans le sac. Seul des objets entiers peuvent être ajoutés.
class ObjetSac:
def __init__(self, poids, valeur, indice):
self.indice = indice
self.poids = poids
self.valeur = valeur
self.rapport = valeur // poids
#Fonction pour la comparaison entre deux ObjetSac
#On compare le rapport calculé pour les trier
def __lt__(self, other):
return self.rapport < other.rapport
def getValeurMax(poids, valeurs, capacite):
tableauTrie = []
for i in range(len(poids)):
tableauTrie.append(ObjetSac(poids[i], valeurs[i], i))
#Trier les éléments du sac par leur rapport
tableauTrie.sort(reverse = True)
compteurValeur = 0
for objet in tableauTrie:
poidsCourant = int(objet.poids)
valeurCourante = int(objet.valeur)
if capacite - poidsCourant >= 0:
#on ajoute l'objet dans le sac
#On soustrait la capacité
capacite -= poidsCourant
compteurValeur += valeurCourante
#On ajoute la valeur dans le sac
return compteurValeur
poids = [1,5,3,2,4]
valeurs = [10,50,20,30,60]
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite)
print("Valeur maxi dans le sac à dos =", valeurMax)
Le résultat obtenu est le suivant :
py sacados.py Valeur maxi dans le sac à dos = 120
Implémentation du problème du sac à dos python – version fractionnaire
En version fractionnaire de l’agorithme du sac à dos python on peut ajouter des fractions d’objet au sac à dos.
class ObjetSac:
def __init__(self, poids, valeur, indice):
self.indice = indice
self.poids = poids
self.valeur = valeur
self.rapport = valeur // poids
#Fonction pour la comparaison entre deux ObjetSac
#On compare le rapport calculé pour les trier
def __lt__(self, other):
return self.rapport < other.rapport
def getValeurMax(poids, valeurs, capacite):
tableauTrie = []
for i in range(len(poids)):
tableauTrie.append(ObjetSac(poids[i], valeurs[i], i))
#Trier les éléments du sac par leur rapport
tableauTrie.sort(reverse = True)
compteurValeur = 0
for objet in tableauTrie:
poidsCourant = int(objet.poids)
valeurCourante = int(objet.valeur)
if capacite - poidsCourant >= 0:
#on ajoute l'objet dans le sac
#On soustrait la capacité
capacite -= poidsCourant
compteurValeur += valeurCourante
#On ajoute la valeur dans le sac
else:
fraction = capacite / poidsCourant
compteurValeur += valeurCourante * fraction
capacite = int(capacite - (poidsCourant * fraction))
break
return compteurValeur
poids = [1,5,3,2,4]
valeurs = [10,50,20,30,60]
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite)
print("Valeur maxi dans le sac à dos =", valeurMax)
Le résultat obtenu est le suivant :
py sacados.py Valeur maxi dans le sac à dos = 140.0
Liens internes algorithme python :
https://128mots.com/index.php/category/python/
Liens externes algorithme python :
http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf
http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf