ALG#7

9.2. Algorytmy żarłoczne, czyli... 237

Aby to dokładniej zilustrować, przeanalizujmy kilka możliwych strategii rozwiązania problemu plecakowego przy użyciu algorytmu „żarłocznego”. Pierwsze, pozornie optymalne rozwiązanie polega na próbach wypełniania plecaka przy pomocy najdroższego sera (sJ): jeśli jego całkow ita objętość mieści się w wolnej przestrzeni, to bierzemy go w całości, w przypadku przeciwnym ucinamy taki jego kawałek, aby nie przekroczyć objętości M i zużyć możliwie największy kawałek tego sera. Następnie zajmujemy się w sposób analogiczny kolejnym w rankingu cen serem ild.

Cóż, wystarczy przetestować „ręcznie” kilka konfiguracji otrzymanych przy pomocy tej metody, aby się przekonać, że nie daje ona najlepszych rezultatów. Najlepszym przykładem może tu być analiza tabelki 9-1, zwłaszcza pozycji 1 i 2.

Przyczyna nieoptymalności rozwiązania jest relatywnie prosta: efekt końcowy (funkcja, którą chcemy zmaksymalizować) zależy nie tylko od aktualnej wartości wkładanych serów, ale i od ich objętości. Może zatem należy patrzeć w pierwszej kolejności nie na parametr c„ ale na w,?

Kilka prób dokonanych „z ołówkiem w ręku” prowadzi nas jednak do niezbyt zachęcających rezultatów także i w tym przypadku i znowu możemy zwątpić w sens metody...

Jeśli obie analizowane „skrajności” nie prowadzą do optymalnego rozwiązania, to jedyne co nam pozostaje, to zmienić strategię postępowania w' taki sposób, aby obiektywnie uwzględniała oba parametry (w„ c,) jednocześnie. Okazuje się, żc jeśli wstępnie poustawiamy dane wejściowe w taki sposób, aby dla dowolnego i zachować stosunek:

to algorytm „żarłoczny” prow-adzi do rozwiązania optymalnego. Aby nie nasycać tego podręcznika zbędną porcją matematyki, dowód powyższego twierdzenia sobie darujemy, gdyż nie jest on istotny.

Popatrzmy na program w C++, który rozwiązuje nasz dylemat plecakowy:

greedy.cpp

const n—3;

void greedy(double M,double W[n],double C(n],double X[n]}

(

double Z=M; // pozostaje do wypełnienia forlint i=0;i<n;i++) ł

if(W[i]>Z) break;

X[i]=l;

Z=Z-W[i);