Informatika gyűjtemény

Színes kövek (Megoldás)
Szakkörök > BDG Szakkör > 2007/2008 > 8. óra
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

1. Nyers erő és rekurzió

Egy rekurzív függvénnyel adunk maximumot, aminek kér paramétere egy prefix (az eddig meghagyott kövek), és egy index (melyik kőről döntünk most). A prefix $2^m$-féle lehet, ez exponenciális algoritmus, de kb. m=30-ig használható.

opt(prefix, i):
    Ha i > m akkor vissza(m-hossz(prefix)) Elágazás vége
    c := stones[i]
    Ha (c nem_eleme(prefix)) vagy (c=utolsó_karakter(prefix))
        akkor opt1 := opt(prefix+c,i+1)
        különben opt1 := végtelen
    Elágazás vége
    opt2 := opt(prefix,i+1)
    vissza( min(opt1,opt2) )
függvény vége

A megoldás pedig:

minimum := opt('',1)

2. Optimalizálás: paraméter-tér transzformáció és DP

Ahhoz, hogy dinamikus programozásra írjuk át a rekurziót, csökkenteni kell a paraméterel lehetséges számát.

Vegyük észre, hogy a prefixből csak az utolsó karakterét és az eddigi karakterek halmazát használjuk. Tehát a prefix helyett elegendő az utolsó karaktert, az eddigi karakter-halmazt és a prefix hosszát megadni.
Ez legfeljebb $5\cdot 32\cdot 100$ lehetőség. Ezek és az opt() "i" bemenete lesznek a DP tömbjének indexei.

cache[utolsó][halmaz][hossz][ind]

A DP-s változat:

opt(utolsó,halmaz,hossz, i):

Ha cache[utolsó][halmaz][hossz][i] != -1
akkor
    vissza( cache[utolsó][halmaz][hossz][i] )
különben
    Ha i > m
    akkor válasz := (m-hossz)
    különben
        c := stones[i]
        Ha (c nem_eleme(halmaz)) vagy (c=utolsó)
            akkor opt1 := opt(c,halmaz+c,hossz+1,i+1)
            különben opt1 := végtelen
        Elágazás vége
        opt2 := opt(utolsó,halmaz,hossz,i+1)
        válasz := min(opt1,opt2)
    Elágazás vége
    cache[utolsó][halmaz][hossz][i] := válasz
    vissza( válasz)
Elágazás vége

függvény vége

Kódok

Mezei Tamás, C#
Kriván Bálint, C#