A megoldás algoritmusa
Tároljuk egy t[] tömbben a lehetőségek számát, jelentse t[i] azt, hogy az i., (i+1)., ..., n. tárgy hányféle módon kerülhet a kemencébe.
Ha az i. tárgyat d másikkal együtt égetjük ki, akkor a maradék tárgyak elhelyezéseinek száma t<i + d + 1>, ahol d lehetséges értékei: 0, 1, ..., k - 1. (t[n + 1] = 1) Minden lehetséges d más csoportosítást ad, tehát d-re összegezve kapjuk meg t<i> értékét.
A t[] tömb elemei t[n], t[n-1], ..., t[1] sorrendben határozhatók meg. t[n] = 1 és az utolsó k tömbelem 1, 2, 4, ..., 2k - 1, hiszen ezekre még nincs kapacitás korlát, ezért minden tárgy esetén dönthetünk, hogy új csoportot kezdünk-e.
Az algoritmus:
Be: n, k
t[n]:=1
Ciklus i := (n - 1)-től (n - k + 1)-ig
t[i] := 2 * t[i + 1]
Ciklus vége
Ciklus i := (n - k)-tól 1-ig
a := 0
Ciklus j := (i + 1)-től (i + k)-ig
a:=a + t[j]
Ciklus vége
t[i] := a
Ciklus vége
Ki: t[1]
Megoldások
