U nastavku ćemo pogledati program u Excel VBA da rješava mali primjerak a problem naprtnjače.
Definicija: S obzirom na skup stavki, od kojih svaka ima težinu i vrijednost, odredite stavke koje ćete uključiti u zbirku tako da ukupna vrijednost bude što je moguće veća, a ukupna težina manja od zadanog ograničenja. Ime je dobio po problemu s kojim se suočava netko tko je ograničen naprtnjačom fiksne veličine i mora ga napuniti najkorisnijim stavkama.
Primjer: 5 stavki s težinama, vrijednostima i ograničenjima kako je navedeno.
U Excelu ovaj problem izgleda ovako:
1. Prvo, deklariramo pet varijabli tipa Double s imenima limit, weight, value, totalWeight i maximumValue.
Ograničenje prigušenja kao dvostruko, težina kao dvostruko, vrijednost kao dvostruko, ukupna težina kao dvostruka, maksimalna vrijednost kao dvostruka
2. Zatim deklariramo pet varijabli tipa Integer s nazivima i, j, k, l, m.
Dim i, j, k, l, m Kao cijeli broj
3. Pokrećemo dvije varijable. Granicu varijable inicijaliziramo vrijednošću ćelije D6. Promjenjivu maximumValue inicijaliziramo s vrijednošću 0.
limit = raspon ("D6"). vrijednost
maksimalna vrijednost = 0
4. Zatim provjeravamo svako moguće rješenje. Možemo ili uključiti stavku (1) ili je izostaviti (0). Počinjemo petlje For Next. Po jedan za svaku stavku.
Za i = 0 do 1
Za j = 0 do 1
Za k = 0 do 1
Za l = 0 do 1
Za m = 0 do 1
5. Izračunavamo težinu i vrijednost mogućeg rješenja.
težina = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
vrijednost = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Samo ako je vrijednost veća od maksimalneVrijednost i težina niža od granice, pronašli smo novo bolje rješenje.
Ako je vrijednost> maksimalnaVrijednost i težina <= granica Tada
7. Ako je točno, novo rješenje zapisujemo u red 4, težinu u totalWeight i vrijednost u maximumValue.
Raspon ("B4"). Vrijednost = i
Raspon ("C4"). Vrijednost = j
Raspon ("D4"). Vrijednost = k
Raspon ("E4"). Vrijednost = l
Raspon ("F4"). Vrijednost = m
ukupna težina = težina
maximumValue = vrijednost
8. Ne zaboravite zatvoriti naredbu If.
Završi ako
9. Ne zaboravite zatvoriti petlje 5 For Next.
Sljedeći m
Sljedeće l
Sljedeće k
Sljedeće j
Sljedeći i
Excel VBA na ovaj način provjerava svako moguće rješenje i kao rezultat toga optimalno rješenje pojavit će se u retku 4. Upamtite, 1 znači da uključujemo stavku, 0 znači da smo je izostavili.
10. Na kraju upišite totalWeight i maximumValue optimalnog rješenja u ćelije B6 i B8.
Raspon ("B6"). Vrijednost = ukupna težina
Raspon ("B8"). Vrijednost = maksimalnaVrijednost
11. Testirajte program.
Proizlaziti:
Zaključak: optimalno je uključiti posljednje četiri stavke s najvećom vrijednošću 15. Ovo rješenje ukupne težine 2 + 1 + 1 + 4 = 8 ne prelazi granicu od 15.
Napomena: postavljanjem pondera i vrijednosti možete riješiti svaki problem s naprtnjačom ove veličine (pogledajte Excel datoteku za preuzimanje).
