Spis Treści
Wymagania i kryteria oceniania
Należy zaimplementować algorytm rozwiązujący dyskretny problem plecakowy, używający programowania dynamicznego.
Dla podanych wag i wartości przedmiotów, oraz ładowności plecaka, należy dokonać wyboru przedmiotów, których:
- sumaryczna waga nie przekracza ładowności plecaka,
- zaś sumaryczna wartość jest możliwie największa.
Gdy możliwych jest kilka optymalnych wyborów, program może wskazać dowolny z nich.
Należy zaimplementować algorytm dynamiczny rozwiązujący jeden z niżej wymienionych wariantów problemu oraz opanować (ze zrozumieniem) dotyczącą go teorię. Ocena zależy od wybranego wariantu i może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.
Warianty
Nieograniczona liczba przedmiotów każdego rodzaju, wartość równa wadze (na ocenę 3)
Przedmiotami są sztabki złota, których wartość jest równa ich wadze (dla każdej sztabki podana jest więc jedna liczba oznaczająca zarówno wagę, jak i wartość). Aby zmaksymalizować wartość zapakowanych przedmiotów, wystarczy więc w jak największym stopniu wypełnić plecak. Równocześnie przyjmuje się, że dostępna jest nieskończona liczba sztabek o każdej z podanych wag.
Przykłady:
- Dla plecaka o pojemności 10 i czterech sztabek o wagach 9, 5, 4, 3, należy wybrać dwie sztabki o wadze 5 (ich łączna waga, oraz wartość, to 10).
- Dla plecaka o pojemności 10 i trzech sztabek o wagach 8, 6, 3, należy wybrać sztabki o wagach 6 i 3, albo trzy sztabki o wadze 3 każda. W obu przypadkach łączna waga (i wartość) to 9. Wystarczy by program znalazł jedną, którąkolwiek z tych odpowiedzi.
Nieograniczona liczba przedmiotów każdego rodzaju, podane wartości (na ocenę 3.5)
Dla każdego przedmiotu podane są dwie liczby, oznaczające jego wagę i wartość. Celem jest wybór przedmiotów o jak największej łącznej wartości, przy łącznej wadze nieprzekraczającej ładowności plecaka. Przyjmuje się, że dostępna jest nieskończona liczba przedmiotów każdego rodzaju.
Przykładowo dla plecaka o ładowności 11 i przedmiotów:
| Waga | Wartość |
|---|---|
| 9 | 12 |
| 5 | 8 |
| 3 | 5 |
Należy zapakować 2 sztuki przedmiotu o wadze 3 i wartości 5, oraz jedną sztukę o wadze 5 i wartości 8. Łączna wartość zapakowanych przedmiotów to 18, zaś waga to 11.
Jeden przedmiot każdego rodzaju, podane wartości (na ocenę 4)
Dla każdego przedmiotu podane są dwie liczby, oznaczające jego wagę i wartość. Celem jest wybór przedmiotów o jak największej łącznej wartości, przy łącznej wadze nieprzekraczającej ładowności plecaka. Przyjmuje się, że dostępna jest jedynie jedna sztuka każdego przedmiotu.
Przykładowo dla plecaka o ładowności 11 i przedmiotów:
| Waga | Wartość |
|---|---|
| 9 | 12 |
| 5 | 8 |
| 3 | 5 |
Należy zapakować przedmiot o wadze 3 i wartości 5, oraz ten o wartości 5 i wadze 8. Łączna wartość zapakowanych przedmiotów wynosi 13, zaś waga 8.
Rozszerzenia, na wyższe oceny
Magiczne kule (+1 do oceny)
Dodatkowo podana jest liczba M magicznych kul oraz waga w, taka sama dla każdej kuli. Zapakowanie jednej kuli do plecaka podwaja wartość umieszczonych w nim przedmiotów. Zapakowanie k kul (gdzie 0 ≤ k ≤ M) powoduje, że całkowita wartość wszystkich zapakowanych przedmiotów zostaje pomnożona przez 2ᵏ. Liczba użytych kul nie może przekroczyć M.
Kule nie mają własnej wartości — zwiększają jedynie wartość całego plecaka poprzez wspomniany mnożnik. Celem pozostaje maksymalizacja końcowej wartości przy zachowaniu ograniczenia wagowego.
Przykładowe pytania sprawdzające z algorytmów
- Zilustrować działanie algorytmu dla zadanych ciągów wejściowych.
- Jaka jest złożoność czasowa oraz pamięciowa algorytmu? Odpowiedź uzasadnij.
- Z jakiego spostrzeżenia korzysta algorytm? Z jakiej zależności rekurencyjnej?
- Na czym polega idea programowania dynamicznego?