Przykładem algorytmu zachłannego jest znajdowanie największej sumy w piramidzie liczb. Piramida zbudowana jest w ten sposób, iż liczby są układane warstwami. Każda liczba warstwy górnej ma pod sobą dwie liczby warstwy dolnej:

W algorytmie zachłannym idziemy w dół od liczby na szczycie piramidy. Przy przejściu niżej wybieramy liczbę większą i kolejne liczby sumujemy.

	Zaczynamy od pierwszej liczby: suma = 2
	Idąc w dół piramidy, wybieramy większą liczbę z pary: suma = 2 + 5 = 7
	Przechodzimy w dół i znów wybieramy największą liczbę z pary: suma = 2 + 5 + 4 = 11
	W następnej warstwie wybieramy największą liczbę z pary: suma = 2 + 5 + 4 + 5 = 16
	W ostatniej warstwie znów wybieramy największą liczbę w parze: suma = 2 + 5 + 4 + 5 + 3 = 19

Otrzymaliśmy wynik 19. Jednakże nie jest to suma największa, gdyż:

suma_max = 2 + 3 + 7 + 8 + 6 = 26

Algorytm zachłanny nie analizuje wszystkich możliwych sum, lecz tylko podejmuje decyzje optymalne lokalnie: przechodzi do największej liczby z pary

Mamy do dyspozycji nieograniczony zbiór monet o zadanych nominałach. Mamy przy pomocy tych monet wydać resztę o jak najmniejszej liczbie monet. Na przykład dysponujemy monetami {10, 5, 2, 1}. Mamy wydać 28 zł. Wydajemy monety 10 10 5 2 1.

Algorytm wydawania reszty jest następujący:

1. Wczytaj resztę r.
2. Wczytaj liczbę nominałów n.
3. Wczytaj tablicę nominałów t.
4. Ustaw i = 0 (pierwszy nominał)
5. Dopóki r > 0, wykonuj kroki 6...7
6. Dopóki r >= t[i]: r = r - t[i], pisz t[i]
7. i = i + 1
8. Koniec

Dane dla programu mają postać:

r
n
d₁ d₂ ... d_n

Gdzie:
r – reszta do wydania
n – liczba nominałów monet
d – nominały monet

Przykładowe dane:

156
5
20 10 5 2 1

// Wydawanie reszty
//------------------

#include <iostream>

using namespace std;

int main()
{
    int r; cin >> r;
    int n; cin >> n;
    int t[n], i;
    for(i = 0; i < n; i++) cin >> t[i];

    cout << endl << "RESZTA = " << r << endl;

    i = 0;

    while (r > 0)
    {
       while(r >= t[i])
       {
           r = r - t[i];
           cout << t[i] << endl;
       }

       i++;
    }

    cout << endl << "KONIEC" << endl;

    return 0;
}

Jeśli naszym celem jest wydanie jak najmniejszej liczby monet, to dla pewnych danych algorytm zachłanny zawodzi. Przykładowo wprowadź do programu następujące dane:

30
3
21 10 1

Ponieważ algorytm zachłanny rozpocznie wydawanie od największej monety, to jako pierwszą wyda monetę o nominale 21 (pomińmy fakt, iż takich monet w praktyce nigdzie nie ma, to tylko przykład). Po wydaniu tej monety pozostanie do wydania 30 - 21 = 9. Ponieważ następna moneta 10 jest za duża, algorytm przejdzie do monety 1 i nią wyda resztę 9. Otrzymamy:

30 = 21 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Daje to w sumie 10 monet. Jednakże sumę 30 da się wydać za pomocą 3 monet 10:

30 = 10 + 10 + 10

Tego rozwiązania algorytm zachłanny nie znajduje.

Nasz program zakłada, iż daną resztę zawsze da się wydać, przy pomocy zdefiniowanego zestawu monet. Co jednak w przypadku, gdy tak nie jest? Otóż wtedy musimy zmodyfikować algorytm, tak aby sprawdzał, czy nie został wyczerpany zbiór dostępnych monet, a jeśli tak, to powinien przerwać wydawanie i wypisać niewydaną resztę:

1. Wczytaj resztę r.
2. Wczytaj liczbę nominałów n.
3. Wczytaj tablicę nominałów t.
4. Ustaw i = 0 (pierwszy nominał)
5. Dopóki (r > 0) i (i < n), wykonuj kroki 6...7
6. Dopóki r >= t[i]: r = r - t[i], pisz t[i]
7. i = i + 1
8. Jeśli r = 0, pisz "SUKCES"
   inaczej pisz r
9. Koniec

Potrzebne zmiany oznaczyłem kolorem czerwonym.

Przykładowe dane testowe:

176
4
100 20 5 1

176
5
100 20 10 5 2

Twoim zadaniem jest wprowadzenie odpowiednich zmian do programu. Następnie program należy przetestować i wysłać plik main.cpp w załączniku listu na adres nauczyciela. W temacie listu wpisujemy swoje imię, nazwisko, klasę oraz kod WR2. Termin do dnia poprzedzającego następne zajęcia.

Podejście zachłanne pozwala rozwiązywać niektóre problemy w sposób optymalny. Wyobraźmy sobie taką sytuację:

W pewnym mieście odbywa się festiwal filmowy. Wszystkie kina wyświetlają różne filmy o różnych godzinach. Seanse filmowe mogą się pokrywać, tzn. w kilku kinach mogą być jednocześnie wyświetlane filmy. Nasz kinoman chce oglądnąć jak najwięcej filmów, zatem po zakończeniu oglądanego filmu w jednym kinie, musi przejść do innego kina, gdzie będzie wyświetlany następny film. Ponieważ przejście z kina do kina zajmuje nieco czasu, kinoman musi wybrać taki seans, który rozpoczyna się później od zakończenia filmu, który kinoman oglądał. Dla ułatwienia załóżmy, iż filmy są wyświetlane o równych godzinach i również kończą się o równych godzinach. Zatem, jeśli oglądany film skończy się o godzinie 10:00, to następny możliwy do oglądnięcia film nie może rozpocząć się wcześniej niż o godzinie 11:00. Jaką strategię powinien przyjąć kinoman, aby mógł obejrzeć najwięcej filmów?

Otóż okazuje się, iż z dostępnych seansów kinoman powinien zawsze wybierać takie, które kończą się najwcześniej. Należy zatem posortować seansy w porządku niemalejącym wg godzin zakończenia i wybierać takie, które rozpoczynają się po seansie oglądniętym. Zobaczmy to na przykładzie. Poniższa tabelka definiuje seanse za pomocą numeru filmu (dla ułatwienia), godziny rozpoczęcia wyświetlania tego filmu w kinie i godziny zakończenia projekcji:

Na wykresie czasowym rozkład seansów wygląda następująco:

W pierwszym kroku sortujemy niemalejąco tablicę wg ostatniej kolumny i otrzymujemy filmy uporządkowane niemalejąco wg czasu zakończenia:

Kinoman wybiera z tablicy pierwszy film o numerze 4. Film kończy się o godzinie 9:00. Zatem kinoman przegląda kolejne komórki tablicy, aż trafi na film, który rozpoczyna się po godzinie 9:00. To film nr 11. Ten film kończy się o godzinie 11. Kinoman szuka dalej i trafia na film nr 15 rozpoczynający się o godzinie 12:00 i trwający do godz. 13. Postępując dalej wg tego schematu kinoman wybiera film nr 7 od 14:00 do 16:00, potem film nr 8 od 19:00 do 22:00. Otrzymujemy następującą listę filmów kinomana:

Jest ich 5.

Wybrana ścieżka oglądania seansów przez kinomana jest następująca:

Zachłanność tego postępowania polega na tym, iż nie analizujemy wszystkich możliwych układów seansów, a jedynie wybieramy pierwszy najbliższy seans w danym momencie - gwarantuje nam to posortowanie seansów wg rosnących czasów zakończenia. Otrzymany wynik jest rozwiązaniem dobrym, chociaż możliwe są również inne ścieżki o tej samej liczbie filmów, np: 10-11-15-7-8. 12-13-3-6-8...

Dane dla programu będą miały następującą postać:

n
{numer groz gzak} n razy dla poszczególnych seansów

n – liczba seansów
numer – numer seansu
groz – godzina rozpoczęcia seansu
gzak – godzina zakończenia seansu

Na przykład dane z naszej tabelki przyjmą postać:

15
1 12 14
2 10 13
3 13 15
4 8 9
5 10 12
6 16 18
7 14 16
8 19 22
9 20 22
10 7 9
11 10 11
12 9 10
13 11 12
14 15 17
15 12 13

15 to liczba wszystkich seansów, po której występuje 15 trójek liczb definiujących poszczególne seanse. Tego typu dane są powiązane ze sobą i odczytamy je do 3 osobnych tablic. Dany seans będzie przechowywany w tych tablicach pod tym samym indeksem. Zatem przy sortowaniu danych wg jednej tablicy musimy również przenosić komórki pozostałych tablic, aby była zachowana spójność danych. Język C++ posiada lepsze sposoby na przetwarzanie takich powiązanych ze sobą danych (struktury i tablice struktur lub listy struktur), jednakże pominiemy je z braku czasu i zastosujemy sposób najprostszy: osobne tablice.

Algorytm wygląda następująco:

Zmienne:

n – liczba seansów
nr – tablica z numerami seansów
gr – tablica z godzinami rozpoczęcia seansów
gz – tablica z godzinami zakończenia seansów
k – indeks seansu kinomana
lfk – liczba filmów oglądniętych przez kinomana
i – indeksy tablic

1. Czytaj n
2. Utwórz tablice nr, gr i gz o n komórkach
3. Dla i = 0,1,...,n-1: czytaj nr[i], gr[i], gz[i]
4. Posortuj niemalejąco tablice nr, gr i gz wg komórek tablicy gz
5. k ← 0
6. lfk ← 1
7. i ← 1
8. Pisz nr[k], gr[k], gz[k]
9. Dopóki i < n, wykonuj kroki 10...11
10.    Jeśli gr[i] > gz[k], to
          k ← i
          pisz nr[k], gr[k], gz[k]
          lfk ← lfk + 1
11.     i ← i + 1
12. Pisz lfk
13. Zakończ

Odpowiedni program napiszemy w trakcie lekcji. Do sortowania tabel wykorzystamy algorytm sortowania przez wybór. Będziemy sortować tabelę gz wspólnie z komórkami pozostałych tabel.