ZADANIE 4 (zadanie nr 2 dla studiów zaocznych).

Celem ćwiczenia jest przybliżenie pojęcia algorytmu dokładnego i przybliżonego, zapoznanie się ze sposobem
przeprowadzania eksperymentalnej oceny dokładności algorytmu przybliżonego oraz eksperymentalnej analizy
efektywności algorytmów.

Należy:

•

Napisać i uruchomić program realizujący rozwiązywanie zagadnienia plecakowego za pomocą 3
algorytmów: zachłannego (AZ), programowania dynamicznego (APD) i generującego wszystkie podzbiory
zbioru n-elementowego (AP).

•

Porównać wyniki (wartości maksymalnego zysku) uzyskane za pomocą poszczególnych algorytmów (dla
danych zamieszczonych w tabeli).

•

Wyznaczyć względne odchylenie od wartości optymalnych rozwiązań uzyskanych za pomocą algorytmu
zachłannego (AZ).

•

Porównać czasy wykonywania obliczeń przez poszczególne algorytmy.

•

Wyprowadzić wnioski.

Uwaga: obliczenia przeprowadzić dla wartości



i





generowanych z przedziału [1,10].

Dla chętnych: uzupełnić podane implementacje o możliwość wyświetlania zbioru projektów wybranego do
realizacji.


Tabela 1. Wartości maksymalnego zysku uzyskiwane przez poszczególne algorytmy

n

b

AZ

APD

AP

5

5

10

10

15

15

20

20

25

25

30

30

100

100

100

5000

1000

1000

1000

50000

10000

10000

10000

50000

Tabela 2. Względne odchylenie od optimum,

, dla AZ

n

b

 [%]

n

b

 [%]

5

5

100

100

10

10

100

500

15

15

1000

1000

20

20

1000

5000

25

25

10000

10000

30

30

10000

50000

średnio:

średnio:

Tabela 3. Czasy wykonywania obliczeń przez poszczególne algorytmy w sekundach

n

b

AZ

APD

AP

5

5

10

10

15

15

20

20

25

25

30

30

100

100

100

500

1000

1000

1000

5000

10000

10000

10000

50000

Wnioski: