Decyzyjny problem plecakowy

Zadanie

Decyzyjny problem plecakowy to przypadek problemu plecakowego, który polega na zmaksymalizowaniu wartości plecaka C bez przekraczania maksymalnej wagi W. W odróżnieniu od ogólnego przypadku każdy wymieniony przedmiot można spakować tylko raz. Jednak jeśli przedmiot występuje na liście n razy to n razy można go spakować. Zadanie to najlepiej odwzorowuje rzeczywistość.

Tak samo jak podczas ogólnego problemu plecakowego należy posortować dane według ilorazu ceny C_i do W_i. Następnie należy zacząć dokładać elementy najbardziej opłacalne. Przedmiot jest dokładany wtedy i tylko wtedy, gdy jest dla niego miejsce w plecaku. Dla każdego przedmiotu po zakończeniu działania algorytmu powinno być określone czy jest zabierany czy nie. Złożoność takiego algorytmu zależy od wybranej metody sortowania o złożoności Θ(k) i wtedy złożoność algorytmu to Θ(n + k), gdzie n to ilość elementów. W najlepszym przypadku decyzyjny problem plecakowy ma złożoność Θ(n·log(n))

Przykład

Przykładowo załóżmy, że maksymalnie można do plecaka włożyć W = 7kg. do spakowania są przedmioty w tabelce. Dla każdego z wymienionych przedmiotów wyliczmy iloraz C_i do W_i.

Kolejny krok polega na posortowaniu listy według opłacalności:

W ostatnim etapie należy określić, które przedmioty zostaną zabrane. Przedmioty są wybierane od tych najbardziej opłacalnych. Jeśli przedmiot można spakować to jest on dokładany do plecaka.

Ostatnie dwa elementy nie muszą być już sprawdzane, ponieważ i tak nie zmieszczą się do plecaka. Ta drobna optymalizacja pozwoli zakończyć działanie algorytmu wcześniej. Wynikiem działania algorytmu jest zwrócenie, że do plecaka należy spakować przedmioty o numerach 1, 3, 5 i 6. Wartość plecaka C wyniesie 10 + 3 + 6 + 1 = 20.

Implementacja

Funkcja pomocnicza

Sortowanie danych zostało oparte na sortowaniu bąbelkowym. W tego typu sortowania należy pamiętać, że dane trzeba zmieniać w obydwu tablicach równocześnie, ponieważ są to nierozłączne pary wartości.

1. void sortuj(double* p_waga, double* p_cena, int n) {
2.   for (int i = 0; i < n - 1; i++) {
3.     for (int j = 0; j < n - i - 1; j++) {
4.       if (p_cena[j] / p_waga[j] <= p_cena[j + 1] / p_waga[j + 1]) {
5.         swap(p_waga[j], p_waga[j + 1]);
6.         swap(p_cena[j], p_cena[j + 1]);
7.       }
8.     }
9.   }
10. }

Pakowanie decyzyjne

Pakowanie decyzyjne realizuje funkcja zapakujDecyzyjnie(), która przyjmuje cztery argumenty: p_waga - tablica wag przedmiotów, p_cena - tablica cen przedmiotów, n - ilość przedmiotów oraz U - maksymalny udźwig.

1. double zapakujDecyzyjnie(double* p_waga, double* p_cena, int n, double U) {
2.   sortuj(p_waga, p_cena, n);
3.   double W = 0;
4.   for (int i = 0; i < n; i++) {
5.     if (U - p_waga[i] >= 0) {
6.       U -= p_waga[i];
7.       W += p_cena[i];
8.       if (U == 0) {
9.         return W;
10.       }
11.     }
12.   }
13.   return W;
14. }

(2.) Po wczytaniu dane są sortowane. Następnie (3.) inicjalizowana jest zmienna do zliczania wartości plecaka. (4.) Dla każdego przedmiotu: (5.) sprawdź czy zmieści się do plecaka. Jeśli tak to (6.) dołóż go zmniejszając aktualny maksymalny udźwig U i (7.) zwiększ wartość plecaka. (8.) Sprawdź czy wartość plecaka nie osiągnęła 0. Jeśli tak to (9.) zakończ wcześniej działanie programu. (13.) Jeśli pętla nie zakończyła działania wcześniej to należy zwrócić W. Przypadek ten może wystąpić, gdy wciąż pozostało wolne miejsce, ale żaden przedmiot nie pasuje (pod względem wagowym).

Testowanie funkcji

Poniższa funkcja main() poprosi użytkownika o wprowadzenie ile będzie elementów oraz maksymalny udźwig. Następnie wczyta n linijek par danych cena × waga.

1. int main() {
2.   int n;
3.   double U;
4.   cin >> n >> U;
5.   double* p_cena = new double[n];
6.   double* p_waga = new double[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> p_cena[i] >> p_waga[i];
9.   cout << zapakujDecyzyjnie(p_waga, p_cena, n, U);
10.   cout << endl;
11.   delete p_waga, p_cena;
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program dla handlowca, który trafił na bardzo dobre oferty. Chciałby, aby zakupione obiekty nie przekroczyły wagi U, ale ich wartość była jak największa. Pomóż handlowcowi wybrać ile jakich przedmiotów powinien zakupić. Na początku zostaną dane n - ilość ofert oraz U - maksymalny udźwig. Następnie zostanie podane n linijek danych postaci nazwa × cena × waga × ilość. Po zakończeniu działania algorytmu wypisz przedmioty do kupienia oraz w jakiej ilości.

Przykładowo zostaną podane następujące dane.

1. 6 100
2. Cukierki 10 10 5
3. Ksiazki 6 20 8
4. Zegarki 2 12 3
5. Plyty 3 12 7
6. Lizaki 3 10 2
7. Sznurowki 1 5 1

Program powinien wypisać na ekran:

1. Cukierki 5
2. Ksiazki 2
3. Lizaki 1

• Kod źródłowy Zadanie 1