Zagadnienia
- Metodyka programowania dynamicznego
- Metoda przeglądu wyczerpującego
- Złożoność obliczeniowa w/w metod
- Zakres stosowalności programowania dynamicznego
- Sformułowanie problemu plecakowego oraz metoda jego rozwiązania
Termin oddawania programów i wyników eksperymentów (+ wykresy): 06.06.2017
Termin dostarczenia sprawozdania (mailem pdf): 13.06.2017
Projekt
Zaimplementuj dwa algorytmy rozwiązujące dyskretny problem plecakowy.
- Metodą przeglądu wyczerpującego
- Metodą programowania dynamicznego
Porównaj na wykresach jak zmienia się czas działania programu wraz ze wzrostem
- liczby elementów (n),
- pojemności plecaka (W).
Czy rozkład danych wejściowych (wagi i wartości przedmiotów) mają wpływ na złożoność obliczeniową? Odpowiedź uzasadnij.