Problem plecakowy

Ogólny problem plecakowy

Ogólny problem plecakowy polega, aby spakować tak przedmioty, aby ich wartość była największa. Przed rozpoczęciem pakowania jest dokładnie wiadomo ile jest różnych przedmiotów, ile każdy waży oraz jaką mają wartość. W ogólnym problemie plecakowym liczba rzeczy jest nieograniczona tj. dany przedmiot możemy brać tyle razy ile chcemy. W przypadku, gdy dany przedmiot możemy wziąć tylko raz to mamy do czynienie z decyzyjnym problem plecakowym.

W celu lepszego zrozumienia zadania warto postawić się w miejscu handlarza, który idzie na targ z plecakiem. Sprzedawca wie, że wszystko co zaniesie sprzeda za określoną cenę. Jego celem jest tak zapakować plecak, aby mógł go unieść, a wartość przedmiotów była jak największa.

Metoda zachłanna

Jeśli handlarz będzie chciał zastosować metodę zachłanną to będzie pakował plecak w taki sposób, żeby w danym momencie do plecaka włożyć jak najwięcej najbardziej wartościowych przedmiotów. Jednak takie podejście można doprowadzić, że zostanie zapakowany tylko jeden przedmiot, a można by zapakować więcej lżejszych i mniej wartościowych przedmiotów, a ich łączna wartość byłaby większa. Z tego powodu najlepiej oszacować opłacalność zabrania przedmiotu. Opłacalność najlepiej przyjąć jako iloraz wartości przedmiotu i jego wagi. W ten sposób można nie uzyskać optymalnego rozwiązania, ale gwarantuje większy zysk niż losowe wybieranie przedmiotów.

Przykład

Przypuśćmy teraz, ze mamy dane 4 przedmioty, których waga i wartość są jak w tabelce. Trzeci wiersz zawiera wyliczoną opłacalność, która nie będzie wprowadzona przez użytkownika, a zostanie wyliczona w trakcie wykonywania programu:

Jak widać handlarz powinien zabrać jak najwięcej przedmiotów oznaczonych numerem 1, a najmniej przedmiotów z numerem 4, ponieważ ważą dużo, a są niewiele warte. Przed rozpoczęciem zliczania ile jakich przedmiotów handlarz ma spakować warto posortować listę malejąco względem opłacalności:

Rozpocznijmy teraz pakowanie plecaka. Wiemy, że do plecaka można spakować maksymalnie wagę U. Na potrzeby przykładu załóżmy, że U = 13. Wtedy sprawdzamy dla pierwszego przedmiotu ile sztuk możemy spakować. W tym przypadku można spakować, aż 8 sztuk. Symulując włożenie przedmiotów do plecaka należy pamiętać, aby zmniejszyć U o iloczyn ile sztuk przedmiotu włożono i zwiększając wartość W spakowanych przedmiotów, tj.: U = 13 - 12 = 1, a W = 8 * 3 = 24.

W plecaku nie zmieści się już żaden przedmiot 1, dlatego ten sam zestaw operacji należy wykonać dla kolejnych przedmiotów. Przedmiot mniej opłacalny ma numer 3 i wejdzie dokładnie jedna sztuka, a do plecaka już nie da rady włożyć więcej przedmiotów, ponieważ U wynosi 0, ponieważ jeden przedmiot waży 1. Wartość całkowita plecaka zwiększa się w ten sposób o 1, czyli W = 25. Podsumowując udało się zapakować plecak w pełni i uzyskać wartość W = 25.

Metoda nieoptymalna

Załóżmy, że mamy dwa przedmioty o podanych wartościach:

Opłacalność z każdego z przedmiotów jest identyczna, dlatego w świetle algorytmu zamiana danych jest niepotrzebna. Warto jednak zauważyć, że dla takiego zestawu jeśli U = 9 to zapakujemy tylko 4 przedmioty o numerze 1 i ani jednego przedmiotu numer 2 przez co wartość plecaka wyniesie tylko W = 16. Jednak, gdyby to właśnie przedmiot numer dwa byłby pakowany pierwszy to zmieściłoby się, aż 6 sztuk, a wartość plecaka wyniosłaby 18.

Implementacja

Funkcja główna

Przypuśćmy, że funkcja zapakujZachlannie() otrzymuje następujące argumenty: p_waga - lista zawierająca wagi n elementów, p_wart - lista zawierająca wartość n elementów, n - określa ile jest różnych przedmiotów oraz U - maksymalna waga jaką można spakować. Wtedy algorytm wygląda następująco:

1. double zapakujZachlannie(double* p_waga, double* p_wart, int n, double U) {
2.   sortuj(p_waga, p_wart, n);
3.   double W = 0;
4.   int sztuk = 0;
5.   for(int i = 0; i < n; i++){
6.     sztuk = U / p_waga[i];
7.     U -= sztuk * p_waga[i];
8.     W += sztuk * p_wart[i];
9.   }
10.   return W;
11. }

(1.) Wynikiem funkcji będzie łączna wartość zapakowanych przedmiotów. (2.) Dane na początku należy posortować względem opłacalności. Deklaracja (3.) zmiennej W, która będzie zliczać wartości przedmiotów oraz (4.) sztuk - zmienna, która przechowa w i-tej iteracji ile sztuk można zapakować. (5.) Dla każdego przedmiotu należy: (6.) wyliczyć ile sztuk można zapakować, a następnie symulując pakowanie: (7.) zmniejszyć wartość ile można jeszcze zapakować oraz (8.) zwiększyć wartość plecaka. Na koniec (10.) należy zwrócić W.

Sortowanie danych

Danych nie da rady posortować względem tylko jednej listy - trzeba tu napisać niestandardowe sortowanie, które uwzględni wartości z jednej jak i drugiej listy. Przykładowa implementacja na podstawie sortowania bąbelkowego wygląda następująco:

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

Różnica względem zwykłego sortowanie bąbelkowego polega na tym, że (1.) podane są dwie listy w argumentach i (5.) podczas porównywania jest wyliczana opłacalność każdego elementu. W przypadku, gdy elementy należy zamienić należy pamiętać, że trzeba tego dokonać na obu listach! Oczywiście do sortowanie można utworzyć dodatkową listę z wyliczonymi wartościami i użyć całkowicie innej metody sortowania.

Testowanie funkcji

W celu przetestowania programu można skorzystać z poniższej funkcji, która oczekuje kolejno: n - ile jest różnych przedmiotów, U maksymalny udźwig plecaka. Następne n elementów określa wartości elementów, a kolejne n ich wagę. Jako wynik podana jest łączna wartość przedmiotów plecaków zapakowana zgodnie z algorytmem zachłannym.

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

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz algorytm pakowania zachłannego tak, aby na konsolę zostało wypisane ile jakich przedmiotów zostało umieszczonych w plecaku. W przypadku, gdy dany przedmiot nie został zapakowany program nie powinien nic wypisywać.

Przykładowo dla danych:

1. 4 13
2. 3 2.5 1 1
3. 1.5 5 1 5

otrzymamy:

1. 8 0 1 0

• Kod źródłowy Zadanie 1