Hieronder zullen we kijken naar een programma in Excel VBA Dat lost op een klein voorbeeld van a rugzak probleem.
Definitie: Bepaal op basis van een set items, elk met een gewicht en een waarde, de items die in een verzameling moeten worden opgenomen, zodat de totale waarde zo groot mogelijk is en het totale gewicht lager is dan een bepaalde limiet. Het ontleent zijn naam aan het probleem waarmee iemand wordt geconfronteerd die wordt beperkt door een rugzak met een vast formaat en deze moet vullen met de meest bruikbare items.
Voorbeeld: 5 items met gewichten, waarden en limiet zoals opgegeven.
In Excel ziet dit probleem er als volgt uit:
1. Eerst declareren we vijf variabelen van het type Double met de namen limit, weight, value, totalWeight en maximumValue.
Dimlimiet als dubbel, gewicht als dubbel, waarde als dubbel, totaalgewicht als dubbel, maximumwaarde als dubbel
2. Vervolgens declareren we vijf variabelen van het type Integer met namen i, j, k, l, m.
Dim i, j, k, l, m Als geheel getal
3. We initialiseren twee variabelen. We initialiseren de variabele limiet met de waarde van cel D6. We initialiseren de variabele maximumValue met waarde 0.
limiet = Bereik ("D6").waarde
maximale waarde = 0
4. Vervolgens controleren we elke mogelijke oplossing. We kunnen een item opnemen (1) of weglaten (0). We starten 5 For Next-lussen. Voor elk artikel één.
Voor i = 0 tot 1
Voor j = 0 tot 1
Voor k = 0 tot 1
Voor l = 0 tot 1
Voor m = 0 tot 1
5. We berekenen het gewicht en de waarde van een mogelijke oplossing.
gewicht = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
waarde = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Alleen als de waarde hoger is dan maximumValue en het gewicht lager is dan de limiet, hebben we een nieuwe betere oplossing gevonden.
Als waarde > maximumWaarde en gewicht <= limiet Dan
7. Indien waar, schrijven we de nieuwe oplossing naar rij 4, weight naar totalWeight en value naar maximumValue.
Bereik ("B4").waarde = i
Bereik ("C4").waarde = j
Bereik ("D4").waarde = k
Bereik ("E4").waarde = l
Bereik ("F4").waarde = m
totaalgewicht = gewicht
maximale waarde = waarde
8. Vergeet niet het If-statement af te sluiten.
Stop als
9. Vergeet niet de 5 For Next-lussen te sluiten.
Volgende m
volgende l
volgende k
volgende j
volgende i
Excel VBA controleert elke mogelijke oplossing op deze manier en als resultaat verschijnt de optimale oplossing in rij 4. Onthoud, 1 betekent dat we een item opnemen, 0 betekent dat we het weglaten.
10. Schrijf tot slot totalWeight en maximumValue van de optimale oplossing naar respectievelijk cel B6 en B8.
Bereik ("B6").waarde = totaalgewicht
Bereik ("B8").waarde = maximale waarde
11. Test het programma.
Resultaat:
Conclusie: het is optimaal om de laatste vier items op te nemen met een maximale waarde van 15. Deze oplossing met een totaal gewicht van 2 + 1 + 1 + 4 = 8 overschrijdt de limiet van 15 niet.
Let op: door de gewichten en waarden variabel te maken kun je elk rugzakprobleem van deze omvang oplossen (zie downloadbaar Excel-bestand).
