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

15. óra

2012.01.30.

Bevezetésnek megvizsgálunk egy tipikus problémát, ami dinamikus programozással közelíthető meg.

Adott összegű részhalmaz

Legyen adott a H = {a1, a2, ..., an} halmaz és az S szám. Döntsük el, hogy létezik-e a H halmaznak olyan részhalmaza, amelyben az elemek összege pontosan S.

Az rögtön látható, hogy az összes részhalmaz ellenőrzése nem fog menni, hiszen egy N-elemű halmaznak 2N részhalmaza van, ez pedig már N = 100 esetén is kezelhetetlen méret. Ami már nem látszik ilyen egyszerűen, az az, hogy a fenti probléma NP-teljes, tehát általános esetben nagy valószínűséggel nem létezik rá hatékony algoritmus. (Wiki)

Ha a bemenetre bizonyos megkötéseket teszünk, akkor már készíthető használható algoritmus. A megkötések a H halmaz elemszámára, illetve az ai elemek nagyságára vonatkozhatnak.

  • Elemszám. Ha N <= 30, akkor a részhalmazok száma nem több, mint 1010, ennek végignézése nem reménytelen.
  • Elemek nagysága. Ha a halmaz elemeinek abszolút-értéke nem túl nagy, akkor viszonylag kevés lehetséges összeg jön szóba. Ebben az esetben a dinamikus programozás célra vezet.

Megoldás dinamikus programozással

Legyen f(i,s) logikai értékeket felvevő függvény, ami pontosan akkor igaz, ha az {a1, a2,...,ai} halmaznak van s összegű részhalmaza. Ha a negatív elemek összege H-ban A, a pozitívaké pedig B, akkor a fenti f függvényt az A és B közé eső s értékekre kell kiszámítani.
  • f(1,s) = (a1=s)
  • f(i,s) = f(i-1,s) vagy (ai=s) vagy f(i-1,s-ai)
A második sor magyarázata: az első i elemből háromféle módon hozható ki az s összeg:
  1. már az első i-1 elemből is kihozható
  2. az i. elem pont s
  3. az első i-1 elemből kihozható s-ai, ehhez hozzávesszük ai-t
Végül az eredeti feladat megoldását az f(N,S) hívás adja meg.

Megjegyzések
  • Amikor a rekurzív függvénnyel leírt megoldást dinamikus programozással (vagyis a már,  kiszámított értékek megjegyzésével és újrahasznosításával) gyorsítjuk, az algoritmus lépésszámát a paraméter-tér méretével becsülhetjük felülről. Esetünkben az első paraméter N különböző értéket vehet fel, a második pedig A+B+1-et.
  • Vegyük észre, hogy a rekurzió i-ben mindig csak az előző értékre hivatkozik, tehát a memorizáláshoz használt tömb-ben elég két "oszlopot használni". A memóriaigény így 2(A+B+1).
A szakköri feladat szoros rokonságban áll az eddig tárgyalt algoritmussal, annak erős általánosításával megoldható.

Feladat