Spodaj si bomo ogledali program v Excel VBA to rešuje majhen primerek a problem nahrbtnika.
Opredelitev: Glede na niz predmetov, od katerih ima vsak težo in vrednost, določite postavke, ki jih želite vključiti v zbirko, tako da je skupna vrednost čim večja in skupna teža manjša od dane omejitve. Ime izhaja iz problema, s katerim se sooča nekdo, ki ga omejuje nahrbtnik s fiksno velikostjo in ga mora napolniti z najbolj uporabnimi predmeti.
Primer: 5 postavk z utežmi, vrednostmi in omejitvami, kot je podano.
V Excelu je ta težava videti tako:
1. Najprej razglasimo pet spremenljivk tipa Double z omejitvami imen, težo, vrednostjo, totalWeight in maximumValue.
Omejitev zatemnitve kot dvojna, teža kot dvojna, vrednost kot dvojna, skupna teža kot dvojna, največja vrednost kot dvojna
2. Nato razglasimo pet spremenljivk tipa Integer z imeni i, j, k, l, m.
Dim i, j, k, l, m Kot celo število
3. Inicializiramo dve spremenljivki. Omejitev spremenljivke inicializiramo z vrednostjo celice D6. Spremenljivko maximumValue inicializiramo z vrednostjo 0.
limit = Range ("D6"). vrednost
največja vrednost = 0
4. Nato preverimo vsako možno rešitev. Vključimo lahko element (1) ali ga izpustimo (0). Začnemo zanke 5 For Next. Ena za vsak predmet.
Za i = 0 do 1
Za j = 0 proti 1
Za k = 0 proti 1
Za l = 0 do 1
Za m = 0 do 1
5. Izračunamo težo in vrednost možne rešitve.
teža = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
vrednost = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Le če je vrednost višja od največje Vrednost in teža nižja od mejne vrednosti, smo našli novo boljšo rešitev.
Če je vrednost> maksimalnaVrednost in teža <= omejitev Potem
7. Če je res, novo rešitev zapišemo v vrstico 4, težo v totalWeight in vrednost v maximumValue.
Razpon ("B4"). Vrednost = i
Razpon ("C4"). Vrednost = j
Razpon ("D4"). Vrednost = k
Razpon ("E4"). Vrednost = l
Razpon ("F4"). Vrednost = m
skupna teža = teža
maximumValue = vrednost
8. Ne pozabite zapreti stavka If.
Konec Če
9. Ne pozabite zapreti zank 5 For Next.
Naslednji m
Naprej l
Naprej k
Naprej j
Naprej i
Excel VBA na ta način preveri vsako možno rešitev, zato se bo v 4. vrstici prikazala optimalna rešitev. Ne pozabite, da 1 pomeni, da vključimo element, 0 pomeni, da ga izpustimo.
10. Na koncu v celice B6 in B8 napišite totalWeight in maximumValue optimalne rešitve.
Razpon ("B6"). Vrednost = skupna teža
Razpon ("B8"). Vrednost = največja vrednost
11. Preizkusite program.
Rezultat:
Zaključek: optimalno je vključiti zadnje štiri postavke z največjo vrednostjo 15. Ta rešitev s skupno težo 2 + 1 + 1 + 4 = 8 ne presega omejitve 15.
Opomba: s spremenljivko teže in vrednosti lahko rešite katero koli težavo nahrbtnika te velikosti (glejte datoteko Excel, ki jo lahko naložite).
