Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2012-2013‎ > ‎

9. óra

Gyakori feladattípus a következő: adott "munkák" egy sorozata, amit optimális módon (legolcsóbban, leggyorsabban, ...) szeretnénk elvégezni. A munkák sorrendje nem változtatható, csak arról dönthetünk, hogy milyen "adagokban" végezzük el őket. Egy-egy adag "költsége" más és más lehet, megoldásunk összköltsége függ a munkák csoportosításától. Az összes lehetséges csoportosítás nem sorolható fel, mert exponenciálisan sok esetről van szó, de a dinamikus programozás segít, ha az m1, m2, ..., mk csoport költsége nem függ az mk+1,... munkák csoportosításától.

Feladatok