Problème du Sac à Dos fraction

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

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 M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter