Problème de sac à dos fractionnaire : algorithme gourmand avec exemple
Sarah Chen
Qu’est-ce que la stratégie gourmande ?
Les algorithmes gloutons sont comme des algorithmes de programmation dynamique qui sont souvent utilisés pour résoudre des problèmes optimaux (trouver les meilleures solutions du problème selon un critère particulier).
Les algorithmes gloutons mettent en œuvre des sélections locales optimales dans l’espoir que ces sélections conduisent à une solution globale optimale pour le problème à résoudre. Les algorithmes gloutons ne sont souvent pas trop difficiles à mettre en place, rapides (la complexité temporelle est souvent une fonction linéaire ou plutôt une fonction du second ordre). De plus, ces programmes ne sont pas difficiles à déboguer et utilisent moins de mémoire. Mais les résultats ne constituent pas toujours une solution optimale.
Les stratégies gloutonnes sont souvent utilisées pour résoudre le problème d'optimisation combinatoire en construisant une option A. L'option A est construite en sélectionnant chaque composante Ai de A jusqu'à ce qu'elle soit complète (suffisamment de n composants). Pour chaque Ai, vous choisissez Ai de manière optimale. De cette façon, il est possible qu'à la dernière étape vous n'ayez rien d'autre à sélectionner que d'accepter la dernière valeur restante.
Il y a deux éléments essentiels aux décisions cupides :
- Mode de sélection gourmande. Vous pouvez sélectionner la meilleure solution à l'heure actuelle, puis résoudre le sous-problème résultant de la dernière sélection. La sélection des algorithmes gloutons peut dépendre des sélections précédentes. Mais cela ne peut dépendre d’aucune sélection future ni dépendre des solutions de sous-problèmes. L'algorithme évolue de manière à effectuer des sélections en boucle, tout en réduisant le problème donné à des sous-problèmes plus petits.
- Sous-structure optimale. Vous effectuez la sous-structure optimale pour un problème si la solution optimale de ce problème contient des solutions optimales à ses sous-problèmes.
Un algorithme glouton comporte cinq composants :
- Un ensemble de candidats, à partir desquels créer des solutions.
- Une fonction de sélection, pour sélectionner le meilleur candidat à ajouter à la solution.
- Une fonction réalisable est utilisée pour décider si un candidat peut être utilisé pour construire une solution.
- Une fonction objectif, fixant la valeur d'une solution ou d'une solution incomplète.
- Une fonction d'évaluation, indiquant quand vous trouvez une solution complète.
L'idée du gourmand
Avec la première idée, vous avez les étapes suivantes de Greedy One :
- Trier par ordre de valeurs non croissant.
- Considérez à votre tour les colis commandés, mettez le colis considéré dans le sac à dos si la capacité restante du sac à dos est suffisante pour le contenir (ce qui signifie que le poids total des colis qui ont été mis dans le sac à dos et le poids des colis considérés ne dépassent pas la capacité du sac à dos).
Cependant, cet algorithme glouton ne donne pas toujours la solution optimale. Ici vous avez un contre-exemple :
- Les paramètres du problème sont : n = 3 ; M = 19.
- Les forfaits : {i = 1 ; W[je] = 14 ; V[je] = 20} ; {je = 2 ; W[je] = 6 ; V[je] = 16} ; {je = 3 ; W[je] = 10 ; V[je] = 8} -> Excellent rapport qualité-prix mais aussi grand poids.
- L'algorithme sélectionnera le package 1 avec une valeur totale de 20, tandis que la solution optimale du problème est sélectionnée (package 2, package 3) avec une valeur totale de 24.
L'idée de Greedy Two
Avec la deuxième idée, vous avez les étapes suivantes de Greedy Two :
- Trier par ordre de poids non décroissant.
- Considérez à votre tour les colis commandés, mettez le colis considéré dans le sac à dos si la capacité restante du sac à dos est suffisante pour le contenir (ce qui signifie que le poids total des colis qui ont été mis dans le sac à dos et le poids des colis considérés ne dépassent pas la capacité du sac à dos).
Cependant, cet algorithme glouton ne donne pas toujours la solution optimale. Ici vous avez un contre-exemple :
- Les paramètres du problème sont : n = 3 ; M = 11.
- Les forfaits : {i = 1 ; W[je] = 5 ; V[je] = 10} ; {je = 2 ; W[je] = 6 ; V[je] = 16} ; {je = 3 ; W[je] = 10 ; V[je] = 28} -> Léger mais la valeur est également très légère.
- L'algorithme sélectionnera (package 1, package 2) avec une valeur totale de 26, tandis que la solution optimale du problème est (package 3) avec une valeur totale de 28.
L'idée de Greedy Three
Avec la troisième idée, vous avez les étapes suivantes de Greedy Three. En fait, c’est l’algorithme le plus utilisé.
- Trier les colis par ordre de non-augmentation de la valeur du coût unitaire
. Tu as:
- Considérez à votre tour les colis commandés, mettez le colis considéré dans le sac à dos si la capacité restante du sac à dos est suffisante pour le contenir (ce qui signifie que le poids total des colis qui ont été mis dans le sac à dos et le poids des colis considérés ne dépassent pas la capacité du sac à dos).
L'idée: L'idée gourmande de ce problème est de calculer le 
rapport de chacun 
. Triez ensuite ces ratios par ordre décroissant. Vous choisirez le plus haut paquet et la capacité du sac à dos peut contenir ce paquet (remain > wi). Chaque fois qu’un colis est placé dans le sac à dos, cela réduira également la capacité du sac à dos.
Façon de sélectionner les forfaits :
- Considérez l’éventail des coûts unitaires. Vous sélectionnez les forfaits selon des coûts unitaires décroissants.
- Supposons que vous ayez trouvé une solution partielle : (x1,…, Xi).
- La valeur du sac à dos s'obtient :
- Correspondant au poids des colis mis dans le sac à dos :
- Par conséquent, la limite de poids restante du sac à dos est de :
Étapes de l'algorithme
Vous voyez, c'est un problème de trouver max. La liste des packages est triée par ordre décroissant de coûts unitaires pour considérer le branchement.
- Étape 1: La racine du nœud représente l'état initial du sac à dos, dans lequel vous n'avez sélectionné aucun package.
- Valeur totale = 0.
- La limite supérieure du nœud racine UpperBound = M * Coût unitaire maximum.
- Étape 2: Le nœud racine aura des nœuds enfants correspondant à la possibilité de sélectionner le package ayant le coût unitaire le plus élevé. Pour chaque nœud, vous recalculez les paramètres :
- TotalValue = TotalValue (ancien) + nombre de packages sélectionnés * valeur de chaque package.
- M = M (ancien) – nombre de colis sélectionnés * poids de chaque colis.
- UpperBound = TotalValue + M (nouveau) * Le coût unitaire du pack à considérer ensuite.
- Étape 3: Dans les nœuds enfants, vous donnerez la priorité au branchement pour le nœud ayant la limite supérieure la plus grande. Les enfants de ce nœud correspondent à la capacité de sélectionner le prochain package ayant un coût unitaire élevé. Pour chaque nœud, vous devez recalculer les paramètres TotalValue, M, UpperBound selon la formule mentionnée à l'étape 2.
- Étape 4: Répétez l'étape 3 avec la remarque : pour les nœuds dont la limite supérieure est inférieure ou égale aux valeurs maximales temporaires d'une option trouvée, vous n'avez plus besoin de créer une branche pour ce nœud.
- Étape 5: Si tous les nœuds sont ramifiés ou coupés, l’option la plus coûteuse est celle à rechercher.
Pseudo-code de l'algorithme :
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
La complexité de l'algorithme :
- Si vous utilisez un algorithme de tri simple (sélection, bulle…) alors la complexité de l'ensemble du problème est O(n2).
- Si vous utilisez un tri rapide ou un tri par fusion, la complexité de l'ensemble du problème est O (nlogn).
Java code pour Greedy Trois
- Tout d’abord, vous définissez la classe KnapsackPackage. Cette classe a des propriétés qui sont : le poids, la valeur et le coût correspondant de chaque colis. Le coût de propriété de cette classe est utilisé pour la tâche de tri dans l'algorithme principal. La valeur de chaque coût est la
rapport de chaque paquet.
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 = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- Vous créez ensuite une fonction pour exécuter l’algorithme 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 kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
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());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
Explication du code:
- Initialisez le poids et la valeur de chaque paquet de sac à dos.
- Triez les paquets de sacs à dos par coût et par ordre décroissant.
- Si vous sélectionnez le package i.
- Si vous sélectionnez le nombre de colis, je suis suffisant.
- Arrêtez-vous lorsque vous parcourez tous les packages.
Dans ce didacticiel, vous avez deux exemples. Voici le code Java pour exécuter le programme ci-dessus avec deux exemples :
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Vous avez le résultat :
- Premier exemple :
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Deuxième exemple :
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Analysez le premier exemple :
- Les paramètres du problème sont : n = 4 ; M = 37.
- Les forfaits : {i = 1 ; W[je] = 15 ; V[je] = 30 ; Coût = 2.0} ; {je = 2 ; W[je] = 10 ; V[je] = 25 ; Coût = 2.5} ; {je = 3 ; W[je] = 2 ; V[je] = 4 ; Coût = 1.0} ; {je = 4 ; W[je] = 4 ; V[je] = 6 ; Coût = 1.5}.
- Vous triez les packages dans l'ordre sans augmentation de la valeur des coûts unitaires. Vous avez : {i = 2} -> {je = 1} -> {je = 4} -> {je = 3}.
Étapes d'application de l'algorithme pour le premier exemple :
- Définir x1, x2, x3, x4 est le numéro de chaque package sélectionné, correspondant au package {i = 2} -> {je = 1} -> {je = 4} -> {je = 3}.
- La racine du nœud N représente l’état dans lequel vous n’avez sélectionné aucun package. Alors:
- Valeur totale = 0.
- M = 37 (comme proposé).
- UpperBound = 37 * 2.5 = 92.5, dont 37 est M et 2.5 est le coût unitaire du package {i = 2}.
- Avec le forfait {i = 2}, vous avez 4 possibilités : sélectionner 3 forfaits {i = 2} (x1 = 3) ; sélectionnez 2 packages {i = 2} (x1 = 2); sélectionnez 1 package {i = 2} (x1 = 1) et ne sélectionnez pas le package {i = 2} (x1 = 0). Conformément à ces 4 possibilités, vous branchez le nœud racine N à 4 enfants N[1], N[2], N[3] et N[4].
- Pour le nœud enfant N1, vous avez :
- TotalValue = 0 + 3 * 25 = 75, où 3 est le nombre de packages {i = 2} sélectionnés et 25 est la valeur de chaque package {i = 2}.
- M = 37 – 3 * 10 = 7, où 37 est la quantité initiale du sac à dos, 3 est le nombre de colis {i = 2}, 10 est le poids de chaque colis {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, où 75 est TotalValue, 7 est le poids restant du sac à dos et 2 est le coût unitaire du colis {i = 1}.
- De même, vous pouvez calculer les paramètres pour les nœuds N[2], N[3] et N[4], dans lesquels UpperBound est respectivement 84, 79 et 74.
- Parmi les nœuds N[1], N[2], N[3] et N[4], le nœud N[1] a le plus grand UpperBound, vous allez donc d'abord brancher le nœud N[1] dans l'espoir qu'il y aura un bon plan venant de ce côté.
- A partir du nœud N[1], vous n'avez qu'un seul nœud enfant N[1-1] correspondant à x2 = 0 (car le poids restant du sac à dos est de 7, alors que le poids de chaque colis {i = 1} est de 15) . Après avoir déterminé les paramètres du bouton N[1-1], la limite supérieure de N[1-1] est de 85.5.
- Vous continuez à brancher le nœud N[1-1]. Le nœud N[1-1] a 2 enfants N[1-1-1] et N[1-1-2] correspondant à x3 = 1 et x3 = 0. Après avoir déterminé les paramètres de ces deux nœuds, vous voyez que le La limite supérieure de N[1-1-1] est 84 et celle de N[1-1-2] est 82, vous continuez donc à brancher le nœud N[1-1-1].
- Le nœud N[1-1-1] a deux enfants, N[1-1-1-1] et N[1-1-1-2], correspondant à x4 = 1 et x4 = 0. Ce sont deux nœuds feuilles (représentant l'option) car pour chaque nœud le nombre de packages a été sélectionné. Dans quel nœud N[1-1-1-1] représente l'option x1 = 3, x2 = 0, x3 = 1 et x4 = 1 pour 83, tandis que le nœud N[1-1-1-2] représente l'option x1 = 3, x2 = 0, x3 = 1 et x4 = 01 à 81. La valeur maximale temporaire ici est donc 83.
- En revenant au nœud N[1-1-2], vous voyez que la limite supérieure de N[1-1-2] est 82 < 83, vous coupez donc le nœud N[1-1-2].
- En revenant au nœud N2, vous voyez que la limite supérieure de N2 est 84 > 83, vous continuez donc à brancher le nœud N2. Le nœud N2 a deux enfants N[2-1] et N[2-2] correspondant à x2 = 1 et x2 = 0. Après avoir calculé les paramètres pour N[2-1] et N[2-2], vous voyez la limite supérieure de N[2-1] est de 83 et celle de N[2-2] est de 75.25. Aucune de ces valeurs n'est supérieure à 83, les deux nœuds sont donc tronqués.
- Enfin, les nœuds N3 et N4 sont également tronqués.
- Ainsi, tous les nœuds de l'arbre sont ramifiés ou coupés, donc la meilleure solution temporaire est celle à rechercher. En conséquence, vous devez sélectionner 3 colis {i = 2}, 1 colis {i = 4} et un colis {i = 3} d'une valeur totale de 83, le poids total est de 36.
Avec la même analyse du deuxième exemple, vous obtenez le résultat : sélectionnez le package 4 (3 fois) et le package 5 (3 fois).
Python3 codes pour Greedy Three
- Tout d’abord, vous définissez la classe KnapsackPackage.
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
- Vous créez ensuite une fonction pour exécuter l’algorithme Greedy Three.
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
Explication du code:
- Initialisez le poids et la valeur de chaque paquet de sac à dos.
- Triez les paquets de sacs à dos par coût et par ordre décroissant.
- Si vous sélectionnez le package i.
- Si vous sélectionnez le nombre de colis, je suis suffisant.
- Arrêtez-vous lorsque vous parcourez tous les packages.
Voici Python3 codes pour exécuter le programme ci-dessus avec 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)
Vous avez le résultat :
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Code C# pour Greedy Trois
- Tout d’abord, vous définissez la classe KnapsackPackage.
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 = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- Vous créez ensuite une fonction pour exécuter l’algorithme Greedy Three.
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
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, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
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);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
Explication du code:
- Initialisez le poids et la valeur de chaque paquet de sac à dos.
- Triez les paquets de sacs à dos par coût et par ordre décroissant.
- Si vous sélectionnez le package i.
- Si vous sélectionnez le nombre de colis, je suis suffisant.
- Arrêtez-vous lorsque vous parcourez tous les packages.
Voici le code C# pour exécuter le programme ci-dessus avec le premier exemple :
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
Vous avez le résultat :
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Contre-exemple de Greedy Three
L'algorithme de Greedy Three se résout rapidement et peut également être optimal dans certains cas. Cependant, dans certains cas particuliers, cela ne donne pas la solution optimale. Ici vous avez un contre-exemple :
- Les paramètres du problème sont : n = 3 ; M = 10.
- Les forfaits : {i = 1 ; W[je] = 7 ; V[je] = 9 ; Coût = 9/7} ; {je = 2 ; W[je] = 6 ; V[je] = 6 ; Coût = 1} ; {je = 3 ; W[je] = 4 ; V[je] = 4 ; Coût = 1}.
- L'algorithme sélectionnera (package 1) avec une valeur totale de 9, tandis que la solution optimale du problème est (package 2, package 3) avec une valeur totale de 10.
Voici le code java pour exécuter le programme ci-dessus avec le contre-exemple :
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Voici le résultat:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
C'est tout le problème du sac à dos fractionné.
