RAkTS1cDR4q491

Ilustracja przedstawia czarny plecak, który jest trzymany w dłoni.

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.

Wyróżniamy ogólny i decyzyjny problem plecakowy.

Z problemem ogólnym mamy do czynienia w sytuacji, gdy dysponujemy nieograniczoną liczbą sztuk każdego z przedmiotów.

W sytuacji, w której każdy przedmiot może być spakowany tylko raz, mówimy o problemie decyzyjnym.

Inny wariant tego problemu to ciągły problem plecakowy – w tym przypadku możliwe jest pakowanie ułamkowych części przedmiotów, jednak każdy przedmiot może być spakowany tylko raz (tak jak w przypadku decyzyjnego problemu plecakowego).

Problem plecakowy należy do problemów optymalizacjioptymalizacjaoptymalizacji. Załóżmy, że mamy zapełnić plecak, który może przenieść maksymalny ciężar $W \gt 0$. Dostępnych jest $n$ rodzajów przedmiotów. Każdy przedmiot $i$ ma swoją określoną wartość $v_i$ oraz wagę $w_i$.

Zadanie polega na spakowaniu przedmiotów do plecaka, który może pomieścić ładunek o wadze nieprzekraczającej $W$. Co więcej, wartość zgromadzonych w plecaku przedmiotów powinna być możliwie największa.

Metoda zachłanna polega na wybieraniu przedmiotów, zaczynając od najcenniejszych, czyli od tych o największym ilorazie wartości i wagi ($\frac{v_i}{w_i}$). Jeśli przechowujemy przedmioty w pewnej tablicy, to należy je posortować nierosnąco tak, aby po posortowaniu spełniały następujący warunek:

Na początku algorytmu wyznaczamy iloraz $\frac{v_i}{w_i}$, który zostanie zapamiętany w odpowiedniej zmiennej. Wówczas algorytm nie musi za każdym razem wyznaczać ilorazu od nowa – wystarczy, że pobierze go z zapisanej tablicy.

W następnym kroku algorytm przechodzi do pakowania przedmiotów do plecaka. Kolejne kroki zależne są od tego, z jakim problemem plecakowym mamy do czynienia.

Zaczniemy od zaprezentowania pseudokodu programu, który rozwiązuje ogólny problem plecakowy z wykorzystaniem algorytmu zachłannegoalgorytm zachłannyalgorytmu zachłannego.

funkcja sortuj(wartość_do_wagi, indeksy, n)
    dla każdego i = 0, 1, 2, ... n - 2,
        dla każdego j = 0, 1, 2, ... n - i - 2
            jeżeli wartość_do_wagi[j] < wartość_do_wagi[j + 1]
                pomocnicza_wdw ← wartość_do_wagi[j]
                wartość_do_wagi[j] ← wartość_do_wagi[j + 1]
                wartość_do_wagi[j + 1] ← pomocnicza_wdw
                
                pomocnicza_indeksy ← indeksy[j]
                indeksy[j] ← indeksy[j + 1]
                indeksy[j + 1] ← pomocnicza_indeksy

Ogólny problem plecakowy

Specyfikacja problemu:

Dane:

• nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów

• wartości – 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

• pojemność – 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 pojemność, 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 pojemność

• całkowita wartość spakowanego plecaka

W programie wykorzystamy dwie funkcje:

• ogólnyPlecak – 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 tu 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,

• wartości – 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,

• pojemność – liczba naturalna; maksymalna pojemność plecaka.

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)

W pierwszym kroku tworzone są dwie kolejne tablice:

• wartość_do_wagi – tablica liczb rzeczywistych,

• indeksy – tablica liczb naturalnych.

Obie tablice składają się z n elementów. Zapisujemy pętlę dla, która będzie iterować przez kolejne elementy tablic, by je zapełnić.

Każdy i-ty element tablicy wartości dzielimy przez i-ty element tablicy wagi. Wynik dodajemy do tablicy wartość_do_wagi. Kolejne wartości licznika i dodajemy do tablicy indeksy. W ten sposób obliczamy iloraz wartości i wagi poszczególnych przedmiotów i wypełniamy nimi tablicę.

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

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

Funkcja sortuj przyjmuje trzy argumenty:

• wartość_do_wagi – tablica liczb rzeczywistych,

• indeksy – tablica liczb naturalnych,

• n – liczba naturalna.

Jej zadaniem jest posortowanie obliczonych ilorazów wartości i wag przedmiotów nierosnąco.

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

    sortuj(wartość_do_wagi, indeksy, n)

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

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

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

Zapisujemy kolejną pętlę  dla. 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.

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

    sortuj(wartość_do_wagi, indeksy, n)

    wynik ← 0
    spakowane ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
    	spakowane[i] ← 0
        
    dla każdego i = 0, 1, 2, ..., n - 1
    	indeks ← indeksy[i]

Wewnątrz pętli zapisujemy pętlę dopóki. 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.

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 pojemność). Równocześnie dodajemy wartość tego przedmiotu do wyniku (element tablicy wartości o indeksie indeks jest dodawany do wartości zmiennej wynik). Inkrementujemy wartość elementu tablicy spakowane o indeksie indeks.

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

    sortuj(wartość_do_wagi, indeksy, n)

    wynik ← 0
    spakowane ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
    	spakowane[i] ← 0
        
    dla każdego i = 0, 1, 2, ..., n - 1
    	indeks ← indeksy[i]
        dopóki wagi[indeks] <= pojemność
        	pojemność ← pojemność - wagi[indeks]
			wynik ← wynik + wartości[indeks]
            spakowane[indeks] ← spakowane[indeks] + 1

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

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

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

    sortuj(wartość_do_wagi, indeksy, n)

    wynik ← 0
    spakowane ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
    	spakowane[i] ← 0
        
    dla każdego i = 0, 1, 2, ..., n - 1
    	indeks ← indeksy[i]
        dopóki wagi[indeks] <= pojemność
        	pojemność ← pojemność - wagi[indeks]
			wynik ← wynik + wartości[indeks]
            spakowane[indeks] ← spakowane[indeks] + 1
            
	dla każdego i = 0, 1, 2, ..., n - 1
    	wypisz "Liczba spakowanych sztuk przedmiotu " nazwy[i] " (indeks " i "):" spakowane[i]
    
    wypisz "Wartość spakowanych przedmiotów: " wynik
   

Dodajemy wywołanie funkcji.

Pamiętamy również o dodaniu funkcji sortuj.

Kompletny kod programu:

funkcja sortuj(wartość_do_wagi, indeksy, n)
    dla każdego i = 0, 1, 2, ... n - 2,
        dla każdego j = 0, 1, 2, ... n - i - 2
            jeżeli wartość_do_wagi[j] < wartość_do_wagi[j + 1]
                pomocnicza_wdw ← wartość_do_wagi[j]
                wartość_do_wagi[j] ← wartość_do_wagi[j + 1]
                wartość_do_wagi[j + 1] ← pomocnicza_wdw
                
                pomocnicza_indeksy ← indeksy[j]
                indeksy[j] ← indeksy[j + 1]
                indeksy[j + 1] ← pomocnicza_indeksy

funkcja ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

    sortuj(wartość_do_wagi, indeksy, n)

    wynik ← 0
    spakowane ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
    	spakowane[i] ← 0
        
    dla każdego i = 0, 1, 2, ..., n - 1
    	indeks ← indeksy[i]
        dopóki wagi[indeks] <= pojemność
        	pojemność ← pojemność - wagi[indeks]
			wynik ← wynik + wartości[indeks]
            spakowane[indeks] ← spakowane[indeks] + 1
            
	dla każdego i = 0, 1, 2, ..., n - 1
    	wypisz "Liczba spakowanych sztuk przedmiotu " nazwy[i] " (indeks " i "):" spakowane[i]
    
    wypisz "Wartość spakowanych przedmiotów: " wynik
    
nazwy ← "antyrama", "bieżnik", "chlebak", "dywanik", "ekspres", "firanki", "garnki"
wartości ← 2, 6, 4, 1, 2, 4, 15
wagi ← 2, 7, 5, 1, 2, 3, 10
n ← 7
pojemność ← 27
ogólnyPlecak(nazwy, wartości, wagi, n, pojemność)

Wynik działania programu:

Liczba spakowanych sztuk przedmiotu antyrama (indeks 0): 0
Liczba spakowanych sztuk przedmiotu bieżnik (indeks 1): 0
Liczba spakowanych sztuk przedmiotu chlebak (indeks 2): 0
Liczba spakowanych sztuk przedmiotu dywanik (indeks 3): 1
Liczba spakowanych sztuk przedmiotu ekspres (indeks 4): 0
Liczba spakowanych sztuk przedmiotu firanki (indeks 5): 2
Liczba spakowanych sztuk przedmiotu garnki (indeks 6): 2

Wartość spakowanych przedmiotów: 39

Decyzyjny problem plecakowy

Specyfikacja problemu:

Dane:

• nazwy – tablica liczb łańcuchów znaków; nazwy poszczególnych przedmiotów

• wartości – 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

• pojemność – liczba naturalna; maksymalna pojemność plecaka

Wynik:

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

• całkowita wartość spakowanego plecaka

Decyzyjny problem plecakowy wymaga, by każdy przedmiot był dodawany do plecaka maksymalnie jeden raz. W programie wymaga to zmiany jednej z instrukcji.

Konieczne jest pominięcie pętli dopóki w tym fragmencie i wykorzystanie instrukcji warunkowej jeżeli.

Wynika to z tego, że w przypadku decyzyjnego problemu plecakowego pakujemy wyłącznie jedną sztukę danego rodzaju przedmiotu. Instrukcja dopóki w rozwiązaniu problemu ogólnego odpowiadała za to, by pakowano tyle sztuk przedmiotu danego rodzaju, ile mieściło się w plecaku.

dla każdego i = 0, 1, 2, ..., n - 1	
	indeks ← indeksy[i]	
	jeżeli wagi[indeks] <= pojemność
		pojemność ← pojemność - wagi[indeks]
		wynik ← wynik + wartości[indeks]
		wypisz "Spakowano przedmiot" nazwy[indeks] "(indeks" indeks ")"

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).

Kompletny kod programu:

funkcja sortuj(wartość_do_wagi, indeksy, n)
    dla każdego i = 0, 1, 2, ... n - 2,
        dla każdego j = 0, 1, 2, ... n - i - 2
            jeżeli wartość_do_wagi[j] < wartość_do_wagi[j + 1]
                pomocnicza_wdw ← wartość_do_wagi[j]
                wartość_do_wagi[j] ← wartość_do_wagi[j + 1]
                wartość_do_wagi[j + 1] ← pomocnicza_wdw
                
                pomocnicza_indeksy ← indeksy[j]
                indeksy[j] ← indeksy[j + 1]
                indeksy[j + 1] ← pomocnicza_indeksy

funkcja decyzyjnyPlecak(nazwy, wartości, wagi, n, pojemność)
    wartość_do_wagi ← utwórz pustą tablicę
    indeksy ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
        wartość_do_wagi[i] ← wartości[i] / wagi[i]
        indeksy[i] ← i

    sortuj(wartość_do_wagi, indeksy, n)

    wynik ← 0
    spakowane ← utwórz pustą tablicę
    dla każdego i = 0, 1, 2, ..., n - 1
    	spakowane[i] ← 0
        
dla każdego i = 0, 1, 2, ..., n - 1	
	indeks ← indeksy[i]	
	jeżeli wagi[indeks] <= pojemność
		pojemność ← pojemność - wagi[indeks]
		wynik ← wynik + wartości[indeks]
		wypisz "Spakowano przedmiot" nazwy[indeks] "(indeks" indeks ")"
    
    wypisz "Wartość spakowanych przedmiotów: " wynik
    
nazwy ← "andruty", "bajaderka", "chałka", "drożdżówka", "ekler", "flan", "galaretka"
wartości ← 3, 10, 2, 3, 2, 7, 8
wagi ← 4, 4, 9, 2, 2, 8, 4
n ← 7
pojemność ← 31
decyzyjnyPlecak(nazwy, wartości, wagi, n, pojemność)

Wynik działania programu:

Spakowano przedmiot bajaderka (indeks 1)
Spakowano przedmiot galaretka (indeks 6)
Spakowano przedmiot drożdżówka (indeks 3)
Spakowano przedmiot ekler (indeks 4)
Spakowano przedmiot flan (indeks 5)
Spakowano przedmiot andruty (indeks 0)

Wartość spakowanych przedmiotów: 33

Słownik