Informatika gyűjtemény

NézetNyomtat

Munka (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2009 > Második forduló > 11-13. osztály

Algoritmus

Mohó - a jó rossz algoritmus

Röhejesen "egyszerű" a feladat, az algoritmust érezzük, be kéne bizonyítani :) Mindenesetre: Rendezzük az alkatrészeket elkészítési idejük szerint csökkenő sorrendben, és szépen elkezdjük beválogatni az alkatrészeket a gépekhez a következő szabállyal: az 1. géphez rakjuk, amennyiben $T_1 < T_2$, a 2. géphez, amennyiben $T_2 \leq T_1$ (egyenlőségnél kedvünk szerint rakhatjuk 1-be vagy 2-be, én a 2-t választottam ;)). Ezzel elérhetjük, hogy $\mbox{max}(T_1, T_2)$ minimális legyen.
A feladathoz nem ad jó megoldást a fenti mohó algoritmus, de a tesztadatok pont olyanok, amire viszont jót ad, de általánosságban ROSSZ!

Dinamikus programozás

Forrás/Ötlet: Horváth Gyula - A programozási versenyek szerepe az oktatásban
Jelöljük $t_i$-vel az $i.$ munka idejét, $F$-re pedig: $F=T_{\mbox{összes}} \mbox{ div } 2$
Több oldalról megközelíthető, de a leggyorsabb/memória takarékos mód a következő:
Keressük azt a $T_1$ és $T_2$ számot amire igaz, hogy $T_1+T_2=T_{\mbox{összes}}$, és lehetőleg a legkisebb a különbség a kettő között. Legyen igaz, hogy $T_1\leq T_2$ (nyílván az lenne a legjobb ha a kettő egyenlő lenne). Keressük a legnagyobb $T_1$-t, melyre teljesül, hogy $T_1\leq F$ (ezzel biztosítjuk az előző egyenlőtlenséget), illetve előállítható a munkák egy részhalmazaként. Ezzel elérjük, hogy $T_2-T_1$ a lehető legkisebb legyen, azaz minimalizáljuk $\mbox{max}(T_1,T_2)$-t.
Felveszünk egy $\mbox{cache}$ kétdimenziós tömböt: $\mbox{cache}[X, i]$. Mely azt mondja meg, hogy az adott $X$ időtartam előállítható-e (igen vagy nem) az első $i$ munka egy részhalmazaként, magyarán kioszthatjuk-e az első $i$ munkát úgy a két processzornak, hogy az egyiknél a munkák ideje $X$. $1\leq X\leq F$, hiszen $T_1$ a legnagyobb olyan $X$, melyre $\mbox{cache}[X, N]=\mbox{Igaz}$, nyilvánvalóan $1\leq i \leq N$. Kérdés, hogy hogyan tudjuk ezt a tömböt feltölteni?
Egy adott $(X, i)$-re a $\mbox{cache}$ a következő esetekben tartalmaz $\mbox{Igaz}$-t:
  1. ha $X=t_i$, hiszen nyílvánvalóan $t_i$ kihozható a munkák részhalmazaként, mely egyelemű: $\{t_i\}$, vagy
  2. ha $\mbox{cache}[X, i-1]$ igaz, tehát már az első $i-1$ munkával is összehozható az $X$, vagy
  3. ha $\mbox{cache}[X-t_i, i-1]$ igaz és $t_i < X$, másik oldalról nézve: ha létezik egy olyan szám ($X-t_i$), ami összehozható az első $i-1$-el, akkor a $\mbox{szám}+t_i=X$ összehozható az első $i$-vel.
Legegyszerűbben az alábbi algoritmussal lehet kitölteni (magyarázatért lásd fent):
cache[t[1], 1] = (t[1] <= F)

Ciklus i:=2-től N-ig
    Ciklus X:=1-től F-ig
        cache[X, i] =
            (X == t[i]) vagy
            cache[X, i-1] vagy
            X > t[i] és cache[X-t[i], i-1]
    Ciklus vége
Ciklus vége
A végén kikeressük azt a legnagyobb $X$-et, melyre $\mbox{cache}[X, N]$ igaz, tehát ő lesz $T_1$, ekkor a $\mbox{max}(T_1, T_2) = T_{\mbox{összes}} - T_1$. Innen visszakeresni azt, hogy kiket tettünk be az első processzorhoz (aminek az ideje $T_1$), a következő képpen történik:
X = T1;
i = N;

Ciklus
    Ciklus amíg ( i>0 és cache[X,i] ) 
        i -= 1
    Ciklus vége
    
    // találtunk egy olyat, amikor már nem hozható össze az első i-ből az adott X
    // de i+1-ből már igen, tehát az tuti benne van, ezt vegyük ki (visszafele haladunk)
    X -= t[i+1]
    
    // itt kezdünk valamit azzal az információval, hogy t[i+1] benne van az első processzorban
    ...

amíg X != 0.
A maradék pedig egyértelműen a második processzorhoz került.

Megoldások

Kriván Bálint (C# - mohó aka. rossz megoldás): kb_munka.cs
Kriván Bálint (C# - dinamikus programozás): kb_munka_dp.cs