Mai jos vom analiza un program în Excel VBA acea rezolvă o mică instanță a problema rucsacului.
Definiție: Având în vedere un set de articole, fiecare cu o greutate și o valoare, determinați articolele care trebuie incluse într-o colecție, astfel încât valoarea totală să fie cât mai mare posibil și greutatea totală să fie mai mică decât o limită dată. Își trage numele din problema cu care se confruntă cineva care este constrâns de un rucsac de dimensiuni fixe și trebuie să-l umple cu cele mai utile articole.
Exemplu: 5 articole cu greutăți, valori și limită așa cum sunt date.
În Excel, această problemă arată după cum urmează:
1. În primul rând, declarăm cinci variabile de tip Double cu nume limit, greutate, valoare, TotalWeight și maximumValue.
Limita dim ca dublă, greutate ca dublă, valoare ca dublă, totală Greutate ca dublă, valoare maximă ca dublă
2. În continuare, declarăm cinci variabile de tip Întreg cu nume i, j, k, l, m.
Dim i, j, k, l, m Ca întreg
3. Inițializăm două variabile. Inițializăm limita variabilă cu valoarea celulei D6. Inițializăm variabila maximumValue cu valoarea 0.
limit = Range ("D6"). valoare
Valoare maximă = 0
4. Apoi, verificăm fiecare soluție posibilă. Putem fie să includem un articol (1), fie să îl lăsăm în afara (0). Începem 5 bucle pentru următorul. Unul pentru fiecare articol.
Pentru i = 0 la 1
Pentru j = 0 la 1
Pentru k = 0 la 1
Pentru l = 0 la 1
Pentru m = 0 la 1
5. Calculăm greutatea și valoarea unei posibile soluții.
greutate = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
valoare = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Numai dacă valoarea este mai mare decât Valoarea maximă și greutatea este mai mică decât limita, am găsit o nouă soluție mai bună.
Dacă valoare> valoare maximă și greutate <= limită Atunci
7. Dacă este adevărat, scriem noua soluție la rândul 4, greutate la TotalWeight și valoare la MaximumValue.
Gama ("B4"). Valoare = i
Gama ("C4"). Valoare = j
Gama ("D4"). Valoare = k
Gama ("E4"). Valoare = l
Gama ("F4"). Valoare = m
TotalWeight = greutate
Valoare maximă = valoare
8. Nu uitați să închideți declarația If.
End If
9. Nu uitați să închideți buclele 5 For Next.
Următorul m
Următorul l
Următorul k
Următorul j
Apoi eu
Excel VBA verifică fiecare soluție posibilă în acest fel și, ca rezultat, soluția optimă va apărea în rândul 4. Amintiți-vă, 1 înseamnă că includem un element, 0 înseamnă că îl lăsăm în afara.
10. În cele din urmă, scrieți TotalWeight și MaximumValue al soluției optime la celula B6 și B8 respectiv.
Gama ("B6"). Valoare = total Greutate
Range ("B8"). Valoare = maximumValue
11. Testați programul.
Rezultat:
Concluzie: este optim să includeți ultimele patru articole cu o valoare maximă de 15. Această soluție cu o greutate totală de 2 + 1 + 1 + 4 = 8 nu depășește limita de 15.
Notă: făcând variabile greutățile și valorile, puteți rezolva orice problemă cu rucsacul de această dimensiune (consultați fișierul Excel descărcabil).
