Przeczytaj

Implementacja rozwiązań różnych wariantów problemu plecakowego w języku C++

Ważne!

W kolejnych implementacjach wykorzystamy funkcję pomocniczą sortuj, której zadaniem jest posortowanie dostępnych przedmiotów nierosnąco ze względu na iloraz wartości oraz wag. Użyjemy zmodyfikowanego algorytmu sortowania bąbelkowegoP77EQCGCtsortowania bąbelkowego (nie będziemy go tu omawiać).

void sortuj(double wartoscDoWagi[], int indeksy[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (wartoscDoWagi[j] < wartoscDoWagi[j + 1]) {
                swap(wartoscDoWagi[j], wartoscDoWagi[j + 1]);
                swap(indeksy[j], indeksy[j + 1]);
            }
        }
    }
}

Wykorzystana funkcja swap to funkcja, która pozwala na zamienianie wartości. Funkcja swap przyjmuje dwa argumenty (zwykle są to zmienne lub elementy tablicy) i zamienia ich wartości.

Ważne!

Podejście zachłannealgorytm zachłannyzachłanne może nie dać najlepszego możliwego wyniku w wypadku problemu plecakowego.

Ogólny problem plecakowy

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
n – liczba naturalna; liczba rodzajów przedmiotów
pojemnosc – 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 pojemnosc, 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 pojemnosc
całkowita wartość spakowanego plecaka

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

maksymalna pojemność plecaka wynosi 41;
do dyspozycji mamy nieograniczoną liczbę sztuk każdego rodzaju przedmiotów;
przedmioty mają następujące wartości oraz wagi:

Przedmiot – $i$	0	1	2	3	4	5	6
Nazwa	anemon	bławatek	chaber	dziurawiec	eustoma	forsycja	gipsówka
Wartość	21	15	4	4	14	1	3
Waga	11	8	5	4	7	1	7

Już wiesz

Przypomnijmy, w jaki sposób działa algorytm, analizując zaprezentowane dane.

Zaczniemy od obliczenia ilorazów wartości i wag.

Obliczone ilorazy: 21/11, 15/8, 4/5, 4/4, 14/7, 1/1, 3/7.

Sortujemy je nierosnąco.

Posortowane nierosnąco ilorazy: 14/7, 21/11, 15/8, 4/4, 1/1, 4/5, 3/7.

Daje to następującą kolejność posortowanych nierosnąco przedmiotów: eustoma, anemon, bławatek, dziurawiec, forsycja, chaber, gipsówka (indeksy: 4, 0, 1, 3, 5, 2, 6).

Dla każdego posortowanego przedmiotu sprawdzamy, czy można go spakować, a jeśli tak, ile sztuk.

Wybieramy pierwszy przedmiot. To eustoma, której waga to 7. Do plecaka wkładamy 5 sztuk tego przedmiotu. Pojemność plecaka po spakowaniu tych przedmiotów wynosi 6.

Waga kolejnego przedmiotu (anemonu) wynosi 11, zatem nie można go spakować do plecaka.

Następny przedmiot, bławatek, waży 8. On również nie może zostać spakowany do plecaka.

Kolejny przedmiot to dziurawiec. Jego waga wynosi 4, zatem do plecaka można spakować jego jedną sztukę. Po spakowaniu kolejnych przedmiotów pojemność plecaka wynosi 2.

Następnym przedmiotem jest forsycja. Jej waga to 1. Do plecaka pakujemy jej dwie sztuki.

W plecaku nie ma więcej miejsca, zatem kolejne przedmioty nie mogą zostać spakowane.

Obliczmy całkowitą wartość spakowanych przedmiotów:

eustoma: 14 × 5 sztuk
dziurawiec: 1 × 4 sztuki
forsycja: 2 × 1 sztuka

Całkowita wartość spakowanych przedmiotów wynosi 76. Wykorzystaliśmy całe miejsce.

W programie wykorzystamy dwie funkcje:

ogolnyPlecak – funkcja mająca na celu znalezienie największej łącznej wartości przedmiotów, które można zmieścić w plecaku o określonej pojemności z wykorzystaniem podejścia zachłannego;
sortuj – funkcja pomocnicza.

Jak wspomnieliśmy, nie będziemy omawiać funkcji sortuj. Przejdziemy zatem do zapisania funkcji właściwej.

Zapisujemy jej nagłówek. Funkcja przyjmie pięć argumentów:

nazwy – tablica ł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,
n – liczba naturalna; liczba rodzajów przedmiotów,
pojemnosc – liczba naturalna; maksymalna pojemność plecaka.

int ogolnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    
}

W pierwszym kroku tworzone są dwie kolejne tablice:

wartoscDoWagi – tablica liczb rzeczywistych,
indeksy – tablica liczb naturalnych.

Obie tablice składają się z n elementów. Zapisujemy pętlę for, która będzie iterować po kolejnych elementach tablic, by je zapełnić.

Każdy i-ty element tablicy wartosci dzielimy przez i-ty element tablicy wagi. Wynik przypisujemy do i-tego elementu tablicy wartoscDoWagi. Następnie i-temu elementowi tablicy indeksy przypisujemy wartość licznika, czyli zmiennej i.

int ogolnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }
}

Po wyjściu z pętli wywołujemy funkcję sortuj.

Funkcja sortuj przyjmuje trzy argumenty:

wartoscDoWagi – tablica liczb rzeczywistych,
indeksy – tablica liczb naturalnych,
n – liczba naturalna.

int ogolnyPlecak(int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }

    sortuj(wartoscDoWagi, indeksy, n);
    
}

Po wykonaniu sortowania tworzymy zmienną wynik i przypisujemy jej wartość 0. Zmienna ta będzie przechowywała sumę wartości wybranych przedmiotów.

Tworzymy również tablicę spakowane. Będzie przechowywała liczniki spakowanych przedmiotów.

W kolejnym kroku zapisujemy pętlę for, która będzie iterowała przez posortowane przedmioty. Wykorzystamy ją do wypełnienia tablicy spakowane zerami.

Zapisujemy kolejną pętlę for. Ponownie iterujemy przez posortowane przedmioty.

W pętli utworzymy zmienną indeks, której z każdą iteracją będziemy przypisywać wartość i-tego elementu tablicy indeksy – pobieramy w ten sposób indeks bieżącego przedmiotu.

Zapisujemy pętlę while. Będzie ona wykonywała się tak długo, jak długo waga pakowanego przedmiotu będzie albo mniejsza od pojemności, albo jej równa. Dzięki tej pętli kolejne przedmioty będą mogły być dodawane więcej niż jeden raz.

int ogolnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }

    sortuj(wartoscDoWagi, indeksy, n);

    int wynik = 0;
    int spakowane[n];
    for (int i = 0; i < n; i++) {
        spakowane[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int indeks = indeksy[i];
        while (wagi[indeks] <= pojemnosc) {

Jeśli przedmiot o danym indeksie zmieści się w plecaku, waga przedmiotu odejmowana jest od dostępnej pojemności plecaka (element tablicy wagi o indeksie indeks jest odejmowany od wartości zmiennej pojemnosc). Równocześnie dodajemy wartość tego przedmiotu do wyniku (element tablicy wartosci o indeksie indeks jest dodawany do wartości zmiennej wynik). Inkrementujemy wartość elementu tablicy spakowane o indeksie indeks.

int ogolnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }

    sortuj(wartoscDoWagi, indeksy, n);

    int wynik = 0;
    int spakowane[n];
    for (int i = 0; i < n; i++) {
        spakowane[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int indeks = indeksy[i];
        while (wagi[indeks] <= pojemnosc) {
            pojemnosc -= wagi[indeks];
            wynik += wartosci[indeks];
            spakowane[indeks]++;
        }

Po wyjściu z pętli for zapisujemy kolejną pętlę for. Wykorzystamy ją do wypisywania informacji na temat tego, ile sztuk danego rodzaju przedmiotu zostało spakowanych.

Wypisujemy całkowitą wartość spakowanych przedmiotów.

Linia 1. int ogolnyPlecak otwórz nawias okrągły string nazwy otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n przecinek int pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. double wartoscDoWagi otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 3. int indeksy otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 4. 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 5. wartoscDoWagi otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości otwórz nawias okrągły double zamknij nawias okrągły wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 6. indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości i średnik. Linia 7. zamknij nawias klamrowy. Linia 9. sortuj otwórz nawias okrągły wartoscDoWagi przecinek indeksy przecinek n zamknij nawias okrągły średnik. Linia 11. int wynik znak równości 0 średnik. Linia 12. int spakowane otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 13. 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 14. spakowane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 15. zamknij nawias klamrowy. Linia 17. 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 18. int indeks znak równości indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 19. while otwórz nawias okrągły wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. pojemnosc minus znak równości wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 21. wynik plus znak równości wartosci otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 22. spakowane otwórz nawias kwadratowy indeks zamknij nawias kwadratowy plus plus średnik. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. 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 27. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liczba spakowanych sztuk przedmiotu cudzysłów 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 otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 28. zamknij nawias klamrowy. Linia 30. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik nWartosc spakowanych przedmiotow dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny wynik otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 32. return 0 średnik. Linia 33. zamknij nawias klamrowy.

int ogolnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }

    sortuj(wartoscDoWagi, indeksy, n);

    int wynik = 0;
    int spakowane[n];
    for (int i = 0; i < n; i++) {
        spakowane[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int indeks = indeksy[i];
        while (wagi[indeks] <= pojemnosc) {
            pojemnosc -= wagi[indeks];
            wynik += wartosci[indeks];
            spakowane[indeks]++;
        }
    }

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

    cout << "\nWartosc spakowanych przedmiotow: " << wynik << endl;

    return 0;
}

Dodajemy odpowiednią bibliotekę oraz wywołanie funkcji.

Pamiętamy również o komunikacie dotyczącym wartości wszystkich spakowanych przedmiotów oraz dodaniu funkcji sortuj.

Oto kompletny kod programu:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. void sortuj otwórz nawias okrągły double wartoscDoWagi otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int indeksy otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 ś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 0 średnik j otwórz nawias ostrokątny n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. swap otwórz nawias okrągły wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 10. swap otwórz nawias okrągły indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int ogolnyPlecak otwórz nawias okrągły string nazwy otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n przecinek int pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. double wartoscDoWagi otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 18. int indeksy otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 19. 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 20. wartoscDoWagi otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości otwórz nawias okrągły double zamknij nawias okrągły wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 21. indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości i średnik. Linia 22. zamknij nawias klamrowy. Linia 24. sortuj otwórz nawias okrągły wartoscDoWagi przecinek indeksy przecinek n zamknij nawias okrągły średnik. Linia 26. int wynik znak równości 0 średnik. Linia 27. int spakowane otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 28. 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 29. spakowane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik. Linia 30. zamknij nawias klamrowy. Linia 32. 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 33. int indeks znak równości indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 34. while otwórz nawias okrągły wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. pojemnosc minus znak równości wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 36. wynik plus znak równości wartosci otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 37. spakowane otwórz nawias kwadratowy indeks zamknij nawias kwadratowy plus plus średnik. Linia 38. zamknij nawias klamrowy. Linia 39. zamknij nawias klamrowy. Linia 41. 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 42. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liczba spakowanych sztuk przedmiotu cudzysłów 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 otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 43. zamknij nawias klamrowy. Linia 45. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik nWartosc spakowanych przedmiotow dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny wynik otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 48. return 0 średnik. Linia 49. zamknij nawias klamrowy. Linia 51. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. string nazwy otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy cudzysłów anemon cudzysłów przecinek cudzysłów bławatek cudzysłów przecinek cudzysłów chaber cudzysłów przecinek cudzysłów dziurawiec cudzysłów przecinek cudzysłów eustoma cudzysłów przecinek cudzysłów forsycja cudzysłów przecinek cudzysłów gipsówka cudzysłów zamknij nawias klamrowy średnik. Linia 53. int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 21 przecinek 15 przecinek 4 przecinek 4 przecinek 14 przecinek 1 przecinek 3 zamknij nawias klamrowy średnik. Linia 54. int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 11 przecinek 8 przecinek 5 przecinek 4 przecinek 7 przecinek 1 przecinek 7 zamknij nawias klamrowy średnik. Linia 55. int n znak równości 7 średnik. Linia 56. int pojemnosc znak równości 41 średnik. Linia 58. ogolnyPlecak otwórz nawias okrągły nazwy przecinek wartosci przecinek wagi przecinek n przecinek pojemnosc zamknij nawias okrągły średnik. Linia 60. return 0 średnik. Linia 61. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

void sortuj(double wartoscDoWagi[], int indeksy[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (wartoscDoWagi[j] < wartoscDoWagi[j + 1]) {
                swap(wartoscDoWagi[j], wartoscDoWagi[j + 1]);
                swap(indeksy[j], indeksy[j + 1]);
            }
        }
    }
}

int ogolnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }

    sortuj(wartoscDoWagi, indeksy, n);

    int wynik = 0;
    int spakowane[n];
    for (int i = 0; i < n; i++) {
        spakowane[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int indeks = indeksy[i];
        while (wagi[indeks] <= pojemnosc) {
            pojemnosc -= wagi[indeks];
            wynik += wartosci[indeks];
            spakowane[indeks]++;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << "Liczba spakowanych sztuk przedmiotu " << nazwy[i] <<" (indeks " << i <<"): " << spakowane[i] << endl;
    }
    
    cout << "\nWartosc spakowanych przedmiotow: " << wynik << endl;


    return 0;
}

int main() {
    string nazwy[] = {"anemon", "bławatek", "chaber", "dziurawiec", "eustoma", "forsycja", "gipsówka"};
    int wartosci[] = {21, 15, 4, 4, 14, 1, 3};
    int wagi[] = {11, 8, 5, 4, 7, 1, 7};
    int n = 7;
    int pojemnosc = 41;
    
    ogolnyPlecak(nazwy, wartosci, wagi, n, pojemnosc);

    return 0;
}

Wynik działania programu:

Liczba spakowanych sztuk przedmiotu anemon (indeks 0): 0
Liczba spakowanych sztuk przedmiotu bławatek (indeks 1): 0
Liczba spakowanych sztuk przedmiotu chaber (indeks 2): 0
Liczba spakowanych sztuk przedmiotu dziurawiec (indeks 3): 1
Liczba spakowanych sztuk przedmiotu eustoma (indeks 4): 5
Liczba spakowanych sztuk przedmiotu forsycja (indeks 5): 2
Liczba spakowanych sztuk przedmiotu gipsówka (indeks 6): 0

Wartosc spakowanych przedmiotow: 76

Decyzyjny problem plecakowy

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
n – liczba naturalna; liczba rodzajów przedmiotów
pojemnosc – liczba naturalna; maksymalna pojemność plecaka

Wynik:

spakowane przedmioty, których całkowita waga nie przekracza wartości przechowywanej w zmiennej pojemnosc, 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 pojemnosc; pakujemy po jednej sztuce przedmiotu każdego rodzaju
całkowita wartość spakowanego plecaka

Zaprezentowane rozwiązania będziemy testować dla następujących danych:

maksymalna pojemność plecaka wynosi 21;
do dyspozycji mamy po jednej sztuce przedmiotu każdego rodzaju;
przedmioty mają następujące wartości oraz wagi:

Przedmiot – $i$	0	1	2	3	4	5	6
Nazwa	aparat	baterie	czajnik	dmuchany materac	ekologiczny prysznic	filtr	garnuszek
Wartość	4	15	6	13	5	12	3
Waga	8	3	2	6	15	16	2

Pojemność plecaka to 21.

Już wiesz

Przypomnijmy, w jaki sposób działa algorytm, analizując podane dane.

Zaczniemy od obliczenia ilorazów wartości i wag: 4/8, 15/3, 6/2, 13/6, 5/15, 12/16, 3/2.

Sortujemy je nierosnąco.

Posortowane nierosnąco ilorazy: 15/3, 6/2, 13/6, 3/2, 12/16, 4/8, 5/15.

Daje to następującą kolejność posortowanych nierosnąco przedmiotów: baterie, czajnik, dmuchany materac, garnuszek, filtr, aparat, ekologiczny prysznic (indeksy: 1, 2, 3, 6, 5, 0, 4).

Dla każdego posortowanego przedmiotu sprawdzamy, czy można go spakować.

Wybieramy pierwszy przedmiot. To baterie, których waga to 3. Waga jest mniejsza od pojemności, zatem pakujemy je do plecaka. Pojemność plecaka po spakowaniu baterii wynosi 18.

Waga kolejnego przedmiotu (czajnika) wynosi 2, zatem można spakować ten przedmiot. Pojemność plecaka to 16.

Kolejnym przedmiotem jest dmuchany materac. Waga tego przedmiotu to 6. Jest mniejsza od pojemności plecaka, zatem przedmiot zostaje zapakowany. Pozostała pojemność plecaka wynosi 10.

Kolejny przedmiot, garnuszek, waży 2. Może zostać spakowany, a pojemność po jego spakowaniu wynosi 8.

Waga filtra, następnego przedmiotu, wynosi 16. Jest większa od tego, jaka jest pozostała pojemność plecaka, zatem nie można go spakować.

Aparat jest kolejnym przedmiotem, a jego waga wynosi 8. Może zostać spakowany do plecaka.

Wypełniliśmy tym samym całe miejsce w plecaku.

Obliczmy całkowitą wartość spakowanych przedmiotów:

baterie: 15
czajnik: 6
dmuchany materac: 13
garnuszek: 3
aparat: 4

Całkowita wartość spakowanych przedmiotów wynosi 41. Wykorzystaliśmy całe miejsce.

Decyzyjny problem plecakowy wymaga, by każdy przedmiot był dodawany do plecaka maksymalnie jeden raz. W programie wymaga to zmiany niewielkiej części programu.

Konieczne jest pominięcie pętli while w tym fragmencie i wykorzystanie instrukcji warunkowej if:

for (int i = 0; i < n; i++) {
	int indeks = indeksy[i];
	if (wagi[indeks] <= pojemnosc) {
		pojemnosc -= wagi[indeks];
		wynik += wartosci[indeks];
		cout << "Spakowano przedmiot " << nazwy[i] << " (indeks " << indeks <<")" << endl;
        }
    }

Zwróć uwagę, że w kodzie nie pojawia się również tablica spakowane, ponieważ w przypadku problemu decyzyjnego nie ma potrzeby liczenia, ile sztuk danego przedmiotu spakowano (do dyspozycji jest tylko jedna sztuka danego przedmiotu).

Oto kompletny kod programu:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. void sortuj otwórz nawias okrągły double wartoscDoWagi otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int indeksy otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 ś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 0 średnik j otwórz nawias ostrokątny n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. swap otwórz nawias okrągły wartoscDoWagi otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek wartoscDoWagi otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 10. swap otwórz nawias okrągły indeksy otwórz nawias kwadratowy j zamknij nawias kwadratowy przecinek indeksy otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 11. zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int decyzyjnyPlecak otwórz nawias okrągły string nazwy otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n przecinek int pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. double wartoscDoWagi otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 18. int indeksy otwórz nawias kwadratowy n zamknij nawias kwadratowy średnik. Linia 19. 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 20. wartoscDoWagi otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości otwórz nawias okrągły double zamknij nawias okrągły wartosci otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wagi otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 21. indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości i średnik. Linia 22. zamknij nawias klamrowy. Linia 24. sortuj otwórz nawias okrągły wartoscDoWagi przecinek indeksy przecinek n zamknij nawias okrągły średnik. Linia 26. int wynik znak równości 0 ś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. int indeks znak równości indeksy otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 29. if otwórz nawias okrągły wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości pojemnosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. pojemnosc minus znak równości wagi otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 31. wynik plus znak równości wartosci otwórz nawias kwadratowy indeks zamknij nawias kwadratowy średnik. Linia 32. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Spakowano przedmiot cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny nazwy otwórz nawias kwadratowy indeks 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 indeks otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów zamknij nawias okrągły cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 36. return wynik średnik. Linia 37. zamknij nawias klamrowy. Linia 39. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. 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 baterie cudzysłów przecinek cudzysłów czajnik cudzysłów przecinek cudzysłów dmuchany materac cudzysłów przecinek cudzysłów ekologiczny prysznic cudzysłów przecinek cudzysłów filtr cudzysłów przecinek cudzysłów garnuszek cudzysłów zamknij nawias klamrowy średnik. Linia 41. int wartosci otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 4 przecinek 15 przecinek 6 przecinek 13 przecinek 5 przecinek 12 przecinek 3 zamknij nawias klamrowy średnik. Linia 42. int wagi otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 8 przecinek 3 przecinek 2 przecinek 6 przecinek 15 przecinek 16 przecinek 2 zamknij nawias klamrowy średnik. Linia 43. int n znak równości 7 średnik. Linia 44. int pojemnosc znak równości 21 średnik. Linia 45. int wynik znak równości decyzyjnyPlecak otwórz nawias okrągły nazwy przecinek wartosci przecinek wagi przecinek n przecinek pojemnosc zamknij nawias okrągły średnik. Linia 47. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik nWartosc spakowanych przedmiotow dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny wynik otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 49. return 0 średnik. Linia 50. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

void sortuj(double wartoscDoWagi[], int indeksy[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (wartoscDoWagi[j] < wartoscDoWagi[j + 1]) {
                swap(wartoscDoWagi[j], wartoscDoWagi[j + 1]);
                swap(indeksy[j], indeksy[j + 1]);
            }
        }
    }
}

int decyzyjnyPlecak(string nazwy[], int wartosci[], int wagi[], int n, int pojemnosc) {
    double wartoscDoWagi[n];
    int indeksy[n];
    for (int i = 0; i < n; i++) {
        wartoscDoWagi[i] = (double)wartosci[i] / wagi[i];
        indeksy[i] = i;
    }

    sortuj(wartoscDoWagi, indeksy, n);

    int wynik = 0;
    for (int i = 0; i < n; i++) {
        int indeks = indeksy[i];
        if (wagi[indeks] <= pojemnosc) {
            pojemnosc -= wagi[indeks];
            wynik += wartosci[indeks];
            cout << "Spakowano przedmiot " << nazwy[indeks] << " (indeks " << indeks <<")" << endl;
        }
    }

    return wynik;
}

int main() {
    string nazwy[] = {"aparat", "baterie", "czajnik", "dmuchany materac", "ekologiczny prysznic", "filtr", "garnuszek"};
    int wartosci[] = {4, 15, 6,13, 5, 12, 3};
    int wagi[] = {8, 3, 2, 6, 15, 16, 2};
    int n = 7;
    int pojemnosc = 21;
    int wynik = decyzyjnyPlecak(nazwy, wartosci, wagi, n, pojemnosc);

    cout << "\nWartosc spakowanych przedmiotow: " << wynik << endl;
    
    return 0;
}

Wynik działania programu

Spakowano przedmiot baterie (indeks 1)
Spakowano przedmiot czajnik (indeks 2)
Spakowano przedmiot dmuchany materac (indeks 3)
Spakowano przedmiot garnuszek (indeks 6)
Spakowano przedmiot aparat (indeks 0)

Wartosc spakowanych przedmiotow: 41

Słownik

algorytm zachłanny

algorytm wybierający na każdym kroku lokalnie najlepsze rozwiązanie, licząc, że doprowadzi to do globalnie optymalnegooptymalizacjaoptymalnego rozwiązania problemu

optymalizacja

(od łac. optimus – najlepszy) poprawa wydajności algorytmu uzyskana dzięki zmniejszeniu liczby operacji niezbędnych do otrzymania wyniku

Wprowadzenie

Prezentacja multimedialna

Implementacja rozwiązań różnych wariantów problemu plecakowego w języku C++

Ogólny problem plecakowy

Decyzyjny problem plecakowy

Słownik