Algorithmes Gloutons

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é 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)

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], i))
    
        # 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 Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :