Problem wydawania reszty (algorytm zachłanny)

Algorytm zachłanny wydawania reszty (1) Przykład rozwiązania problemu wydawania reszty za pomocą algorytmu zachłannego. Jak widać, rozwiązanie znalezione przez algorytm nie jest rozwiązaniem optymalnym
REKLAMA

Pragmatyczny programista. Od czeladnika do mistrza. Wydanie II
−30%53,90 zł
Algorytmy. Ćwiczenia
34,90 zł

Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.

Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).

Opis działania algorytmu

Dany jest posortowany rosnąco ciąg nominałów A=(c1, c2, …, cn) oraz kwota do wydania r. Algorytm działa następująco:

  1. Przypisujemy współczynnikom k1, k2, …, kn wartości 0.
  2. Dopóki r jest większe od zera:
    • Jeżeli r jest mniejsze od cn, zmniejszamy n o 1.
    • W przeciwnym razie zwiększamy wartość kn o 1 i zmniejszamy wartość r o cn.

Rozwiązania optymalne

Choć w przypadku ogólnym algorytm zachłanny nie daje rozwiązania optymalnego, to istnieją takie zbiory nominałów, dla których algorytm tę gwarancję daje. W pracy Combinatorics of the change-making problem (link w bibliografii) zaprezentowano metodę pozwalającą sprawdzić, czy dla danego ciągu nominałów algorytm zachłanny daje gwarancję znalezienia rozwiązania optymalnego niezależnie od wydawanej kwoty (takie ciągi nominałów w dalszej części artykułu będziemy określać jako „zachłanne”). Posortowany ciąg nominałów A=(c1, c2, …, cn) jest „zachłanny”, jeśli są spełnione następujące warunki:

  • Ciąg A′=(c1, c2, …, cn-1) jest „zachłanny”.
  • Liczba monet wyznaczona przez algorytm zachłanny dla ciągu nominałów A′ i kwoty mcn-1-cn jest mniejsza bądź równa m-1, gdzie wartość m to zaokrąglony w górę iloraz dwóch największych nominałów (cn/cn-1).

Dowód tego twierdzenia jest dostępny we wspomnianej pracy Combinatorics of the change-making problem. Znając powyższe warunki możemy sprawdzić kolejno zachłanność podciągów (c1, c2), (c1, c2, c3) aż do (c1, c2, …, cn).

Dla przykładu sprawdźmy, czy „zachłanny” jest ciąg nominałów (1, 2, 5, 10):

  • Jednoelementowy ciąg 1 musi być „zachłanny”, gdyż dla każdej kwoty istnieje tylko jedno rozwiązanie.
  • Dla ciągu (1, 2) wartość m wynosi 2. Kwota mcn-1-cn wynosi zatem 0. Algorytm zachłanny do wyznaczenia tej kwoty użyje 0 monet. 0 jest mniejsze niż 2-1, zatem ciąg jest „zachłanny”.
  • Dla ciągu (1, 2, 5) wartość m wynosi 3. Kwota mcn-1-cn wynosi zatem 1. Algorytm zachłanny do wyznaczenia tej kwoty użyje 1 monety. 1 jest mniejsze niż 3-1, zatem ciąg jest „zachłanny”.
  • Dla ciągu (1, 2, 5, 10) wartość m wynosi 2. Kwota mcn-1-cn wynosi zatem 0. Algorytm zachłanny do wyznaczenia tej kwoty użyje 0 monet. 0 jest mniejsze niż 2-1, zatem ciąg jest „zachłanny”.

Z tego twierdzenia wynikają też pewne bardziej ogólne wnioski. Zastanówmy się nad ciągami, w których każdy element ciągu jest wielokrotnością poprzedniego (kcn-1=cn, k > 0). Wówczas iloraz cn/cn-1 wynosi dokładnie k. Kwota mcn-1-cn wynosi wówczas 0. Do wydania kwoty 0 potrzeba 0 monet. 0 zawsze jest mniejsze bądź równe k-1. Podsumowując, jeśli w ciągu nominałów każdy element (poza pierwszym) jest wielokrotnością poprzedniego, to algorytm zachłanny będzie dawał rozwiązania optymalne.

Złożoność obliczeniowa

Dla kwoty 1 i n nominałów główna pętla programu wykona się n razy. Dla zbioru nominałów (1) i kwoty r pętla wykona się r razy. Można zatem powiedzieć, że złożoność czasowa algorytmu to O(n+r). Warto jednak zauważyć, że w praktyce algorytm może działać jeszcze szybciej – dla ustalonego r liczba wykonań pętli może wręcz maleć wraz ze wzrostem n, dopóki cn<r. Złożoność pamięciowa algorytmu jest stała (nie zależy od n ani r).

Bibliografia

  • A. Adamaszek, M. Adamaszek, Combinatorics of the change-making problem, European Journal of Combinatorics, Volume 31, Issue 1, 2010, s. 47-63, DOI: 10.1016/j.ejc.2009.05.002.
  • Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
Ocena: +3 Tak Nie
Liczba głosów: 3.

Dodano: 6 października 2016 12:33, ostatnia edycja: 24 kwietnia 2020 20:24.

REKLAMA

Zobacz też

Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.

Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość

Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.

Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:

$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$

Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.

→ Czytaj całość

Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.

→ Czytaj całość
Polityka prywatnościKontakt