Úvod - specifikace úlohy

Teoretický úvod je v plném znění k nalezení zde.

Popis použitých algoritmů

Dynamické programování

Princip tohoto řešení je rozložení problému na menší. Využívá se toho, že je-li řešení problému s k věcmi a nosností N optimální a obsahuje k-tou věc, pak optimální řešení problému s prvními k-1 věcmi a nosností (N - váha k) je toto řešení po vyjmutí k-té věci. Výhoda DP spočívá v tom, že si pamatujeme co jsme již počítali a nepočítáme to znovu.

Metoda větví a hranic

Algoritmus je vylepšená metoda řešení hrubou silou. Vylepšení spočívá v tom, že jsou prozkoumávány pouze ty větve, které ještě potenciálně mohou přinést lepší řešení, než nejlepší dosud nalezené. Potenciální cena řešení při prozkoumávání i-té věci je součet cen věcí, které už při procházení této větve v batohu jsou a cen všech věcí, které v této větvi ještě nebyly prozkoumány a tedy mohou potenciálně být v řešení.

Heuristika "cena / váha"

Jedná se o stejný algoritmus jako v první úloze, předměty se seřadí podle klesajícího poměru cena / váha a předměty které se ještě vejdou do batohu se postupně přidávají.

Výsledky měření

zadání DP BB HR
cena kroky cena kroky cena kroky
4 352 400 352 12 342 3
10 1125 1000 1125 146 1104 8
15 1814 3000 1814 178 1808 14
20 2335 5000 2335 3491 2322 17
22 2501 5500 2501 12755 2481 17
25 2954 7500 2954 33225 2941 20
27 3143 9450 3143 38631 3131 22
30 3581 12000 3581 184291 3565 24
32 3694 14400 3694 263077 3684 26
35 4081 17500 4081 677279 4071 28
37 4222 20350 4222 721623 4213 29
40 4628 24000 4628 8576258 4621 31

Zhodnocení

Z tabulky je vidět, že všechny tři metody dávají zhruba stejnou cenu řešení. Heuristika dává průměrně nižší ceny než zbylé dvě metody, to ovšem za cenu řádově menšího počtu kroků nutných k nalezení řešení. Jako nejhorší z hlediska počtu kroků se jeví metoda větví a hranic, počet kroků u ní s množstvím věcí neúměrně roste. Nejmenší počet kroků potřebuje heuristika, u ní je počet kroků řádově srovnatelný s počtem věcí (je o něco menší, protože pokud je batoh již plný, nepokračuje se v hledání dalších předmětů, jinak by byl počet kroků roven počtu předmětů).

Zdrojové kódy

Třída pro práci s batohem
cpp html
Třída pro čtení vstupu
cpp html
Hlavní program a jednotlivé algoritmy
cpp html