1. megoldás: Mohó algoritmus (nem mindig jó)
A feladatokat (süteményeket) hossz (sütési idő) szerint csökkenően rendezzük, majd sorra vesszük, és
mindig abba a sütőbe tesszük, ahol a minimális az eddigi össz-idő.
Ellenpélda
A "
12 5 5 2 2 2 2 2 2 2 2 2 2" bemenetre a mohó algoritmus a
11
1: 5 2 2 2
2: 5 2 2
3: 2 2 2 2 2
megoldást adja, az optimális
10
1: 5 5
2: 2 2 2 2 2
3: 2 2 2 2 2
helyett.
A következő két (optimális megoldást adó) algoritmus alapötlete, hogy
ha két sütő munkaidejét kiszámoltuk ($t_a, t_b$), akkor a harmadik sütő
ideje $t_c = \sum t_i -t_a - t_b$, és a teljes munkaidő
$ t = max (t_a, t_b, t_c) $.
2. megoldás: Rekurzió
Egy opt() függvényt írunk, ami paraméterül azt kapja, hogy hányadik feladatot akarjuk elvégezni, és a három sütőben eddig mennyi a betervezett sütések összideje.
Az előző megjegyzés szerint a harmadik sütési idő számítható, de az érthetőség kedvéért
azt is beleírjuk az algoritmusba. A feladat megoldását az opt(1,0,0,0) adja, ami azt jelenti, hogy az első feladat jön, és még semelyik sütőben nem sütöttünk.
függvény opt(i,a,b,c)
Ha i > n akkor
vissza( max(a,b,c) )
különben
ra := opt(i+1,a+t[i],b,c)
rb := opt(i+1,a,b+t[i],c)
rc := opt(i+1,a,b,c+t[i])
vissza( min(ra,rb,rc) )
Elágazás vége
függvény vége
Optimalizálás:
c = t - a - b, illetve az "opt" értékei táblázatolhatók, és
egyszerre elég két
i indexre tárolni az értékeket.
3. megoldás: Okos táblázatolás
Jelentse lehet[j,k] azt, hogy a lehetséges a sütési feladatok
olyan beosztása, hogy az első sütő j, a második pedig k ideig
sütött. (Ekkor a harmadik sütő ideje l = összidő - j - k, és a munkaidő
max(j,k,l).
Ha a lehet[] tömb értékeit kiszámoltuk, akkor az optimum egy kétdimenziós minimumkiválasztással határozható meg.
lehet[] := hamis;lehet[0,0] := igaz; s := 0
Ciklus i :=1-tól n-ig
s := s + t[i]
t := t[i]
Ciklus j := 1200-tól 0-ig
Ciklus k := 1200-tól 0-ig
Ha j>=t és lehet[j-t,k] akkor
lehet[j,k] := igaz
Elágazás vége
Ha k>=t és lehet[j,k-t] akkor
lehet[j,k] := igaz
Elágazás vége
Ciklus vége
Ciklus vége
Ciklus vége
opt := 1200
Ciklus j := 0-tól 1200-ig
Ciklus k := 0-tól 1200-ig
Ha lehet[j,k] akkor
opt := min(opt, max(j,k,s-j-k))
Elágazás vége
Ciklus vége
Ciklus vége
Kódok
