Níže se podíváme na program v Excel VBA že řeší malá instance a problém s batohem.
Definice: Vzhledem k sadě položek, z nichž každá má váhu a hodnotu, určete položky, které chcete zahrnout do kolekce, aby celková hodnota byla co největší a celková hmotnost byla menší než daný limit. Název odvozuje od problému, se kterým se potýká někdo, kdo je omezen batohem pevné velikosti a musí jej naplnit nejužitečnějšími položkami.
Příklad: 5 položek s váhami, hodnotami a limitem, jak je uvedeno.
V aplikaci Excel tento problém vypadá následovně:
1. Nejprve deklarujeme pět proměnných typu Double s názvy limit, weight, value, totalWeight a maximumValue.
Dim limit As Double, váha As Double, hodnota As Double, totalWeight As Double, maximumValue As Double
2. Dále deklarujeme pět proměnných typu Integer s názvy i, j, k, l, m.
Dim i, j, k, l, m jako celé číslo
3. Inicializujeme dvě proměnné. Inicializujeme variabilní limit s hodnotou buňky D6. Inicializujeme proměnnou maximumValue s hodnotou 0.
limit = rozsah („D6“). hodnota
maximumValue = 0
4. Dále zkontrolujeme každé možné řešení. Můžeme buď zahrnout položku (1), nebo ji vynechat (0). Začínáme smyčky 5 pro další. Ke každé položce jeden.
Pro i = 0 až 1
Pro j = 0 až 1
Pro k = 0 až 1
Pro l = 0 až 1
Pro m = 0 až 1
5. Vypočítáme hmotnost a hodnotu možného řešení.
hmotnost = 12 * i + 2 * j + 1 * k + 1 * l + 4 * m
hodnota = 4 * i + 2 * j + 2 * k + 1 * l + 10 * m
6. Pouze pokud je hodnota vyšší než maximumHodnota a hmotnost je nižší než limit, našli jsme nové lepší řešení.
Pokud hodnota> maximumValue And weight <= limit Then
7. Pokud je to pravda, zapíšeme nové řešení do řádku 4, váha do totalWeight a hodnota do maximumValue.
Rozsah („B4“). Hodnota = i
Rozsah („C4“). Hodnota = j
Rozsah („D4“). Hodnota = k
Rozsah ("E4"). Hodnota = l
Rozsah ("F4"). Hodnota = m
celková hmotnost = hmotnost
maximumValue = hodnota
8. Nezapomeňte zavřít příkaz If.
Konec If
9. Nezapomeňte zavřít smyčky 5 pro další.
Další m
Další l
Další k
Další j
Příště já
Excel VBA tímto způsobem kontroluje každé možné řešení a v důsledku toho se optimální řešení objeví v řádku 4. Pamatujte, že 1 znamená, že zahrneme položku, 0 znamená, že ji vynecháme.
10. Nakonec do buňky B6 a B8 zapište celkovou hmotnost a maximální hodnotu optimálního řešení.
Rozsah („B6“). Hodnota = totalWeight
Rozsah ("B8"). Hodnota = maximumValue
11. Otestujte program.
Výsledek:
Závěr: optimální je zahrnout poslední čtyři položky s maximální hodnotou 15. Toto řešení s celkovou hmotností 2 + 1 + 1 + 4 = 8 nepřekračuje hranici 15.
Poznámka: změnou hmotnosti a hodnot můžete vyřešit jakýkoli problém s batohem této velikosti (viz soubor aplikace Excel ke stažení).
