Implémentation du problème du sac à dos 0/1 en C/C++ à l'aide de la méthode branch-and-bound

L'idée est de prendre conscience du fait que la méthode gloutonne offre la meilleure solution au problème du sac à dos fractionnaire.

Pour vérifier si un nœud spécifique peut nous fournir une meilleure solution, nous calculons la meilleure solution (par nœud) en mettant en œuvre une approche gloutonne. Si la méthode glouton elle-même calcule plus de solutions que la meilleure solution jusqu’à présent, alors nous ne pouvons pas parvenir à une meilleure solution via les nœuds.

L'algorithme complet est le suivant -

• Triez tous les articles selon l'ordre décroissant du rapport valeur par unité de poids afin que la limite supérieure puisse être calculée à l'aide de la méthode gourmande.

• Initialisez le profit maximum, par exemple maxProfit = 0

• Créez une file d'attente vide Q.

• Les nœuds virtuels de décision créent des arbres et les insèrent ou les mettent en file d'attente dans Q. Le profit et le poids du nœud virtuel sont 0.

• Effectuez les opérations suivantes lorsque Q n'est pas vide ou vide.

  • Création du projet en Q. Soit l'élément d'extraction u.

  • Calculez le profit du nœud de niveau suivant. Si le profit est supérieur à maxProfit, modifiez maxProfit.

  • Calculez les limites du nœud de niveau suivant. Si la limite est supérieure à maxProfit, ajoutez le nœud de niveau suivant à Q.

  • Considérez le cas où le nœud de niveau suivant n'est pas pris en compte ou est considéré comme faisant partie de la solution et ajoutez le nœud à la file d'attente au niveau suivant, mais le poids et le profit ne gèrent pas ou ne prennent pas en compte le nœud de niveau suivant.

Illustration ci-dessous -

Entrée

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

Sortie

The maximum possible profit = 235

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!