Zadania zaliczeniowe

Uwagi ogólne:

Terminem zaliczenia programu jest dzień wyszczególniony w terminarzu zajęć. Tylko w tym dniu można uzyskać maksymalną punktację za program (w przypadku niemożności zaliczenia programu na wyznaczonych zajęciach należy umowić się na zaliczenie indywidualne).
W każdym programie należy zapewnić możliwość wprowadzania danych z klawiatury. W niektórych zadaniach należy dodatkowo umożliwić wczytywanie danych wejściowych z pliku tekstowego (jeśli ta opcja jest konieczna zaznaczono to w treści zadania).
Do każdego programu należy stworzyć automatyczny generator danych wejściowych, który zostanie wykorzystany do generowania danych na potrzeby testów obliczeniowych.
Sprawozdanie z danego tematu powinno być zapisane w pliku *.pdf i wysłane przez USOSMAIL najpóźniej 3 dni po zaliczeniu programu.
W sprawozdaniu osie wykresów powinny być opisane (jakie dane na której osi, jednostki pomiaru). Każdy punkt na wykresie powinien być obliczony jako średnia z 10 pomiarów. Na wykresie należy przedstawić błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podać te dane w postaci tabelarycznej.
Każde sprawozdanie powinno zawierać informację o tym, w jakim języku programowania zakodowano poszczególne algorytmy, na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

Zaimplementuj algorytmy rozwiązujące 0-1 problem plecakowy:
- algorytm programowania dynamicznego AD
- algorytm zachłanny AZ (sortowanie po współczynniku opłacalności: wartość na jednostkę masy)
- algorytm siłowy AB.
Wszystkie implementacje powinny spełniać następujące wymagania:
- należy umożliwić wczytywanie danych (zbiór przedmiotów z parametrami i pojemność plecaka) z klawiatury oraz z pliku tekstowego;
- format danych w pliku: pierwszy wiersz to para liczb n b (liczba przedmiotów, pojemność plecaka), kolejne wiersze to pary liczb r w (rozmiar przedmiotu, wartość przedmiotu). Spacja jest separatorem liczb w pojedynczej linii.
- program winien być odporny na wszelkie błędy wprowadzane przez użytkownika przy podawaniu danych wejściowych;
- na potrzeby prezentacji algorytmów program powinien wyświetlać: elementy wybrane do plecaka, ich sumaryczny rozmiar oraz wartość funkcji celu, a dla algorytmu zachłannego dodatkowo informację czy znalezione rozwiązanie jest optymalne.
Dla chętnych: zakoduj algorytm programowania dynamicznego na jak najmniejszej liczbie znaków.

Wygeneruj dane wejściowe dla problemu plecakowego: n-elementowy zbiór przedmiotów, każdemu z nich przyporządkuj rozmiar r(i) oraz wartość w(i). Parametry rozmiar i wartość przyjmują wartości ze zbioru liczb naturalnych. Każdy przedmiot jest unikatowy (ma inny identyfikator), ale w zbiorze może istnieć wiele przedmiotów o takim samym rozmiarze / wartości. Ustal pojemność plecaka b, do którego zapakujesz przedmioty ze zbioru.
Zastosuj zaimplementowane algorytmy do znalezienia optymalnego/ suboptymalnego rozwiązania problemu. Porównaj efektywność tych algorytmów mierząc czas uzyskania rozwiązania przez każdą metodę dla tych samych instancji problemu.

Wykonaj w skali logarytmicznej wykres t=f(n) zależności czasu obliczeń t od liczby n przedmiotów, przy stałej pojemności plecaka b. Na wykresie przedstaw 3 krzywe (jedna krzywa dla każdego algorytmu).
Wykonaj dla każdego algorytmu wykres t=f(b) zależności czasu obliczeń t od pojemności plecaka b, przy stałej liczbie przedmiotów n.
Wykonaj dla każdego algorytmu wykres t=f(n,b) zależności czasu obliczeń t od liczby n przedmiotów i pojemności plecaka b.
Podaj jaka jest złożoność obliczeniowa zaproponowanych algorytmów oraz do jakich klas złożoności obliczeniowej należy 0-1 problem plecakowy (wersja optymalizacyjna i decyzyjna).
Przedstaw obserwacje związane z działaniem wszystkich algorytmów. Podaj dla ilu procent instancji algorytm zachłanny nie znalazł rozwiązania optymalnego. Czy można ustalić w jakich przypadkach ten algorytm nie znajdzie optimum?