Az alábbiakban megnézzük a programot Excel VBA hogy megoldja egy kis példája a hátizsák probléma.
Meghatározás: Adott egy tételkészlet, amelyek mindegyike súlyával és értékével rendelkezik, határozza meg a gyűjteménybe felvenni kívánt elemeket, hogy a teljes érték a lehető legnagyobb legyen, és a teljes súly kisebb legyen, mint egy adott határérték. Nevét arról a problémáról kapta, amellyel valaki szembesül, akit rögzített méretű hátizsák korlátozza, és meg kell töltenie a leghasznosabb elemekkel.
Példa: 5 tétel súlyokkal, értékekkel és határértékekkel a megadott módon.
Excelben ez a probléma a következőképpen néz ki:
1. Először öt Double típusú változót deklarálunk, nevekkel limit, súly, érték, totalWeight és maximumValue.
Halvány korlát Dupla, súly Kettős, Érték Dupla, összsúly Kettős, maximumValue Kettősként
2. Ezután öt Integer típusú változót deklarálunk i, j, k, l, m névvel.
Dim i, j, k, l, m Mint egész
3. Két változót inicializálunk. A változó korlátot a D6 cella értékével inicializáljuk. A maximumValue változót 0 értékkel inicializáljuk.
limit = tartomány ("D6"). érték
maximumValue = 0
4. Ezután minden lehetséges megoldást megvizsgálunk. Megadhatunk egy elemet (1), vagy kihagyhatjuk (0). Elkezdjük az 5 For Next ciklusokat. Minden elemhez egyet.
I = 0 és 1 között
Ha j = 0 - 1
K = 0 és 1 között
L = 0 és 1 között
M = 0 és 1 között
5. Kiszámítjuk a lehetséges megoldás súlyát és értékét.
súly = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
érték = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Csak akkor találtunk új jobb megoldást, ha az érték magasabb, mint a maximumValue és a súly alacsonyabb, mint a határérték.
Ha érték> maximumValue És súly <= korlát Akkor
7. Ha igaz, akkor az új megoldást a 4. sorba írjuk, a súlyt a totalWeight -ba és az értéket maximumValue értékbe.
Tartomány ("B4"). Érték = i
Tartomány ("C4"). Érték = j
Tartomány ("D4"). Érték = k
Tartomány ("E4"). Érték = l
Tartomány ("F4"). Érték = m
totalWeight = súly
maximumValue = érték
8. Ne felejtse el bezárni az If utasítást.
Vége Ha
9. Ne felejtse el bezárni az 5 For Next hurkot.
Következő m
Következő l
Következő k
Következő j
Következő i
Az Excel VBA minden lehetséges megoldást így ellenőriz, és ennek eredményeként az optimális megoldás jelenik meg a 4. sorban. Ne feledje, hogy az 1 azt jelenti, hogy tartalmazunk egy elemet, a 0 azt, hogy kihagyjuk.
10. Végül írja be az optimális megoldás totalWeight és maximumValue értékét a B6 és B8 cellába.
Tartomány ("B6"). Érték = totalWeight
Tartomány ("B8"). Érték = maximumValue
11. Tesztelje a programot.
Eredmény:
Következtetés: optimális, ha az utolsó négy tételt legfeljebb 15 értékkel tartalmazza. Ez a megoldás, amelynek össztömege 2 + 1 + 1 + 4 = 8, nem haladja meg a 15 korlátot.
Megjegyzés: a súlyok és értékek változó beállításával minden ekkora hátizsák problémát megoldhat (lásd a letölthető Excel fájlt).
