Knapsack – algorithme de force brute

J’ai trouvé ce code pour résoudre le problème de sac à dos en utilisant un mécanisme de force brute (principalement pour apprendre, il n’est donc pas nécessaire d’indiquer que la dynamic est plus efficace). J’ai le code au travail, et comprends la plupart. PLUS. Voici la question:

J’ai remarqué ces deux conditions, que je ne sais pas du tout comment elles fonctionnent et pourquoi elles sont dans le code – je sais qu’elles sont vitales, car toutes les modifications que j’ai apscopes ont donné à l’algorithme des résultats erronés:

// if bit not included then skip if (((i >> j) & 1) != 1) continue; // if bit match then add if (((bestPosition >> j) & 1) == 1) { include.Add(Items[j]); } 

Voici toute la classe, et la façon dont je l’appelle de la manière principale:

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace KnapSack2 { class BruteForce { public double Capacity { get; set; } public Item[] Items { get; set; } public Data Run() { int bestValue = 0; int bestPosition = 0; int size = Items.Length; var permutations = (long)Math.Pow(2,size); for (int i = 0; i<permutations; i++) { int total = 0; int weight = 0; for (int j = 0; j>j)&1)!=1) continue; total += Items[j].v; weight += Items[j].w; } if (weight bestValue) { bestPosition = i; bestValue = total; } } var include = new List(); for (int j = 0; j>j) & 1)==1) include.Add(Items[j]); } return new Data { BestValue = bestValue, Include = include }; }//End of Run } } 

Appelant dans principal

 var ks = new BruteForce { Capacity = MaxWeight, Items = items.ToArray() }; Data result = ks.Run(); 

La classe d’objects n’est qu’un simple object contenant la valeur, le poids et l’ID

Ceci & est le bitwise-AND

L’opérateur binary-AND compare chaque bit de son premier opérande au bit correspondant de son second opérande. Si les deux bits sont à 1, le bit de résultat correspondant est mis à 1. Sinon, le bit de résultat correspondant est mis à 0.

Bien que ce >> soit l’opérateur de décalage à droite

L’opérateur de décalage à droite (>>) décale son premier opérande du nombre de bits spécifié par son deuxième opérande.

Cela étant dit, prenons l’expression suivante

 if (((i >> j) & 1) != 1) continue; 

et essayer de le comprendre.

Initialement, cela i >> j les bits de i par j positions.

Par exemple, prenons la tâche suivante:

 int number = 5; 

La représentation binary du number est:

 0000 0000 0000 0000 0000 0000 0000 0101 

Si nous définissons un nouvel entier comme:

 int shiftNumbersBitByOne = a >> 1; 

La représentation binary de shiftNumbersBitByOne serait alors:

 0000 0000 0000 0000 0000 0000 0000 0010 

Ensuite, sur le résultat de cette opération et sur 1, nous appliquons l’opérateur AND au niveau du bit.

Que fait exactement cet opérateur?

Malgré le fait que la définition soit claire, un exemple le rendra plus clair.

Laissons que nous ayons les nombres binarys a et b , alors le résultat de a&b est le suivant:

 a = 0001 0100 1010 0001 1000 1010 1101 0011 b = 0010 1100 1111 0111 0011 1010 1011 0111 a & b = 0000 0100 1010 0001 0000 1010 1001 0011 

Ceci étant dit, dans cette opération (i >> j) & 1 nous appliquons l’opérateur bitwise-AND entre le résultat de i >> j et la représentation binary de 1

 0000 0000 0000 0000 0000 0000 0000 0001 

Quand le résultat de (i >> j) & 1 serait-il 1?

Cela se produira si et seulement si le dernier chiffre de i >> j est 1.

Mettre à jour

Ci-dessus, nous avons abordé le sujet – je n’ai aucune idée de la façon dont ils fonctionnent . Nous allons maintenant aborder la partie pourquoipourquoi ils sont dans le code .

Définissons notre problème, le problème de Knapsack. Selon wikipedia

Le problème de sac à dos ou de sac à dos est un problème d’optimisation combinatoire: à partir d’un ensemble d’articles comportant chacun une masse et une valeur, déterminez le nombre d’articles à inclure dans une collection de manière à ce que le poids total soit inférieur ou égal à un. limite donnée et la valeur totale est aussi grande que possible.

D’après ce qui précède, il est évident que

 // This is the total weight limit. public double Capacity { get; set; } 

et

 // This is an array with all the given items. public Item[] Items { get; set; } 

De plus, en fonction de votre code, nous pouvons en déduire que chaque élément a une valeur et un poids auxquels on peut accéder en tant que item.v et item.w respectivement. Je vous suggère de renommer cette valeur en valeur et en poids, respectivement, afin que votre code soit plus significatif.

Apparemment, cette int size = Items.Length; est le nombre d’éléments disponibles.

Le point entier de pourquoi partie commence ici :

 var permutations = (long)Math.Pow(2,size); 

Quelle est la permutations ? Que représentent les permutations ?

Avant de répondre à cette question, réfléchissons à la manière dont nous pouvons représenter les éléments de la collection d’éléments qui seront utilisés dans la solution finale. Je soutiens que nous pouvons représenter cela avec un nombre de n bits, à condition que nous ayons n éléments. Comment est-ce possible? Si chaque bit du nombre n-bit fait référence à l’un des n-éléments, il est assez évident que nous pouvons le faire. La valeur du nième bit serait 0 si le nième élément n’était pas inclus dans la solution finale. Alors que sa valeur serait 1, si elle sera incluse.

Ceci étant dit, ce que représentent les permutations est assez clair. Il représente toutes les combinaisons possibles des éléments de la solution finale . Cela est clair, car chaque bit peut avoir 2 valeurs, 0 ou 1. Étant donné que nous avons n bits, le nombre de combinaisons possibles est 2 ^ n.

En fait, pour cette raison, cet algorithme est un algorithme de force brute (nous effectuons une recherche exhaustive). Nous visitons toutes les combinaisons possibles pour trouver la meilleure. Dans la boucle suivante:

 for (int i = 0; i 

vous parcourez toutes les combinaisons possibles.

Ensuite, pour chaque combinaison, vous parcourez la collection d’articles:

 for (int j = 0; j < size; j++) { // Here you check if the item in position j // is included in the current combination. // If it is not, you go to the next value of the loop's variable // and you make the same check. if(((i>>j)&1)!=1) continue; // The j-th item is included in the current combination. // Hence we add it's // value to the total value accumulator and it's weight to // the total weight accumulator. total += Items[j].v; weight += Items[j].w; } 

Maintenant, si le weight est inférieur à la valeur limite et que la valeur totale est supérieure à la meilleure valeur totale actuelle, nous choisissons cette combinaison comme étant la meilleure actuelle:

 bestPosition = i; bestValue = total; 

À la fin, après avoir parcouru toutes les combinaisons disponibles, nous aurons la meilleure.

Ayant trouvé la meilleure combinaison, nous devons parcourir les éléments pour voir lesquels d’entre eux sont inclus dans cette combinaison.

 // The include is a list that will hold the items of the best combination. var include = new List(); // We loop through all the available items for (int j = 0; j>j) & 1)==1) include.Add(Items[j]); } 

Apparemment, les parties de code en question vérifient qu’un certain bit est défini, comme indiqué par les commentaires. La condition

 ((i >> j) & 1) != 1 

est vrai si et seulement si le j ème bit de i est zéro; la condition

 ((bestPosition >> j) & 1) == 1 

est vrai si et seulement si le bit j de bestPosition est un. En ce qui concerne la vue d’ensemble, apparemment, l’implémentation utilise int pour modéliser un ensemble d’éléments, où le jième bit est défini si et seulement si l’élément unique est inclus dans l’ensemble; par conséquent, les tests d’appartenance peuvent être effectués par contrôle de bits. L’implémentation énumère tous les sous-ensembles d’éléments (en utilisant int pour les représenter) afin d’effectuer une recherche exhaustive.

Notez que l’implémentation Delphi pour les ensembles utilise la même approche, mais masque l’indexation des bits dans le code client.