Problème de sac à dos fractionnaire : algorithme gourmand avec exemple

Qu’est-ce que la stratégie gourmande ?

Algorithmes gourmands À chaque étape, on choisit la meilleure solution locale dans l'espoir qu'une succession d'optima locaux aboutisse à une solution optimale globale. À l'instar de la programmation dynamique, ces méthodes ciblent les problèmes d'optimisation, mais elles ne reviennent jamais sur les décisions précédentes.

Les algorithmes gloutons sont généralement simples à écrire, rapides (souvent en temps linéaire ou quadratique), faciles à déboguer et peu gourmands en mémoire. En contrepartie, le résultat n'est pas toujours optimal ; cette stratégie ne fonctionne donc que pour les problèmes dont la structure est reconnue comme sûre face aux algorithmes gloutons.

Les stratégies gloutonnes résolvent l'optimisation combinatoire en construisant une solution A composant par composant Ai. À chaque étape, on choisit Ai de manière optimale en fonction des contraintes actuelles et on réduit le problème à un sous-problème plus petit.

Deux propriétés doivent être vérifiées pour qu'une méthode gloutonne soit correcte :

1. Propriété de choix glouton : À chaque étape, un optimum local mène à un optimum global. Le choix dépend des décisions passées, mais pas des décisions futures.
2. Sous-structure optimale : La solution optimale du problème global contient les solutions optimales de ses sous-problèmes.

Un algorithme glouton comporte cinq composants :

1. Un ensemble de candidats à partir duquel les solutions sont construites.
2. Une fonction de sélection qui choisit le meilleur candidat suivant.
3. Une fonction de faisabilité qui vérifie si un candidat peut étendre la solution partielle actuelle.
4. Une fonction objectif qui évalue une solution complète ou partielle.
5. Une fonction d'évaluation qui signale lorsque la solution est terminée.

L'idée du gourmand

Greedy One trie les paquets uniquement en fonction de leur valeur :

• Trier les colis par ordre décroissant de valeur.
• Parcourez la liste triée et ajoutez chaque paquet au sac à dos si la capacité restante le permet.

Cette règle ne donne pas toujours la réponse optimale. Contre-exemple :

• Paramètres : n = 3, M = 19.
• Paquets : {i = 1 ; W = 14 ; V = 20}, {i = 2 ; W = 6 ; V = 16}, {i = 3 ; W = 10 ; V = 8} — valeur élevée mais aussi poids élevé.
• Le joueur le plus gourmand choisit le paquet 1 d'une valeur totale de 20, alors que le choix optimal (paquet 2, paquet 3) atteint 24.

L'idée de Greedy Two

Greedy Two trie les colis uniquement en fonction de leur poids :

• Triez les colis par ordre de poids croissant.
• Parcourez la liste triée et ajoutez chaque paquet au sac à dos si la capacité restante le permet.

Cette règle n'est pas non plus optimale. Contre-exemple :

• Paramètres : n = 3, M = 11.
• Paquets : {i = 1 ; W = 5 ; V = 10}, {i = 2 ; W = 6 ; V = 16}, {i = 3 ; W = 10 ; V = 28} — léger mais de faible valeur.
• Deux choix gourmands (package 1, pack 2) avec une valeur totale de 26, tandis que le choix optimal (package 3) atteint 28.

L'idée de Greedy Three

L'algorithme Greedy Three corrige ces deux problèmes en combinant valeur et poids en un seul critère de classement. C'est la méthode standard pour le problème du sac à dos fractionnaire.

• Calculez le coût unitaire V[i] / W[i] pour chaque colis.
• Trier les colis par ordre décroissant de coût unitaire.
• Parcourez la liste triée et ajoutez chaque colis si la capacité restante le permet.

Trois tris gourmands par coût unitaire V[i] / W[i]

Idée: calculer le rapport valeur/poids V[i] / W[i] pour chaque paquet, trier par ordre décroissant et prendre d'abord le plus grand rapport disponible jusqu'à ce que le sac à dos soit plein.

Pour le vrai Fractionnaire Dans une variante, lorsque le paquet suivant ne peut pas être placé en entier, on prend une fraction qui remplit exactement l'espace restant. Cette règle supplémentaire est ce qui rend l'algorithme Greedy Three optimal pour le problème du sac à dos fractionnaire.

Étapes de l'algorithme

Pour la variante de séparation et d'évaluation 0/1, la liste triée des coûts unitaires alimente un arbre de recherche :

• Étape 1 : Le nœud racine représente un sac à dos vide. Valeur totale = 0. Limite supérieure = M × coût unitaire maximal.
• Étape 2 : Créez une branche racine en fonction du nombre d'exemplaires du paquet ayant le plus grand ratio pouvant y être intégrés. Pour chaque enfant, recalculez TotalValue, la capacité restante M et UpperBound.
• Étape 3 : Développez d'abord l'enfant ayant la plus grande limite supérieure, dans l'espoir de trouver rapidement une solution satisfaisante.
• Étape 4 : Éliminez tout nœud dont la limite supérieure n'est pas meilleure que la meilleure solution complète actuelle.
• Étape 5 : Lorsque chaque nœud est soit développé, soit élagué, la meilleure solution complète actuelle est optimale.

Pseudo-code de l'algorithme glouton pur du problème du sac à dos fractionnaire :

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Complexité de l'algorithme :

• En utilisant un tri simple (sélection ou à bulles) : O(n²).
• Utilisation du tri rapide ou du tri fusion : O(n log n), dominé par l'étape de tri.

Java Code pour les trois gourmands

Définir la KnapsackPackage classe avec poids, valeur et coût dérivé (le rapport V/W utilisé pour le tri) :

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

Créez ensuite la fonction qui implémente Greedy Three :

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Fonction sac à dosGreProc() dans Java

Explication du code:

1. Enveloppez chaque entrée dans un KnapsackPackage La clé de tri (ratio V/W) est donc précalculée.
2. Trier par ordre décroissant de prix.
3. Prenez chaque paquet entier s'il rentre.
4. Prenez une fraction du paquet suivant pour remplir l'espace restant.
5. Arrêtez dès que la capacité restante atteint zéro.

Note de correction : l'original Java boucle avancée i Ce n'est que lorsqu'un paquet ne rentrait pas, ce qui entraînait le transport répété du même paquet, que la version ci-dessus avance d'un paquet par itération et ajoute une étape de remplissage fractionné, conformément à la véritable règle du sac à dos fractionné.

Java pilote qui exécute l'algorithme sur un exemple fonctionnel :

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code pour les trois gourmands

Commencez par définir le KnapsackPackage classer. le __lt__ Cette méthode permet de trier directement par coût :

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

Implémentez ensuite la routine du sac à dos fractionnaire :

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Fonction sac à dosGreProc() dans Python

Note de correction : l'original Python classe définie comme vide __init__ sans corps, ce qui soulève IndentationErrorLa version ci-dessus supprime le constructeur vide car aucun n'est nécessaire.

Pilote qui exécute l'algorithme sur le premier exemple :

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code pour les trois gourmands

Définir la KnapsackPackage classe:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Implémentez l'algorithme Greedy Three avec une étape de remplissage fractionnaire :

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Fonction KnapsackGreProc() en C#

Contre-exemple : Trois joueurs gourmands sur un sac à dos 0/1

La stratégie « Greedy Three » est optimale pour la variante Fractionnée, mais elle peut être surpassée sur la variante Sac à dos 0/1 (où les objets ne peuvent pas être divisés). Contre-exemple :

• Paramètres : n = 3, M = 10.
• Paquets : {i = 1 ; W = 7 ; V = 9 ; coût = 9/7}, {i = 2 ; W = 6 ; V = 6 ; coût = 1}, {i = 3 ; W = 4 ; V = 4 ; coût = 1}.
• Greedy Three choisit le paquet 1 pour une valeur totale de 9, tandis que le choix optimal 0/1 (paquet 2, paquet 3) atteint 10.

La leçon : n’utilisez l’algorithme « Greedy Three » que lorsque les fractions sont autorisées. Pour la variante 0/1, utilisez… Programmation dynamique à la place.

Applications du sac à dos fractionnaire

• Chargement de marchandises où les produits liquides, en poudre ou en vrac peuvent être fractionnés en fonction du poids.
• Répartition du portefeuille entre les options d'investissement qui acceptent un financement partiel.
• Partage de bande passante dans le cloud, où les flux peuvent consommer une fraction de la liaison.
• Planification du processeur selon un modèle de tranches de temps partagées avec des charges de travail divisibles.
• Allocation des ressources IA où une tâche d'entraînement peut utiliser une fraction d'un GPU.

FAQ