Ci-dessous, nous examinerons un programme en Excel VBA ce résout un petit exemple 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 collection de sorte 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 les objets les plus utiles.
Exemple : 5 articles avec des poids, des valeurs et une limite tels qu'indiqués.
Dans Excel, ce problème se présente comme suit :
1. Tout d'abord, nous déclarons cinq variables de type Double avec les noms limit, weight, value, totalWeight et maximumValue.
Dim limit As Double, poids As Double, valeur 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 i, j, k, l, m As Integer
3. Nous initialisons deux variables. On initialise la variable limite avec la valeur de la cellule D6. On initialise la variable maximumValue avec la valeur 0.
limite = Plage("D6").valeur
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.
Pour i = 0 à 1
Pour j = 0 à 1
Pour k = 0 à 1
Pour l = 0 à 1
Pour m = 0 à 1
5. On calcule 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. Ce n'est que si la valeur est supérieure à la valeur maximale et que le poids est inférieur à la limite, que nous avons trouvé une nouvelle meilleure solution.
If value > maximumValue And weight <= limit Then
7. Si vrai, nous écrivons la nouvelle solution à la ligne 4, le poids à totalWeight et la valeur à maximumValue.
Plage("B4").value = i
Plage("C4").value = j
Plage("D4").valeur = k
Range("E4").value = l
Plage("F4").valeur = m
poids total = poids
valeurmaximale = valeur
8. N'oubliez pas de fermer l'instruction If.
Fin si
9. N'oubliez pas de fermer les boucles 5 For Next.
m suivant
Suivant l
k suivant
j suivant
Ensuite je
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 que 1 signifie que nous incluons un élément, 0 signifie que nous l'omettons.
10. Enfin, écrivez totalWeight et maximumValue de la solution optimale respectivement dans les cellules B6 et B8.
Range ("B6").value = totalWeight
Range("B8").value = maximumValue
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 rendant les poids et valeurs variables, vous pouvez résoudre n'importe quel problème de sac à dos de cette taille (voir fichier Excel téléchargeable).
