Problem plecakowy - porównanie algorytmów rozwiązujących binarne zagadnienie plecakowe cd.

4. WYNIKI BADAŃ

Przykładowy eksperyment obejmował wpływ liczby przedmiotów na wypełnienie plecaka oraz na czas wykonania przydziału i miał służyć porównaniu efektywności obu algorytmów. Badania zostały przeprowadzone dla losowo generowanych wartości przedmiotów. Zysk oraz objętość były losowane z przedziału [1, 20), a pojemność plecaka została ustawiona na wartość maksymalną i wynosiła 100. Liczba przedmiotów była zwiększana w każdym kroku o 10.

Rezultaty zostały zebrane w Tabeli 1.



Można zauważyć, że czas przydziału jest w przybliżeniu wprost proporcjonalny do ilości przedmiotów (rozmiaru problemu), przy czym zawsze jest on nieco (o 40-50%) dłuższy dla algorytmu opartego na programowaniu dynamicznym. Świadczy to o jego większej złożoności obliczeniowej.

Algorytm oparty na programowaniu dynamicznym, za wyjątkiem pomiaru pierwszego, uzyskuje zawsze 100% wypełnienie plecaka, natomiast wykorzystujący sortowanie – nieco mniejsze. Wynika to stąd, iż po posortowaniu przydzielamy przedmioty po kolei, nie troszcząc się o „fragmentację wewnętrzną”, czyli niewykorzystaną końcówkę pojemności plecaka. To właśnie ona powoduje, że wypełnienie nie osiąga 100%.

Ogólnie programowanie dynamiczne daje lepsze rozwiązania binarnego problemu plecakowego, szczególnie dla instancji o większych rozmiarach. Okupione jest to jednak nieco większym nakładem czasu wymaganym dla uzyskania wyniku.