Przeczytaj

Algorytm zachłanny to taki, który – dążąc do uzyskania jak najlepszego wyniku – w każdym kroku dokonuje wyboru, który w danym momencie wydaje się najlepszy.

Takie podejście może, ale nie musi dać najlepszy możliwy wynik.

Problem wydawania reszty jest jednym z przykładów problemów, w przypadku których podejście zachłanne w zupełności wystarczy. Co więcej, w niektórych sytuacjach z określonym zbiorem nominałów algorytm zachłannyalgorytm zachłannyalgorytm zachłanny faktycznie zwraca wynik, w którym wykorzystana jest najmniejsza liczba monet.

Przykład problemu wydawania reszty najmniejszą liczbą nominałów

Problem 1

Przeanalizujmy realizację algorytmu zachłannegoalgorytm zachłannyalgorytmu zachłannego wydawania reszty najmniejszą liczbą nominałów dla kwoty 2604 zł.

Mamy do dyspozycji osiem nominałów: 500 zł, 200 zł, 100 zł, 50 zł, 10 zł, 5 zł, 2 zł oraz 1 zł.

Przyjmijmy, że podczas wydawania reszty posiadamy nieskończoną liczbę monet lub banknotów każdego z podanych nominałów.

Największym nominałem jest 500 – próbujemy wydać nim 2604 zł. Najbardziej zbliżoną kwotą, jaką możemy wydać, jest 2500 zł, czyli w tym przypadku wybieramy pięć razy nominał 500.

Linia 1. Wydana gotówka dwukropek 500 500 500 500 500.

Pozostaje nam do wydania kwota równa 104 zł. Przechodzimy do nominału 200 zł i sprawdzamy, czy można nim wydać kwotę 104 zł. Kwota 200 zł jest większa od 104 zł, więc jest to niemożliwe. Sprawdzamy zatem, czy możemy wydać część pozostałej kwoty nominałem 100. Faktycznie — banknotu o nominale 100 możemy użyć jeden raz.

Linia 1. Wydana gotówka dwukropek 500 500 500 500 500 100.

Pozostaje nam do wydania 4 zł, przechodzimy więc do następnego nominału, czyli 50 zł. Nie możemy go wykorzystać, podobnie jak nominałów 20 zł, 10 zł i 5 zł. Kolejny nominał, którego możemy użyć, to 2 zł. Wykorzystujemy go dwa razy, wydając tym samym pozostałą kwotę.

Linia 1. Wydana gotówka dwukropek 500 500 500 500 500 100 2 2.

W ten sposób wydaliśmy całą kwotę i jak się okazuje, jest to faktycznie najmniejsza liczba nominałów, jaką można użyć do wydania 2604 złotych.

W polskim systemie monetarnymsystem monetarnysystemie monetarnym, gdzie mamy do wyboru nominały 500 zł, 200 zł, 100 zł, 50 zł, 20 zł, 10 zł, 5 zł, 2 zł i 1 zł, algorytm zachłanny wydawania reszty dla kwoty  całkowitoliczbowej zawsze wybierze najmniejszą możliwą liczbę monet lub banknotów.

Gdybyśmy korzystali z niestandardowych nominałów, algorytm nie zawsze zwróciłby minimalną liczbę monet lub banknotów. Np. jeśli reszta wynosi 14 zł, a dostępne nominały to 9, 7 i 1, algorytm zachłanny wybierze nominały w następującej kolejności: 9, 1, 1, 1, 1, 1 – czyli łącznie sześć monet. Optymalnym wynikiem byłyby dwie monety o nominale 7.

Może zdarzyć się sytuacja, że pomimo istnienia takiego doboru monet algorytm wybierze monety, których suma będzie mniejsza od oczekiwanej wartości reszty. Weźmy przykład, gdzie reszta do wydania wynosi 8 zł, a dostępne nominały to 5 i 2. Algorytm zachłanny wybierze jedną monetę 5 zł i jedną monetę 2 zł, dające łącznie resztę 7 zł, podczas gdy wydanie dokładnej reszty jest możliwe – poprzez wybór czterech monet o nominale 2.

Naszym zadaniem jest napisanie programu obsługującego wydawanie reszty w automacie do kawy.

W przypadku wydawania reszty liczba wybranych nominałów do wydania musi być możliwie najmniejsza. Sytuacja, w której klient otrzymuje resztę w samych monetach jednozłotowych, jest bardzo niepraktyczna i chcemy jej uniknąć. Możemy zdefiniować problem polegający na znalezieniu minimalnej liczby monet o sumarycznej wartości równej reszcie.

Algorytm wydawania reszty

Problem 2

Napisz program, który dla zadanej reszty resztaDoWydania zwróci liczbę monet lub banknotów z tablicy nominaly potrzebnych do jej wydania. Każdego nominału z tablicy nominaly możemy użyć dowolną liczbę razy.

Specyfikacja problemu:

Dane:

  • resztaDoWydania – liczba naturalna; wartość reszty do wydania

  • n – liczba naturalna; liczba dostępnych nominałów

  • nominały – tablica liczb naturalnych; tablica dostępnych nominałów posortowana malejąco

Wynik:

  • komunikat dotyczący wykorzystanych nominałów

Przykładowy komunikat:

Linia 1. Nominał 500 wydano 5 razy. Linia 2. Nominał 200 wydano 0 razy. Linia 3. Nominał 100 wydano 1 razy. Linia 4. Nominał 50 wydano 0 razy. Linia 5. Nominał 20 wydano 0 razy. Linia 6. Nominał 10 wydano 0 razy. Linia 7. Nominał 5 wydano 0 razy. Linia 8. Nominał 2 wydano 2 razy. Linia 9. Nominał 1 wydano 0 razy. Linia 10. Liczba nominałów użytych do wydania reszty 2604 dwukropek 8.

Lista kroków algorytmu:

  1. Tworzymy tablicę nominały i wczytujemy do niej wartości możliwych do wykorzystania nominałów.

  2. Tworzymy zmienną resztaDoWydania i wczytujemy do niej wartość, która jest resztą do wydania.

  3. Tworzymy zmienną wynik i przypisujemy jej wartość 0.

  4. Tworzymy zmienną k i przypisujemy jej wartość 0.

  5. Dla każdego elementu tablicy nominały:

    • zmiennej k przypisujemy wartość ilorazu zmiennych resztaDoWydania oraz i-tego elementu tablicy nominaly;

    • zmienną wynik powiększamy o wartość zmiennej k;

    • zmiennej resztaDoWydania przypisujemy wartość różnicy zmiennej resztaDoWydania oraz k, pomnożonej przez i-ty element tablicy nominały;

    • wypisujemy komunikat: Nominał (nominały[i]) wydano k razy.

  6. Wypisujemy komunikat:
    Liczba nominałów użytych do wydania reszty (resztaDoWydania): wynik

Wszystkie dostępne nominały przechowywane są w tablicy nominaly. Zakładamy przy tym, że możemy skorzystać z dowolnej liczby monet lub banknotów każdego nominału.

Ważne!

Przed zastosowaniem algorytmu zachłannego dla wydawania reszty należy się upewnić, czy tablica zawierająca dostępne nominały jest posortowana malejąco. W omawianym przykładzie zakładamy, że tablica jest posortowana, więc nie musimy tego sprawdzać.

Ważne!

Dla niektórych systemów monetarnych algorytm zachłanny wydawania reszty nie zawsze znajduje optymalny wynik. Załóżmy, że mamy do dyspozycji nominały: 5, 4 i 1, a kwota, którą musimy wydać, równa jest 8. Algorytm zachłanny wybierze jeden raz 5 i trzy razy 1, co zapisujemy jako (5,1,1,1), podczas gdy najlepsze rozwiązanie to dwie monety o nominale 4, czyli (4,4).

Ważne!

Rozwiązanie zwrócone przez algorytm może wcale nie być najlepszym rozwiązaniem, a nawet może okazać się błędne. Załóżmy, że mamy do wyboru trzy nominały: 5, 4 i 2, a kwota, którą musimy wydać, to 8. Algorytm zachłanny wybierze wówczas jeden raz 5 i jeden raz 2, co w sumie da 7, czyli wartość mniejszą od żądanej reszty 8.

Pseudokod algorytmu

Ważne!

W pseudokodzie wykorzystujemy operatory div oraz mod:

  • div – operator dzielenia całkowitego;

  • mod – operator modulo (oblicza resztę z dzielenia).

Pojawia się również funkcja długość(). Używamy jej, by obliczyć rozmiar tablicy.

Zapiszmy pseudokod zaprezentowanego algorytmu.

Zaczniemy od nagłówka funkcji zachłanneWydawanieReszty. Przyjmuje ona trzy parametry:

  • resztaDoWydania – liczba naturalna;

  • nominały – tablica liczb naturalnych;

  • n – liczba naturalna; liczba elementów tablicy nominały.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły.

Zapisujemy pętlę dla, która będzie iterować po elementach tablicy nominały.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj.

W pętli zmiennej k będziemy przypisywać wynik dzielenia całkowitego wartości zmiennej resztaDoWydania przez wartość i-tego elementu tablicy nominały. Tym samym sprawdzamy, ile razy w kwocie do wydania zmieści się dany nominał.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 3. k ← resztaDoWydania div nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy.

W kolejnym kroku aktualizujemy wartość zmiennej wynik, dodając do niej wartość zmiennej k. Tym samym obliczamy, ile wszystkich nominałów wykorzystamy do wydania reszty.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 3. k ← resztaDoWydania div nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 4. wynik ← wynik plus k.

Następnie zmiennej resztaDoWydania przypisujemy wartość operacji modulo resztaDoWydania mod nominały[i]. Obliczamy w ten sposób, ile reszty zostało do wydania, po wykorzystaniu danego nominału.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 3. k ← resztaDoWydania div nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 4. wynik ← wynik plus k. Linia 5. resztaDoWydania ← resztaDoWydania mod nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy.

Wyświetlamy komunikat mówiący o tym, ile razy użyto danego nominału do wydania reszty, i zwracamy wartość zmiennej wynik. Zmienna przechowuje informację o tym, ile w sumie nominałów wykorzystano.

Powtarzamy operacje dla wszystkich nominałów.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 3. k ← resztaDoWydania div nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 4. wynik ← wynik plus k. Linia 5. resztaDoWydania ← resztaDoWydania mod nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 7. wydrukuj cudzysłów Nominał cudzysłów nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy cudzysłów wydano cudzysłów k cudzysłów razy cudzysłów. Linia 9. zwroć wynik.

Dodajemy odpowiednie wywołanie funkcji.

Linia 1. nominały znak równości otwórz nawias kwadratowy 50 przecinek 20 przecinek 10 przecinek 5 przecinek 2 przecinek 1 zamknij nawias kwadratowy. Linia 2. n znak równości długość otwórz nawias okrągły nominały zamknij nawias okrągły. Linia 3. resztaDoWydania znak równości 77. Linia 4. k znak równości zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 6. wydrukuj cudzysłów Liczba nominałów użytych do wydania reszty cudzysłów resztaDoWydania cudzysłów dwukropek cudzysłów k. Linia 7. wydrukuj cudzysłów Liczba wszystkich użytych nominałów cudzysłów wynik.

Zaprezentowana implementacja nie jest jednak jedyną możliwą. W kolejnej wersji wykorzystujemy odejmowanie każdej monety oddzielnie w zagnieżdżonej pętli.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 3. dopóki nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny resztaDoWydania wykonuj. Linia 4. resztaDoWydania ← resztaDoWydania minus nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 5. wynik ← wynik plus 1. Linia 7. wydrukuj cudzysłów Nominał cudzysłów nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy cudzysłów wydano cudzysłów k cudzysłów razy cudzysłów. Linia 9. zwróć wynik.

Ostatnia wersja algorytmu zapamiętuje w zmiennej k liczbę powtórzeń danego nominału. Nie używamy również operacji obliczania reszty z dzielenia.

Linia 1. funkcja zachłanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominały przecinek n zamknij nawias okrągły. Linia 2. dla każdego i znak równości 0 przecinek 1 przecinek kropka kropka kropka przecinek n minus 1 wykonuj. Linia 3. k ← resztaDoWydania div nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 4. resztaDoWydania ← resztaDoWydania minus k asterysk nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 5. wynik ← wynik plus k. Linia 7. wydrukuj cudzysłów Nominał cudzysłów nominały otwórz nawias kwadratowy i zamknij nawias kwadratowy cudzysłów wydano cudzysłów k cudzysłów razy cudzysłów. Linia 9. zwróć wynik.

Porównajmy wyniki otrzymane po zastosowaniu kolejnych algorytmów.

Spróbujemy wydać resztę równą 129, wykorzystując nominały: 50, 20, 10, 5, 2, 1.

Nominał

50

20

10

5

2

1

Suma wykorzystanych nominałów

Przykład 1 

2

1

0

1

2

0

6

Przykład 2 

2

1

0

1

2

0

6

Przykład 3

2

1

0

1

2

0

6

Choć liczba wydanych nominałów jest taka sama, poszczególne algorytmy różnią się tym, ile razy wykonują się pętle. Pod tym względem najlepszy jest algorytm trzeci, który wykonuje się cztery razy. Algorytm pierwszy wykonuje się pięć razy, natomiast drugi – aż sześć razy.

Polecenie 1

Wybierz inną resztę i zestaw nominałów. Dla wybranych danych przeanalizuj na liczbach, jakie wyniki dają poszczególne algorytmy.

Słownik

algorytm zachłanny
algorytm zachłanny

algorytm dokonujący na każdym kroku takiego wyboru, który wydaje się w danym momencie najlepszy, zakładając, że seria takich kroków doprowadzi do wyniku globalnie optymalnego

modulo
modulo

operacja zwracająca resztę z dzielenia jednej liczby całkowitej przez drugą

system monetarny
system monetarny

podział określonej waluty na nominały o określonej wartości

Wprowadzenie
Aplet