Nous examinerons un programme dans Excel VBA qui résout une petite instance d’un problème de sac à dos.

Définition: étant donné un ensemble d’articles, chacun avec un poids et une valeur, déterminez les articles à inclure dans une collecte afin que la valeur totale soit aussi grande que possible et que le poids total soit inférieur à une limite donnée. Il tire son nom du problème rencontré par quelqu’un qui est contraint par un sac à dos de taille fixe et doit le remplir avec le plus de nos  articles utiles.

Exemple: 5 articles avec des poids, des valeurs et une limite comme indiqué.

Dans Excel, ce problème se présente comme suit:

1. Premièrement, nous déclarons cinq variables de type Double avec les noms limit, weight, value, totalWeight et maximumValue.

Dim limit As Double, weight As Double, value As Double, totalWeight As Double, maximumValue As Double

2.Ensuite, nous déclarons cinq variables de type Integer avec les noms i, j, k, l, m.

Dim limit As Double, Poids As Double, value As Double, poidstotal As Double,Valeurmaximale As Double

3. Nous initialisons deux variables. Nous initialisons la limite variable avec la valeur de la cellule D6. Nous initialisons la variable

maximumValue avec la valeur 0.
limit = Range("D6").value
Valeurmaximale = 0

4. Ensuite, nous vérifions chaque solution possible. Nous pouvons soit inclure un élément (1), soit le laisser de côté (0). Nous commençons 5 boucles For Next. Un pour chaque article.

For i = 0 To 1

    For j = 0 To 1

        For k = 0 To 1

            For l = 0 To 1

                For m = 0 To 1

5. Nous calculons le poids et la valeur d’une solution possible.

Poids = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
valeur = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m

6. Seulement si la valeur est supérieure à la valeur maximale et le poids est inférieur à la limite, nous avons trouvé une nouvelle meilleure solution.

If value > Valeurmaximale And poids <= limit Then

7. Si vrai, nous écrivons la nouvelle solution à la ligne 4, le poids à poidstotal et la valeur à Valeurmaximale.

Range("B4").value = i

Range("C4").value = j

         Range("D4").value = k

         Range("E4").value = l

         Range("F4").value = m

poidstotal = poids

Valeurtotal = valeur

8. N’oubliez pas de fermer l’instruction If.

End if

9. N’oubliez pas de fermer les 5 boucles For Next.

           Next m

            Next l

        Next k

    Next j

Next i

Excel VBA vérifie chaque solution possible de cette façon et, par conséquent, la solution optimale apparaîtra dans la ligne 4. N’oubliez pas, 1 signifie que nous incluons un élément, 0 signifie que nous l’oublions.

10. Enfin, écrivez totalWeight et maximumValue de la solution optimale respectivement aux cellules B6 et B8.

Range("B6").value = poidstotal

Range("B8").value =Valeurmaximale

11. Testez le programme.

Résultat:

Conclusion: il est optimal d’inclure les quatre derniers éléments avec une valeur maximale de 15. Cette solution avec un poids total de

2 + 1 + 1 + 4 = 8 ne dépasse pas la limite de 15.

Remarque: en faisant la variable poids et valeurs, vous pouvez résoudre tout problème de sac à dos de cette taille