Przeczytaj

Implementacja rozwiązania ogólnego problemu plecakowegoproblem plecakowyproblemu plecakowego wykorzystującego programowanie dynamiczne – język Java

Specyfikacja problemu:

Dane:

nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów
wartosci – tablica liczb naturalnych; wartości poszczególnych przedmiotów
wagi – tablica liczb naturalnych; wagi poszczególnych przedmiotów
poj – liczba naturalna; maksymalna pojemność plecaka

Wynik:

liczby sztuk poszczególnych przedmiotów (również równe 0), których całkowita waga nie przekracza wartości przechowywanej w zmiennej poj, a których całkowita wartość jest największa wśród możliwych wypełnień plecaka rzeczami o takiej wadze, która nie przekracza wartości zmiennej poj
całkowita wartość spakowanego plecaka

Zaczynamy od zapisania nagłówka metody ogolnyProblemPlecakowyDynamiczne. Przyjmuje pięć argumentów:

wagi – tablica liczb naturalnych; tablica wag przedmiotów;
wartosci – tablica liczb naturalnych; tablica wartości przedmiotów;
nazwy – tablica łańcuchów znaków; nazwy przedmiotów;
n – liczba naturalna; liczba dostępnych przedmiotów;
poj – liczba naturalna; pojemność plecaka.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
}

Tworzymy dwie tablice – P oraz Q. Długość obu tablic wynosi poj + 1, wypełniamy je zerami.

Tablica P przechowuje maksymalne wartości, jakie można osiągnąć dla różnych pojemności plecaka, a tablica Q przechowuje informacje o indeksach przedmiotów, które zostały spakowane dla danej pojemności.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
}

Zapisujemy dwie pętle for. Pierwsza z nich iteruje przez wszystkie przedmioty, druga (zagnieżdżona) iteruje przed wszystkie możliwe pojemności plecaka.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
        }
    }        
}

Sprawdzamy, czy aktualnie rozważany przedmiot może być spakowany do plecaka o danej pojemności j, czyli czy jego waga jest mniejsza lub równa wartości i-tego elementu tablicy wagi.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
            if (wagi[i] <= j) {
            }                
        }
    }        
}

Dla każdego przedmiotu sprawdzamy, czy jego waga jest mniejsza lub równa aktualnej pojemności plecaka. Jeśli tak, to porównujemy maksymalną wartość dla aktualnej pojemności plecaka z wartością uzyskaną przez dodanie aktualnego przedmiotu. Jeśli wartość uzyskana przez dodanie przedmiotu jest większa, aktualizujemy wartość w tablicy P na pozycji j oraz indeks w tablicy Q.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
            if (wagi[i] <= j) {
                if (P[j] < P[j - wagi[i]] + wartosci[i]) {
                    P[j] = P[j - wagi[i]] + wartosci[i];
                    Q[j] = i + 1;
                }                    
            }                
        }
    }        
}

Po obliczeniu wartości dla wszystkich możliwych kombinacji przedmiotów i pojemności plecaka iterujemy przez tablicę Q, aby określić, które przedmioty zostały spakowane i w jakiej liczbie.

Tworzymy listę spakowane_przedmioty, która będzie przechowywać liczbę spakowanych sztuk każdego przedmiotu. Inicjalizujemy ją wartościami zero, ponieważ na początku jeszcze nie spakowaliśmy żadnego przedmiotu.

Inicjalizujemy zmienną pojemnosc wartością poj, czyli maksymalną pojemnością plecaka. Ta zmienna będzie nam służyć do śledzenia, ile miejsca w plecaku pozostało do zapakowania.

Uruchamiamy pętlę while, która będzie wykonywać się, dopóki wartość zmiennej pojemnosc jest większa od 0, czyli w plecaku jest jeszcze miejsce.

Linia 1. public static void ogolnyProblemPlecakowyDynamiczne otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int n przecinek int poj zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy P znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy Q znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości poj średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły P otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. P otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1 średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowanePrzedmioty znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 17. int pojemnosc znak równości poj średnik. Linia 18. while otwórz nawias okrągły pojemnosc zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 20. zamknij nawias klamrowy.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
            if (wagi[i] <= j) {
                if (P[j] < P[j - wagi[i]] + wartosci[i]) {
                    P[j] = P[j - wagi[i]] + wartosci[i];
                    Q[j] = i + 1;
                }                    
            }                
        }
    }    
    
    int[] spakowanePrzedmioty = new int[n];
	int pojemnosc = poj;
    while (pojemnosc > 0) {
    }        
}

Sprawdzamy, czy dla aktualnej pojemności pojemnosc istnieje jakiś indeks przedmiotu w tablicy Q (czyli czy został spakowany jakiś przedmiot). Jeśli tak, przechodzimy do kolejnego kroku.

Linia 1. public static void ogolnyProblemPlecakowyDynamiczne otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int n przecinek int poj zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy P znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy Q znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości poj średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły P otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. P otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1 średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowanePrzedmioty znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 17. int pojemnosc znak równości poj średnik. Linia 18. while otwórz nawias okrągły pojemnosc zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. zamknij nawias klamrowy. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
            if (wagi[i] <= j) {
                if (P[j] < P[j - wagi[i]] + wartosci[i]) {
                    P[j] = P[j - wagi[i]] + wartosci[i];
                    Q[j] = i + 1;
                }                    
            }                
        }
    }    
    
    int[] spakowanePrzedmioty = new int[n];
	int pojemnosc = poj;
    while (pojemnosc > 0) {
        if (Q[pojemnosc] != 0) {
        }            
    }        
}

Zwiększamy licznik spakowanych sztuk dla przedmiotu o indeksie Q[pojemnosc] - 1. Indeks ten wskazuje na przedmiot, który został spakowany dla aktualnej pojemności pojemnosc.

Linia 1. public static void ogolnyProblemPlecakowyDynamiczne otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int n przecinek int poj zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy P znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy Q znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości poj średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły P otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. P otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1 średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowanePrzedmioty znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 17. int pojemnosc znak równości poj średnik. Linia 18. while otwórz nawias okrągły pojemnosc zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. spakowanePrzedmioty otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy plus znak równości 1 średnik. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
            if (wagi[i] <= j) {
                if (P[j] < P[j - wagi[i]] + wartosci[i]) {
                    P[j] = P[j - wagi[i]] + wartosci[i];
                    Q[j] = i + 1;
                }                    
            }                
        }
    }    
    
    int[] spakowanePrzedmioty = new int[n];
	int pojemnosc = poj;
    while (pojemnosc > 0) {
        if (Q[pojemnosc] != 0) {
            spakowanePrzedmioty[Q[pojemnosc] - 1] += 1;
        }            
    }        
}

Zmniejszamy wartość pojemnosc o wagę przedmiotu, który został spakowany dla aktualnej pojemności pojemnosc. Dzięki temu symulujemy usunięcie spakowanego przedmiotu z plecaka, aby sprawdzić, ile miejsca pozostało do zapakowania kolejnych przedmiotów.

Linia 1. public static void ogolnyProblemPlecakowyDynamiczne otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int n przecinek int poj zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. int otwórz nawias kwadratowy zamknij nawias kwadratowy P znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy Q znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 5. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości poj średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły P otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. P otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1 średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowanePrzedmioty znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 17. int pojemnosc znak równości poj średnik. Linia 18. while otwórz nawias okrągły pojemnosc zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. spakowanePrzedmioty otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy plus znak równości 1 średnik. Linia 21. zamknij nawias klamrowy. Linia 22. pojemnosc minus znak równości wagi otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy.

public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
	int[] P = new int[poj + 1];
    int[] Q = new int[poj + 1];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= poj; j++) {
            if (wagi[i] <= j) {
                if (P[j] < P[j - wagi[i]] + wartosci[i]) {
                    P[j] = P[j - wagi[i]] + wartosci[i];
                    Q[j] = i + 1;
                }                    
            }                
        }
    }    
    
    int[] spakowanePrzedmioty = new int[n];
	int pojemnosc = poj;
    while (pojemnosc > 0) {
        if (Q[pojemnosc] != 0) {
            spakowanePrzedmioty[Q[pojemnosc] - 1] += 1;
        }   
        pojemnosc -= wagi[Q[pojemnosc] - 1];
    }        
}

Na końcu wypisujemy informacje o spakowanych przedmiotach oraz łączną wartość spakowanych przedmiotów.

Dodajemy wywołanie metody.

Kompletny kod:

Linia 1. public class PlecakowyProblem otwórz nawias klamrowy. Linia 2. public static void ogolnyProblemPlecakowyDynamiczne otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci przecinek String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy przecinek int n przecinek int poj zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. int otwórz nawias kwadratowy zamknij nawias kwadratowy P znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 4. int otwórz nawias kwadratowy zamknij nawias kwadratowy Q znak równości new int otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy średnik. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. for otwórz nawias okrągły int j znak równości 1 średnik j otwórz nawias ostrokątny znak równości poj średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. if otwórz nawias okrągły P otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. P otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości P otwórz nawias kwadratowy j minus wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias kwadratowy plus wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 11. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1 średnik. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. int otwórz nawias kwadratowy zamknij nawias kwadratowy spakowanePrzedmioty znak równości new int otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 18. int pojemnosc znak równości poj średnik. Linia 19. while otwórz nawias okrągły pojemnosc zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. if otwórz nawias okrągły Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy wykrzyknik znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. spakowanePrzedmioty otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy plus znak równości 1 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. pojemnosc minus znak równości wagi otwórz nawias kwadratowy Q otwórz nawias kwadratowy pojemnosc zamknij nawias kwadratowy minus 1 zamknij nawias kwadratowy średnik. Linia 24. zamknij nawias klamrowy. Linia 26. System kropka out kropka println otwórz nawias okrągły cudzysłów Liczba spakowanych sztuk przedmiotów dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. System kropka out kropka println otwórz nawias okrągły nazwy otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów otwórz nawias okrągły indeks cudzysłów plus i plus cudzysłów zamknij nawias okrągły dwukropek cudzysłów plus spakowanePrzedmioty otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy. Linia 31. System kropka out kropka println otwórz nawias okrągły cudzysłów Wartość spakowanych przedmiotów dwukropek cudzysłów plus P otwórz nawias kwadratowy poj zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 32. zamknij nawias klamrowy. Linia 34. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. int otwórz nawias kwadratowy zamknij nawias kwadratowy wagi znak równości otwórz nawias klamrowy 1 przecinek 2 przecinek 2 zamknij nawias klamrowy średnik. Linia 36. int otwórz nawias kwadratowy zamknij nawias kwadratowy wartosci znak równości otwórz nawias klamrowy 1 przecinek 4 przecinek 5 zamknij nawias klamrowy średnik. Linia 37. String otwórz nawias kwadratowy zamknij nawias kwadratowy nazwy znak równości otwórz nawias klamrowy cudzysłów aparat cudzysłów przecinek cudzysłów bukłak cudzysłów przecinek cudzysłów chlebak cudzysłów zamknij nawias klamrowy średnik. Linia 38. int n znak równości wagi kropka length średnik. Linia 39. int poj znak równości 5 średnik. Linia 41. ogolnyProblemPlecakowyDynamiczne otwórz nawias okrągły wagi przecinek wartosci przecinek nazwy przecinek n przecinek poj zamknij nawias okrągły średnik. Linia 42. zamknij nawias klamrowy. Linia 43. zamknij nawias klamrowy.

public class PlecakowyProblem {
    public static void ogolnyProblemPlecakowyDynamiczne(int[] wagi, int[] wartosci, String[] nazwy, int n, int poj) {
        int[] P = new int[poj + 1];
        int[] Q = new int[poj + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= poj; j++) {
                if (wagi[i] <= j) {
                    if (P[j] < P[j - wagi[i]] + wartosci[i]) {
                        P[j] = P[j - wagi[i]] + wartosci[i];
                        Q[j] = i + 1;
                    }
                }
            }
        }

        int[] spakowanePrzedmioty = new int[n];
        int pojemnosc = poj;
        while (pojemnosc > 0) {
            if (Q[pojemnosc] != 0) {
                spakowanePrzedmioty[Q[pojemnosc] - 1] += 1;
            }
            pojemnosc -= wagi[Q[pojemnosc] - 1];
        }

        System.out.println("Liczba spakowanych sztuk przedmiotów:");
        for (int i = 0; i < n; i++) {
            System.out.println(nazwy[i] + " (indeks " + i + "): " + spakowanePrzedmioty[i]);
        }

        System.out.println("Wartość spakowanych przedmiotów: " + P[poj]);
    }

    public static void main(String[] args) {
        int[] wagi = {1, 2, 2};
        int[] wartosci = {1, 4, 5};
        String[] nazwy = {"aparat", "bukłak", "chlebak"};
        int n = wagi.length;
        int poj = 5;

        ogolnyProblemPlecakowyDynamiczne(wagi, wartosci, nazwy, n, poj);
    }
}

Wynik działania programu:

Liczba spakowanych sztuk przedmiotu aparat (indeks 0): 1
Liczba spakowanych sztuk przedmiotu bukłak (indeks 1): 0
Liczba spakowanych sztuk przedmiotu chlebak (indeks 2): 2
Wartość spakowanych przedmiotów: 11

Polecenie 1

Wróć do e‑materiału Problem plecakowy w języku Java. Porównaj wyniki działania obu zaprezentowanych programów.

Słownik

memoryzacja

zapamiętywanie wyników mniejszych podproblemów, aby później móc z nich skorzystać przy dalszych etapach rozwiązywania większych podproblemów

nakładające się podproblemy

problem główny składa się z nakładających się podproblemów, jeżeli można go rozbić na podproblemy, które mogą być używane wielokrotnie i które są ze sobą powiązane

problem optymalizacyjny

problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej lub najmniejszej wartości pewnego parametru tego problemu, spełniającej określoną własność

problem plecakowy

problem plecakowy, który jest tematem tej serii e‑materiałów, polega na takim wyborze przedmiotów z danego zbioru, by po spakowaniu wybrane przedmioty miały jak największą wartość, ale ich waga nie przekraczała pojemności plecaka; istnieją różne metody jego rozwiązania, w tej serii prezentujemy jedną z nich – podejście zachłanne

własność optymalnej podstruktury

problem posiada własność optymalnej podstruktury, jeśli optymalne rozwiązanie głównego problemu można znaleźć na podstawie optymalnychproblem optymalizacyjnyoptymalnych rozwiązań jej podproblemów

Wprowadzenie

Prezentacja multimedialna

Implementacja rozwiązania ogólnego problemu plecakowegoproblem plecakowyproblemu plecakowego wykorzystującego programowanie dynamiczne – język Java

Słownik