Przeczytaj

Implementacja rozwiązania ogólnego problemu plecakowego wykorzystującego programowanie dynamiczne – język C++

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 dodania niezbędnych bibliotek oraz przestrzeni nazw.

Następnie zapiszemy nagłówek funkcji ogolny_problem_plecakowy_dynamiczne. 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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};
}

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

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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 spakowane_przedmioty[n] = {0};
    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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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 spakowane_przedmioty[n] = {0};
    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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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 spakowane_przedmioty[n] = {0};
    int pojemnosc = poj;
    while (pojemnosc > 0) {
        if (Q[pojemnosc] != 0) {
            spakowane_przedmioty[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.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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 spakowane_przedmioty[n] = {0};
    int pojemnosc = poj;
    while (pojemnosc > 0) {
        if (Q[pojemnosc] != 0) {
            spakowane_przedmioty[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 funkcji.

Kompletny kod:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. void ogolny podkreślnik problem podkreślnik plecakowy podkreślnik dynamiczne otwórz nawias okrągły int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek string nazwy otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n przecinek int poj zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int P otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 zamknij nawias klamrowy średnik. Linia 8. int Q otwórz nawias kwadratowy poj plus 1 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 zamknij nawias klamrowy średnik. Linia 10. 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 11. 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 12. 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 13. 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 14. 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 15. Q otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości i plus 1 średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. int spakowane podkreślnik przedmioty otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 0 zamknij nawias klamrowy średnik. Linia 22. int pojemnosc znak równości poj średnik. Linia 23. while otwórz nawias okrągły pojemnosc zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. 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 25. spakowane podkreślnik przedmioty 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 26. zamknij nawias klamrowy. Linia 27. 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 28. zamknij nawias klamrowy. Linia 30. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liczba spakowanych sztuk przedmiotów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 31. 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 32. cout otwórz nawias ostrokątny otwórz nawias ostrokątny nazwy otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów otwórz nawias okrągły indeks cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny i otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias okrągły dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny spakowane podkreślnik przedmioty otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 33. zamknij nawias klamrowy. Linia 35. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wartość spakowanych przedmiotów dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny P otwórz nawias kwadratowy poj zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 36. zamknij nawias klamrowy. Linia 38. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 2 przecinek 2 zamknij nawias klamrowy średnik. Linia 40. int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 4 przecinek 5 zamknij nawias klamrowy średnik. Linia 41. string nazwy otwórz nawias kwadratowy zamknij nawias kwadratowy 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 42. int n znak równości sizeof otwórz nawias okrągły wagi zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły wagi otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 43. int poj znak równości 5 średnik. Linia 45. ogolny podkreślnik problem podkreślnik plecakowy podkreślnik dynamiczne otwórz nawias okrągły wagi przecinek wartosci przecinek nazwy przecinek n przecinek poj zamknij nawias okrągły średnik. Linia 47. return 0 średnik. Linia 48. zamknij nawias klamrowy.

#include <iostream>
#include <string>

using namespace std;

void ogolny_problem_plecakowy_dynamiczne(int wagi[], int wartosci[], string nazwy[], int n, int poj) {
    int P[poj + 1] = {0};
    int Q[poj + 1] = {0};

    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 spakowane_przedmioty[n] = {0};
    int pojemnosc = poj;
    while (pojemnosc > 0) {
        if (Q[pojemnosc] != 0) {
            spakowane_przedmioty[Q[pojemnosc] - 1] += 1;
        }
        pojemnosc -= wagi[Q[pojemnosc] - 1];
    }

    cout << "Liczba spakowanych sztuk przedmiotów: " << endl;
    for (int i = 0; i < n; i++) {
        cout << nazwy[i] << "(indeks " << i << "): " << spakowane_przedmioty[i] << endl;
    }

    cout << "Wartość spakowanych przedmiotów: " << P[poj] << endl;
}

int main() {
    int wagi[] = {1, 2, 2};
    int wartosci[] = {1, 4, 5};
    string nazwy[] = {"aparat", "bukłak", "chlebak"};
    int n = sizeof(wagi) / sizeof(wagi[0]);
    int poj = 5;

    ogolny_problem_plecakowy_dynamiczne(wagi, wartosci, nazwy, n, poj);

    return 0;
}

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 C++PZG7khrclProblem plecakowy w języku C++. 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 optymalnych rozwiązań jej podproblemów

Wprowadzenie

Prezentacja multimedialna

Implementacja rozwiązania ogólnego problemu plecakowego wykorzystującego programowanie dynamiczne – język C++

Słownik