ADŠ prednáška 18: Dynamické programovanie 2 - maximálny súčet nesusediacich prvkov, cesty po mriežke

Zhrnutie prednášky

Prednáška nadväzuje na predchádzajúcu tému dynamického programovania a demonštruje ju na úlohe maximálneho súčtu nesusediacich prvkov, ilustrovanej ako výber fliaš na polici bez toho, aby sa vybrali dve susediace. Najprv sa ukazuje, že pažravý prístup (výber najväčších hodnôt) nefunguje, keďže existuje jednoduchý protipríklad. Následne sa prezentuje riešenie hrubou silou generovaním všetkých podmnožín pomocou bitových operácií a ich filtrovaním podľa platnosti, s časovou zložitosťou O(n·2^n). Na praktických príkladoch sa demonštruje exponenciálny rast výpočtového času pri zväčšovaní vstupu, čo motivuje potrebu efektívnejšieho riešenia pomocou dynamického programovania, ktoré sa začína programovať v závere úseku.

• - Úloha: vybrať fľaše z police s maximálnym súčtom objemov bez výberu dvoch susediacich fliaš.
• - Pažravý algoritmus (výber najväčšej hodnoty) nefunguje – demonštrované na protipríklade.
• - Riešenie hrubou silou: generovanie všetkých 2^n podmnožín a filtrovanie neplatných pomocou bitových operácií (AND s posunutou maskou).
• - Časová zložitosť hrubej sily je O(n·2^n), čo sa experimentálne potvrdzuje exponenciálnym rastom výpočtového času.
• - Demonštrácia programu v Pythone na testovacích vstupoch s rastúcim počtom fliaš (16 až 22).
• - Motivácia na efektívnejšie riešenie pomocou dynamického programovania namiesto hrubej sily.
• - Začiatok implementácie efektívnejšieho riešenia využívajúceho globálne premenné pre vstupné dáta.

Zhrnutie pripravené s pomocou AI z prepisu videa.