Algoritmusok
Kis bemenetre
Mohó algoritmus. Feltehető, hogy az optimális esetben (amikor a legtöbb a továbbjutó), a továbbjutók pontosan C feladatot oldottak meg. Újra és újra kiválasztunk C db feladatot, csökkentjük a hozzájuk rendelt megoldásszámot, és növeljük eggyel a továbbjutók számát. (Átfogalmazva: újra és újra "generálunk" egy továbbjutót, kiválasztva, hogy ő melyik C feladatot oldotta meg.)
Amitől mohó: a feladatokat megoldásszám szerint csökkenően rendezzük, és mindig a C legnagyobbhoz rendelünk egy továbbjutót. A levonások után újrarendezünk.
(S[1], S[2], ..., S[P]) := csökkenően_rendez(S[1], S[2], ..., S[P])
opt := 0
Ciklus amíg S[C] > 0
Ciklus i:= 1-től C-ig
S[i] := S[i] - 1
Ciklus vége
opt := opt + 1
(S[1], S[2], ..., S[P]) := csökkenően_rendez(S[1], S[2], ..., S[P])
Ciklus vége
Bizonyítás...
Nagy bemenetre
Mivel minden továbbjutó legalább C feladatot megoldott, ezért az összesen megoldott feladatok száma nem lehet kevesebb, mint a továbbjutók számának C-szerese. Innen:
$\displaystyle{opt \le \left\lfloor\frac{S_1+S_2+\ldots+S_P}{C} \right\rfloor}$
Ha egy feladatra több megoldás érkezett, mint a fent kiszámolt felső becslés, akkor
a becslés feletti megoldások eldobhatók, és ez nem csökkenti az optimumot, hiszen eldobhatók kiesők megoldásai.
A csökkentések után újraszámolható a felső becslés, ami csökkenhet. Addig folytatjuka becslés élesítését, amíg eljutunk egy olyan állapotba, ahol már semelyik feladatra adott megoldásszám nem haladja meg a becslést. Ekkor megtaláltuk az optimumot.
Ciklus
opt0 := (S[1]+S[2]+ ...+S[P])/C
Ciklus minden i-re
Ha S[i] > opt0 akkor S[i] := opt0 Elágazás vége
Ciklus vége
amíg volt változás
opt := opt0
Bizonyítás...
Kódok
