A megoldás
Adattárolás
A munkákat a megszokott módon, két tömbben fogjuk tárolni: a J-edik munka kezdési ideje kezd[j] lesz, a befejezési ideje pedig bef[j].
Az algoritmus
Egy mohó stratégia nevű elvet fogunk alkalmazni. Az ilyen algoritmusokat általában akkor írunk, ha a megoldás folyamatát fel lehet bontani döntési lehetőségek sorozatára. A mohó algoritmus ilyenkor sorra veszi ezeket a döntéseket, és mindegyiknél azt a lehetőséget választja, amelyik az adott pillanatban valamilyen szempontból a legjobbnak tűnik. (Szemben a dinamikus programozással, ahol szinte minden döntés befolyásolja a többit is.) Ez bizonyos esetekben működik, bizonyos esetekben viszont nem.
Most azt fogjuk csinálni, hogy vesszük a munkákat növekvő befejezési idő szerint sorban, és mindig az lesz a döntési feladat, hogy az adott munkát bevegyük-e a megoldás halmazba, vagy sem.
(Az ilyen döntési lehetőségekre bontások sokszor nem egyértelműek, de nem biztos, hogy mindegyikhez jó mohó stratégiát lehet megfogalmazni. Most például vehettük volna a munkákat nem rendezve, vagy olyan döntésekre is felbonthattuk volna a megoldást, hogy mindig választani kell egy munkát az összes közül, amit aztán beválasztunk...
)
Legyen a döntési stratégiánk az, hogy ha az adott munka nem ütközik egy beválasztottal sem, akkor mindig bevesszük, különben meg sosem.
Miért jó ez?
Ez a fejezet a megoldás elkészítéséhez kihagyható, de nagyon tanulságos.
Tegyük fel, hogy ez az algoritmus lefutott, és létrehozott egy $H$ megoldáshalmazt, ami nem maximális elemszámú. (Azaz több munka is el lenne végezhető, mint $\left| H \rigjt|$.) Legyen
$H^*$ egy olyan maximális elemszámú megoldáshalmaz, ami a lehető legkevesebb elemben különbözik $H$-tól!
A következőkben megnézünk egy olyan módszert, ami bármely $H^*$-ra mutat egy másik $H^{**}$ megoldáshalmazt, ami még kevesebb elemben különbözik $H$-tól.
Tehát tudjuk, hogy $\left|H\right| \lt \left|H^*\right|$, és legyen pl.
$H = \left\{m_1, m_2, m_3, ... \right\}$, $H^* =\left\{m^*_1, m^*_2, m^*_3, ...\right\}$.
Legyen $i$ az a legkisebb index, amire $m_i \neq m^*_i$! Tehát $\forall j \lt i$-re $m_j = m^*_j$, ráadásul
$m^*_i$ befejezési ideje biztosan nagyobb, mint $m_i$ befejezési ideje, mert különben a mohó algoritmus is az $m^*_i$ munkát választott volna $H$-ba. Legyen $H^{**} = \left\{m_1, m_2, ..., m_i, m^*_{i+1}, m^*_{i+2}, ..., m^*_{\left|H^*\right|}\right\}$. Ez is egy helyes megoldáshalmaz lesz. Ráadásul $\left|H^{**}\right| = \left|H^*\right|$ és egyel kevesebb elemben különbözik $H$-tól, mint $H^*$. Ez ellentmondás, így nem lehet igaz a kezdeti feltevés mely szerint a mohó algoritmus ebben a feladatban nem találja meg az optimális megoldást.
Leprogramozás
Első lépésben
sorbarendezzük a munkákat befejezési idő szerint. Az egyszerű cserés rendezés nekünk tökéletesen meg fog felelni.
Ciklus i:= 1-től N-ig
Ciklus j:= i+1-től N-ig
Ha bef[i] > bef[j] Akkor
tmp_bef := bef[j]; tmp_kezd := kezd[j];
bef[j]:= bef[i]; bef[i] := tmp_bef;
kezd[j] := kezd[i]; kezd[i] := tmp_kezd;
Elágazás Vége
Ciklus vége
Cilus Vége
Ezzel csak az a probléma, hogy így elvész a munkák eredeti sorszáma, ezért fel kell venni még egy sorsz[] tömböt, aminek kezdetben minden eleme: sorsz[i] = i, és ennek az elemeit is ugyanúgy rendezni kell. Nincs más hátra, mint sorra venni a munkákat, és mindről eldönteni, hogy bekerülhet-e. Felvehetnénk még egy tömböt: bek[i], az i-edik beválasztott munka sorszáma. Ha nem trükközünk bitműveletekkel, akkor mind a kezd[], mind a bef[], mind a sorsz tömbök elemenként két byteot foglalnak, így 64k-s (DOS-os) memóriakorlátok mellett már nem tudunk felvenni még egy tömböt. A bitműveletekkel trükközés viszont nagyon kockázatos dolog, mert minden egyes architektúrák másképpen ábrázolják a számokat bit-szinten. (És sokat kéne trükközni, hogy ezt megkerüljük.) Ezért egy másik trükköt alkalmazunk, mégpedig azt, hogy minden beválasztott elem sorszámát a -1-szeresére változtatjuk. (Ez is 1 bitnyi információ, de nem feltétlenül 1 bit változást okoz a változó memóriaképében.)
szabad := 1;
szamol := 0;
Ciklus i:= 1-től N-ig
Ha kezd[i] >= szabad Akkor
sorsz[i] := -szorsz[i];
szabad := befi] + 1;
szamol := szamol + 1;
Elágazás Vége
Ciklus vége
Amint látható, a szamol változó a beválasztott elemek sorszámát tárolja, a szabad változó
pedig az aktuális első olyan napot, amin már lehet újabb munkát vállalni. Az eredmény innen már könnyen kiíratható:
Kiir(szamol); Ujsor;
Ciklus i := 1-től N-ig
Ha sorsz[i] < 0 Akkor
Kiir(-sorsz[i], ' ');
Elágazás Vége
Ciklus Vége
Megoldások
