Az S. 2. feladat értékelése és megoldása

Az egyszerű megoldáshoz a dinamikus programozást volt célszerű használni. Miről is szól a dinamikus programozás? Ezt először egy példán keresztül világítjuk meg.

Feladat: Számítsuk ki az n. Fibonacci számot!

Első megoldás:

#include <stdio.h>
#include <sys/types.h>

int n;

long int fib(int n1)
{
  if (n1 < 2) return(n1);
  return(fib(n1-1)+fib(n1-2));
}

main()
{
  scanf("%d",&n);
  printf("F(%d)=%d\n",n,fib(n));
}

Ez a kézenfekvő, a definíciónak megfelelő rekurzív program. Ha teszteljük a futását, már n=45 esetén nagy meglepetések érnek! Ha kiszámoljuk, hogy hány lépést tesz meg a program, azt kapjuk, hogy F(n) kiszámolásához legalább F(n) lépés kell, ami nagyobb mint a^n-2 (ahol a~=1.618), tehát exponenciálisan nagy. Már F(45) kiszámításához is 42 másodpercre van szükség, mivel több, mint F(45)=1134903170 lépés kell. Ha megvizsgáljuk, hogy miért ilyen lassú a program, rájöhetünk, hogy az az oka, hogy bizonyos dolgokat (pld. F(2) értékét) ez a program rengetegszer -- újra meg újra -- kiszámolja.

Azt a módszert, ami ezt a hibát kiküszöböli, dinamikus programozásnak nevezzük. A módszer lényege, hogy ha valamit már egyszer kiszámoltunk, annak eredményét írjuk fel, és eszünkbe se jusson még egyszer kiszámolni, hanem helyette nézzük meg a felírtak között. Persze a módszerhez még az is hozzátartozik, hogy a részfeladatok eredményét jó sorrendben kell kiszámolni, ügyesen a kisebbektől a nagyobbakig, hogy minden pillanatban a felhasználandó részeredmények már fel legyenek írva.

Mit jelent ez a fenti példára? Azt, hogy jobban járunk, ha sorban kiszámoljuk minden i-re F(i) értékét, mint pl. az alábbi programban:

#include <stdio.h>
#include <sys/types.h>

long int F[50], n, i;

main()
{
  scanf("%d",&n);
  F[0]=0;
  F[1]=1;
  for (i=2; i<=n; i++) F[i]=F[i-1]+F[i-2];
  printf("F(%d)=%d\n",n,F[n]);
}

Ez a program már kevesebb, mint 0,01 másodperc alatt kiszámolja F(45) értékét, és nyilván F(n) kiszámításához csak n+1 lépésre van szükség.

A hátizsák feladat megoldása dinamikus programozással

Egy új T[j] érték kiszámolásához azt kell észrevenni, hogy két eset lehetséges:

• Az első i+1 tárgyból ugyanannyi értéket lehet legfeljebb j tömegbe berakni, mint az első i tárgyból, ekkor T[j] értéke nem változik, vagy
• Nagyobb értéket tudunk berakni, ekkor persze használnunk kell az i. tárgyat, és így T[j]=E[i]+T[j-V[i]], ha T[j-V[i]] még az első i tárgyra vonatkozó optimumot tartalmazza. (Itt E[i] jelöli az i. tárgy értékét, V[i] pedig a tömegét. Felhasználjuk a szuboptimalitás elvét, ami durván azt mondja ki, hogy egy optimális megoldásban egy részmegoldás szükségképpen a megfelelő részfeladatnak optimális megoldását adja. Ahol ez nem teljesül, ott esélyünk sincs dinamikus programozással megtalálni az optimumot!)

for (i=0; i<=w; i++) T[i] = 0;
for (i=0; i<n; i++) {
  for (j=w; j>=V[i]; j--) {
    if (T[j-V[i]]+E[i] > T[j]) {
      T[j] = T[j-V[i]]+E[i];
    }
  }
}
printf("Elerheto ertek: %d\n", T[w]);

for (i=1; i<=osszertek; i++) T[i] = w+1;
T[0] = 0;
for (i=0; i<n; i++) {
  for (j=osszertek; j>=E[i]; j--) {
    if ((T[j-E[i]]+V[i] < T[j])) {
      T[j] = T[j-E[i]]+V[i];
    }
  }
}
for (i=osszertek; i>=0; i--) {
  if (T[i] <= w) {
    max = i;
    i = 0;
  }
}
printf("Elerheto ertek: %d\n", max);

Értékelés

A legérdekesebb Engedy Balázs ún. backtrack algoritmusa volt, ez az óriás teszteken minden más versenyzőénél sokkal gyorsabban futott le (2.2 ill. 1.1 másodperc), viszont például az egyik kicsi teszten (100 tárgy, minden tömeg és érték <210) 22 óra alatt sem tudott lefutni. Ezt a teljesítményt -- hosszas vívódás után -- 6 ponttal jutalmaztuk.

A többiek dinamikus programozást használtak. Deák Áron programja a T tömb újrahasznosítása helyett egy mátrixban tárolta az összes i-re az értékeket, ezért a nagy teszteken már nem futott le. Ezenkívül a program egy kisebb hibát is tartalmazott (az iii változó a while ciklusban fel tudott venni n-nél nagyobb értékeket is), ezért 4 pontot kapott. Vincze János és Strenner Balázs programja egyik óriás teszten se futott le, Strenner Balázs 8, Vincze János 7 pontot kapott (a kétmondatnyi leírás miatt). Kuti József szintén 7 pontot kapott (bár az egyik óriás teszten 55 perc alatt lefutott, de az algoritmus leírása hiányzott, a programba írt commentek nem voltak jól érthetőek). Acsai Péter, Földényi Miklós és Nikházy László 9 pontot kaptak, az első óriás tesztre háromnegyed órán belül jól lefutott a programjuk. 10 pontos lett Stippinger Marcell programja, az óriás teszteken 19 illetve 8.5 perc alatt lefutott. Ez a program egy kicsit bonyolultabb, rendezi a tárgyakat érték és tömeg szerint is, és ezt használva bizonyos tárgyakról már eleve tudja, hogy nem lehetnek benne az optimumban. Az 5 pontnál többet elérő versenyzőknek gratulálunk!

Aki kiváncsi egy profi programra is, megtalálhatja David Pisinger programjait a http://www.diku.dk/~pisinger/codes.html oldalon, az itt található MINKNAP program az első óriás teszten 0.04, a másodikon 0.15 másodperc alatt futott le! (A programokat AMD 1800+ processzoron futtattuk).