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): 31.05.2016
Termin dostarczenia sprawozdania (mailem pdf): 07.06.2016
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.