Strona główna » Algorytmy » Artykuły » Ogólny problem plecakowy
 

Ogólny problem plecakowy

· Ogólny · Zasada Bellmana · Decyzyjny ·

Wstęp

Rozwiązując ogólny problem plecakowy przy pomocy metody zachłannej nie zawsze gwarantuje, że uzyskamy optymalne rozwiązanie. Istnieje jednak możliwość skorzystania z zasady Bellmana, która pomaga wyznaczyć zawsze optymalne rozwiązanie. Polega ona na rozwiązaniu prostszych podzadań, a następnie uzyskanie wyniku. Zaletą takiego rozwiązania jest fakt, że nie trzeba sortować wprowadzonych danych. To znacznie przyśpiesza wyszukanie rozwiązania.

Zakładając, że na wejściu dane jest n różnych przedmiotów - ponumerowanych od 1 do n, a maksymalna waga plecaka wynosi U to należy narysować dwie tabelki o szerokości U i wysokości n. W pierwszej tabelce w i-tym wierszu znajdują się wartości plecaka dla każdego udźwigu mniejszego lub równego maksymalnemu U. Ponadto w i-tym wierszu można spakować przedmioty, których numer jest nie większy niż i. Innymi słowy w pierwszym wierszu zapisywane są maksymalne wartości dla każdego udźwigu w zakresie [1, U] wykorzystując tylko przedmiot o numerze 1. W drugim wierszu można użyć przedmiotów numer 1 i 2.W każdym kolejnym wierszu należy sprawdzić czy dla aktualnie rozpatrywanego udźwigu nie można uzyskać większej wartości: jeśli można to należy w j-tej kolumnie zapisać nowy wynik niż wartość z poprzedniego wiersza w tej samej kolumnie. Jednak jeśli wartość udźwigu nie wzrośnie to należy przepisać wartość z poprzedniego wiersza w tej samej kolumnie. W ten sposób jest zagwarantowane, że każdym nowym przedmiotem można uzyskać optymalne rozwiązanie.

Druga tabelka przechowuje na pozycjach (i, j) jaki element został wtedy włożony do plecaka. Jeśli wartość plecaka została przepisana z poprzedniego wiersza to numer ostatniego wsadzonego elementu też musi być identyczny. Jeśli jednak wartość w pierwszej tabelce została poprawiona to należy ustalić numer na numer aktualnie rozpatrywanego wiersza.

Na sam koniec w tabelce należy znaleźć maksymalną wartość. Jest to poszukiwany wynik. Maksymalnych wartości może być więcej. Oznacza to, że optymalny wynik można osiągnąć na wiele różnych sposobów.

Przykład

Rozpatrzmy ponownie przykład z poprzedniej części z algorytmem zachłannym. Maksymalny udźwig U = 13, a dostępne przedmioty to:

Przedmiot1234
Wartość6511
Waga4315

Teraz można stworzyć na tej podstawie tabelkę o wymiarach 13 x 4:

Waga123456789101112
100066661212121218
20056610111215161720
31256710111215161720
41256710111215161720

Pierwszy wiersz obrazuje ile razy dany przedmiot można wsadzić dla określonej wagi. Jak widać ostatecznie używając całego plecaka i tylko przedmiotu numer 1 można uzyskać wartość 18. W drugim wierszu można już użyć zarówno drugiego jak i pierwszego przedmiotu. Wiersze zaczynają się różnić dla U' = 3, ponieważ wtedy można już włożyć przedmiot numer 2, ale numeru 1 jeszcze nie. Jednak w następnej komórce wartość jest taka sama jak w poprzednim wierszu, ponieważ wykorzystując tylko przedmiot 2 nie można uzyskać lepszego wyniku niż używając pierwszego. W podany sposób wypełniana jest cała tabelka.

W celu wykorzystania dotychczas znalezionych wartości optymalnych w trakcie wypełniania wiersza algorytm sprawdza wartość optymalną dla mniejszej wagi i na tej podstawie określa czy można dodać nowy element, albo zastąpić wszystkie wsadzone w poprzednim wierszu.

W tabelce jak widać największa wartość to 20. Wartość ta występuje w trzech wierszach. Należy jednak zauważyć, że dwa wiersze są identyczne, więc maksymalną wartość można uzyskać na dwa różne sposoby. Jest to spowodowane faktem, że przedmiot numer 4 jest za ciężki i za mało warty i nie ma go gdzie upchać w plecaku. W celu odczytania jak dane wartości zostały uzyskane należy skorzystać z drugiej tabelki do której były wstawiane wartości jaki element został ostatnio włożony:

Waga123456789101112
1000111111111
2002112212222
3332132212222
4332132212222

Sprawdzając jakie elementy zostały wsadzone dla rozwiązania w wierszu 4 należy pobrać kolejno elementy:

Waga pozostałaPozycjaNumer
12(12, 4)2
9(9, 4)2
6(6, 4)2
3(3, 4)2
0--

Z odczytanych wartości wynika, że plecak został zapełniony czterema elementami o numerze 2.

Implementacja

Podczas działania programu będzie istniała potrzeba stworzenia i usunięcia tablic dwuwymiarowych, dlatego przydatne okażą się funkcja utworzTabele(), która stworzy tabelę o zadanych wymiarach i wyzeruje elementy.

  1. int** utworzTabele(int w, int h){
  2.   int** tab = new int*[h];
  3.   for(int i = 0; i < h; i++){
  4.     tab[i] = new int[w];
  5.     for(int j = 0; j < w; j++){
  6.       tab[i][j] = 0;
  7.     }
  8.   }
  9.   return tab;
  10. }

Kolejna funkcja pomocnicza to usunTabele(), która usunie stworzoną wcześniej tabele.

  1. void usunTabele(int** tab, int h){
  2.   for(int i = 0; i < h; i++){
  3.     delete[] tab[i];
  4.   }
  5.   delete[] tab;
  6. }

(1.) Główna funkcja pakująca plecak przyjmuje cztery argumenty: p_waga - listę wag przedmiotów, p_wartosc - listę wartość przedmiotów, n - ile jest danych różnych przedmiotów oraz U - maksymalne obciążenie plecaka.

  1. int zapakujOptymalnie(int* p_waga, int* p_wartosc, int n, int U) {
  2.   int** wartosc = utworzTabele(U+1, n);
  3.   int** numery = utworzTabele(U+1, n);
  4.   for(int i = 1; i < n; i++){
  5.     for(int j = 1; j <= U; j++){
  6.       if(j >= p_waga[i] && wartosc[i - 1][j] < wartosc[i][j - p_waga[i]] + p_wartosc[i]){
  7.         wartosc[i][j] = wartosc[i][j - p_waga[i]] + p_wartosc[i];
  8.         numery[i][j] = (i+1);
  9.       } else {
  10.         wartosc[i][j] = wartosc[i - 1][j];
  11.         numery[i][j] = numery[i - 1][j];
  12.       }
  13.     }
  14.   }
  15.   int w = wartosc[n-1][U];
  16.   usunTabele(wartosc, n);
  17.   usunTabele(numery, n);
  18.   return w;
  19. }

(2. - 3.) Zadeklarowanie tablic pomocniczych. (4.) Dla każdego wiersza i (5.) każdej kolumny: (6.) należy wyliczyć nową wartość w danej komórce, która jest aktualnie najbardziej optymalna. Jeśli okaże się, że jest bardziej optymalna niż poprzednia to w tabelach jest dopisana (7.) nowa wartość i (8.) jaki przedmiot został wsadzony. Jednak jeśli okaże się, że nowa wartość jest mniejsza niż wyliczona dla takiego samego udźwigu w poprzednim wierszu to (10. - 11.) należy przepisać wartości z wiersza poprzedniego. Na sam koniec (15.) pobierana jest największa wartość, (16., 17.) usuwane tablice pomocnicze i (18.) zwracany wynik.

Oszczędna implementacja

Złożoność czasowa jak i pamięciowa rozwiązania wynosi Θ(nm), gdzie n to ilość elementów, a m to maksymalny udźwig plecaka. Istnieje możliwość poprawy złożoności pamięciowej. Należy zauważyć, że algorytm w trakcie wyznaczania każdego kolejnego wiersza korzysta tylko poprzedniego wiersza, dlatego będzie potrzebne tylko 2m pamięci co ostatecznie sprowadzi się do złożoności Θ(m).

  1. int zapakujOptymalnie(int* p_waga, int* p_wartosc, int n, int U) {
  2.   int* wartosci_stare = new int[U + 1];
  3.   int* wartosci_nowe = new int[U + 1];
  4.   int* numery_stare = new int[U + 1];
  5.   int* numery_nowe = new int[U + 1];
  6.   int* wsk;
  7.   for(int i = 0; i <= U; i++){
  8.     wartosci_stare[i] = 0;
  9.     numery_stare[i] = 0;
  10.   }
  11.   for(int i = 0; i < n; i++){
  12.     for(int j = 1; j <= U; j++){
  13.       if(j >= p_waga[i] && wartosci_stare[j] < wartosci_nowe[j - p_waga[i]] + p_wartosc[i]){
  14.         wartosci_nowe[j] = wartosci_nowe[j - p_waga[i]] + p_wartosc[i];
  15.         numery_nowe[j] = (i+1);
  16.       } else {
  17.         wartosci_nowe[j] = wartosci_stare[j];
  18.         numery_nowe[j] = numery_stare[j];
  19.       }
  20.     }
  21.     wsk = wartosci_stare;
  22.     wartosci_stare = wartosci_nowe;
  23.     wartosci_nowe = wsk;
  24.     wsk = numery_stare;
  25.     numery_stare = numery_nowe;
  26.     numery_nowe = wsk;
  27.   }
  28.   int w = wartosci_nowe[U];
  29.   delete[] wartosci_stare, wartosci_nowe, numery_stare, numery_nowe;
  30.   return w;
  31. }

(2. - 5.) Utworzenie list pomocniczych oraz (6.) zadeklarowanie wskaźnika. (7. - 10.) Wyzerowanie poprzedniego wiersza co można przeczytać, że wiersz 0 przez to, że nie ma żadnych elementów to nigdzie nie może mieć wartości różnej od 0. (11. - 27.) to przepisanie poprzedniej implementacji - zmienia się tylko sposób odwołania do określonej wartości. Jednak w (21. - 26.) zamienia stary wiersz z nowym. Bez tego program niepoprawnie by odczytywał dane z poprzedniego wiersza. Na koniec (28.) należy odczytać wynik, (29.) usunąć listy pomocnicze i (30.) zwrócić wynik.

Testowanie funkcji

Po uruchomieniu programu należy w pierwszym wierszu wpisać dwie liczby całkowite: n - liczbę różnych elementów oraz U - maksymalną wagę plecaka. Drugi wiersz powinien zawierać n wartości kolejnych przedmiotów, a w trzecim n wag kolejnych przedmiotów. Program na ekran wypisze maksymalną wartość plecaka.

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

Zadania

Zadanie 1

Napisz program, który prócz zwracania wyniku wypisze na ekran jakie elementy należy wsadzić do plecaka, aby uzyskać optymalny wynik.

Przykładowo dla danych:

  1. 4 12
  2. 6 5 1 1
  3. 4 3 1 5

Program powinien zwrócić:

  1. 2 2 2 2
  2. 20