Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Materiały dla klasy III

Algorytmy zachłanne

SPIS TREŚCI

Co to jest algorytm zachłanny?

Pojęcie "algorytm zachłanny" (ang. greedy algorithm) oznacza w informatyce taki algorytm, który szuka rozwiązania globalnego przez podejmowanie najlepszych decyzji lokalnie. Takie podejście upraszcza algorytm, jednakże nie daje gwarancji znalezienia rozwiązania optymalnego.

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ż:

sumamax = 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

Na początek:  podrozdziału   strony 

Wydawanie reszty

Na lekcji napiszemy program, który wykorzysta algorytm zachłanny do rozbicia danej kwoty pieniężnej na sumę monet o zadanych nominałach. Zadanie jest następujące:

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
d1 d2 ... dn

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.

Na początek:  podrozdziału   strony 

Uczta kinomana

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:

Nr Godzina
rozpoczęcia
Godzina
zakończenia
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

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:

Nr Godzina
rozpoczęcia
Godzina
zakończenia
4. 8 9
10. 7 9
12. 9 10
11. 10 11
5. 10 12
13. 11 12
2. 10 13
15. 12 13
1. 12 14
3. 13 15
7. 14 16
14. 15 17
6. 16 18
8. 19 22
9. 20 22

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:

Nr Godzina
rozpoczęcia
Godzina
zakończenia
4. 8 9
11. 10 11
15. 12 13
7. 14 16
8. 19 22

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
          ki
          pisz nr[k], gr[k], gz[k]
          lfklfk + 1
  11.     ii + 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.

Na początek:  podrozdziału   strony