Cvicenie - Vypoctova zlozitost algoritmov 18.11.2020 13:00

Zhrnutie prednášky

Cvičenie sa venuje riešeniu problému batohu (0/1 knapsack) pomocou rekurzie a dynamického programovania. Najprv sa implementuje základná rekurzívna funkcia, ktorá pre každý predmet rozlišuje prípady: žiadne predmety, predmet sa nezmestí, alebo sa zmestí a vtedy sa porovná varianta s jeho vložením a bez neho. Na testovacích vstupoch (nosnosť 10, štyri predmety) vychádza maximálna cena 46. Keďže čisto rekurzívne riešenie opakuje výpočty a je pomalé, zavádza sa memoizácia, teda dynamické programovanie zhora nadol, s dvojrozmernou tabuľkou medzivýsledkov inicializovanou na -1. Domácou úlohou je dorobiť aj variant zdola nahor a vypísať obsah tabuľky pri oboch prístupoch.

• - Problém batohu sa rieši rekurziou s tromi prípadmi: nulový počet predmetov, predmet sa nezmestí, predmet sa zmestí.
• - Pri zmestení predmetu sa porovná hodnota s vložením (B1) a bez vloženia (B2) a vráti sa väčšia.
• - Čisto rekurzívne riešenie je pri veľkom počte predmetov pomalé, lebo sa opakujú tie isté výpočty.
• - Memoizácia ukladá medzivýsledky do dvojrozmernej tabuľky B inicializovanej na -1; výpočet sa vykoná, len ak je hodnota ešte záporná.
• - Pri prístupe zhora nadol sa vypočítajú iba volané hodnoty, pri prístupe zdola nahor sa vyplní celá tabuľka.
• - Testovací vstup s nosnosťou 10 a štyrmi predmetmi dáva maximálnu cenu 46.
• - Domáca úloha: dopracovať riešenie zdola nahor a vypísať tabuľku medzivýsledkov pre oba prístupy.

Zhrnutie pripravené s pomocou AI z prepisu videa.