nechodím na prednáškyADŠ prednáška 20: Dynamické programovanie 4 - pseudopolynomiálne algoritmy.
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška sa vracia k problému batoha (Robin Hood a pokladnica na zámku) a rieši ho novým pohľadom pomocou rekurzie s memoizáciou. Problém je vo všeobecnosti NP-ťažký, takže polynomiálne riešenie sa neočakáva, no ak sú hmotnosti predmetov malé celé čísla, existuje efektívne riešenie. Rekurzia sa pýta, aké najlepšie riešenie možno vybrať spomedzi prvých k vecí pri voľnej kapacite v, pričom posledný predmet sa buď nechá, alebo zoberie (ak sa zmestí). Počet rôznych otázok je ohraničený n·Dmax, takže časová zložitosť je O(n·Dmax), čo je pseudopolynomiálne riešenie.
- - Problém batoha je NP-ťažký, všeobecné polynomiálne riešenie sa nepredpokladá.
- - Rekurzia zvažuje poslednú vec: nechať ju, alebo zobrať a znížiť voľnú kapacitu o jej hmotnosť.
- - Vetvenie len do prípustných možností vynecháva zjavne neplatné kombinácie, no v najhoršom prípade zostáva O(2^n).
- - Stav rekurzie tvoria dva parametre: počet ešte nerozhodnutých vecí k a voľná kapacita v.
- - Pri malých celočíselných hmotnostiach sa stavy opakujú, takže memoizácia je účinná.
- - Časová zložitosť je O(n·Dmax), čo je pseudopolynomiálny algoritmus závislý od veľkosti nosnosti.
Zhrnutie pripravené s pomocou AI z prepisu videa.
