ALG#8

238

Rozdział 9. Zaawansowane techniki programowania

if(i <n)

X[i]=Z/W[i];

I

void main()

I

double Wtn]-{10,12,16), C(n)=(60,70,80), X[n] = {0,0,0 } ; greedy(20, W, C, X) ; double p-0;

for (int i=0; l<n;p+=»X [i ] *CIi), i++)

cout « i « "\t" « W[i) <<"\t" << C(i] « "\l"

<< X|i] << endl;

COUt << "Total:" << p « endl;

I

Okazuje się. ze rozwiązaniem optymalnym jest wektor    ^w takiej kolej

ności danych, w jakiej są zamieszczone na listingu, gdzie nastąpiła już wstępna „obróbka” wg zacytowanego wcześniej wzoru.

Wniosek z analizy problemu plecakowego powinien być dla Czytelnika następujący: przed przystąpieniem do kodowania programu w naszym ulubionym języku programowania (niekoniecznie w C++), warto poświęcić kilka minut na refleksję, co może znakomicie zwiększyć jakość otrzymanego rozwiązania końcowego.

9.3. Programowanie dynamiczne

Zalety programowania rekurencyjnego uwidaczniają się w prostocie i naturalności formułowania rozwiązań. Niestety rekurencja ma swoje drugie oblicze, o którym łatwo zapomnieć rozważając ją w kategoriach czysto matematycznych. Chodzi oczywiście o to. jak naprawdę formuła rekurencyjna zostanie wykonana przez komputer, ile będzie „kosztowało” zrealizowanie wywołań rekurencyj-nych, powrotów z nich, kombinowanie rezultatów cząstkowych ctc.

Może się zatem okazać, że formalnie szybki algorytm rekurencyjny (rozumując w kategoriach klasy O) będzie znacznie wolniejszy niż to wynika z obliczeń teoretycznych.

Sposobów na zaradzenie temu zjawisku jest kilka (patrz np. rozdział 6). między innymi jest wśród nich... pisanie tylko procedur iteracyjnych!

Wprowadzanie rewolucji w programowaniu w postaci powszechnego zakazu stosowania rekurencji nie jest bynajmniej celem tej książki. Postawmy zatem problem inaczej: czy jest możliwe wykorzystanie korzyści, płynących z rekurencyjnego formułowania rozwiązań, bez używaniu rekurencji?