Poniżej przyjrzymy się programowi w Excel VBA że rozwiązuje mała instancja problem z plecakiem.
Definicja: Mając zestaw przedmiotów, każdy o wadze i wartości, określ elementy, które mają być zawarte w kolekcji, tak aby łączna wartość była jak największa, a całkowita waga była mniejsza niż określony limit. Swoją nazwę wywodzi od problemu, z jakim boryka się ktoś, kto jest skrępowany plecakiem o ustalonej wielkości i musi wypełnić go najbardziej użytecznymi przedmiotami.
Przykład: 5 pozycji z podanymi wagami, wartościami i limitem.
W Excelu ten problem wygląda następująco:
1. Najpierw deklarujemy pięć zmiennych typu Double o nazwach limit, weight, value, totalWeight i maximumValue.
Limit przyciemnienia jako podwójny, waga jako podwójny, wartość jako podwójny, całkowita waga jako podwójny, maksymalna wartość jako podwójny
2. Następnie deklarujemy pięć zmiennych typu Integer o nazwach i, j, k, l, m.
Dim i, j, k, l, m As Integer
3. Inicjujemy dwie zmienne. Inicjujemy limit zmiennej wartością komórki D6. Inicjujemy zmienną maximumValue o wartości 0.
limit = Zakres("D6").wartość
maksymalnaWartość = 0
4. Następnie sprawdzamy każde możliwe rozwiązanie. Możemy dołączyć element (1) lub pominąć go (0). Rozpoczynamy 5 pętli For Next. Po jednym na każdy przedmiot.
Dla i = 0 do 1
Dla j = 0 do 1
Dla k = 0 do 1
Dla l = 0 do 1
Dla m = 0 do 1
5. Obliczamy wagę i wartość możliwego rozwiązania.
waga = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
wartość = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Dopiero gdy wartość jest wyższa niż maksymalnaWartość, a waga jest niższa od limitu, znaleźliśmy nowe, lepsze rozwiązanie.
Jeśli wartość > maksymalnaWartość I waga <= limit Wtedy
7. Jeśli prawda, zapisujemy nowe rozwiązanie w wierszu 4, wagę w totalWeight i wartość w maximumValue.
Zakres("B4").wartość = i
Zakres("C4").wartość = j
Zakres("D4").wartość = k
Zakres("E4").wartość = l
Zakres("F4").wartość = m
całkowita waga = waga
maksymalnaWartość = wartość
8. Nie zapomnij zamknąć instrukcji If.
Zakończ, jeśli
9. Nie zapomnij zamknąć pętli 5 For Next.
Następny m
Następne ja
Następna k
Następny j
Dalej ja
Excel VBA sprawdza w ten sposób każde możliwe rozwiązanie, w wyniku czego w wierszu 4 pojawi się optymalne rozwiązanie. Pamiętaj, 1 oznacza, że uwzględniamy element, 0 oznacza, że go pomijamy.
10. Na koniec wpisz totalWeight i maximumValue optymalnego rozwiązania odpowiednio do komórki B6 i B8.
Zakres("B6").wartość = masa całkowita
Zakres("B8").wartość = maksymalnaWartość
11. Przetestuj program.
Wynik:
Wniosek: optymalne jest uwzględnienie ostatnich czterech pozycji o maksymalnej wartości 15. To rozwiązanie o łącznej wadze 2 + 1 + 1 + 4 = 8 nie przekracza limitu 15.
Uwaga: zmieniając wagi i wartości jako zmienne, możesz rozwiązać każdy problem z plecakiem tej wielkości (patrz plik Excel do pobrania).
