Problème du Sac à Dos fraction
Problème ! Étant donné les poids et les valeurs de n articles, nous devons mettre ces articles dans un sac à dos de capacité C pour obtenir la valeur totale maximale dans le sac à dos.
Exemple :
articles[] = [(60, 10), (100, 20), (100, 60), (40, 20)] ; C= 50
200.0 ( articles de poids 10, 20 et 20)
200.0 ( articles de poids 10, 20 et 20)
Une solution naive consisterait à essayer tous les sous-ensembles possibles avec des fractions différentes, mais cela prendrait trop de temps.
Une solution efficace consiste à utiliser l'approche gloutonne. L'idée de l'approche gloutonne est de calculer le rapport valeur/poids pour chaque article et de trier les articles sur la base de ce rapport. Ensuite, prenez l’élément avec le rapport le plus élevé et ajoutez-le jusqu’à ce que nous ne puissions plus ajouter l’élément suivant dans son intégralité et à la fin, ajoutez-le autant que possible. Qui restera toujours la solution optimale à ce problème.
class Article: def __init__(self, benefice, poids): self.benefice = benefice self.poids = poids self.rapport = benefice/poids # définir une fonction __lt__ pour comparer deux articles def __lt__(self, article): return self.rapport < article.rapport def Sac_Dos(objets, poids_max): articles = [] for i in range(len(objets)): articles.append(Article(objets[i][0], objets[i][1])) # trier dans l'ordre décroissant des rapports articles.sort(reverse=True) total = 0 for article in articles: if poids_max - article.poids >= 0: poids_max -= article.poids total += article.benefice else: fraction = poids_max / article.poids total += article.benefice * fraction poids_max = poids_max - (article.poids * fraction) break return total articles = [(60, 10), (100, 20), (100, 60), (40, 20)] capacite = 50 max = Sac_Dos(articles, capacite) print("Valeur maximale en sac à dos =", max)
Valeur maximale en sac à dos = 200.0
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa