Programowanie zachłanne, wydawanie reszty

powrót

Programowanie zachłanne (ang. greedy programming) jest metodą projektowania algorytmów, w której podejmowane są lokalnie optymalne decyzje, w celu uzyskania rozwiązania problemu. Inaczej mówiąc, w danym momencie działania algorytmu wiemy co będzie wchodziło w skład rozwiązania. Algorytmy zachłanne są stosunkowo proste i często skuteczne w rozwiązywaniu pewnych problemów optymalizacyjnych.

Idea programowania zachłannego polega na tym, aby wybierać najlepsze dostępne rozwiązanie w danym momencie, nie zastanawiając się nad dalszymi krokami. Algorytmy zachłanne są często stosowane w problemach, gdzie dokładna optymalizacja jest trudna lub czasochłonna, a osiągnięcie lokalnej optymalności na każdym etapie prowadzi do globalnej optymalności.

Przykłady problemów, które mogą być rozwiązane za pomocą algorytmów zachłannych, to:

1. Znajdowanie najkrótszej ścieżki w grafie: Algorytm Dijkstry to przykład algorytmu zachłannego, który znajduje najkrótszą ścieżkę między dwoma wierzchołkami w grafie o nieujemnych wagach krawędzi.

2. Zakodowanie Huffmana: Algorytm Huffmana jest używany do kompresji danych. Polega na przypisywaniu krótszych kodów binarnych do częściej występujących symboli.

3. Zadania planowania: W pewnych problemach planowania, gdzie każdy krok ma pewną wartość i czas trwania, algorytmy zachłanne mogą pomóc w maksymalizacji wartości w danej jednostce czasu.

4. Wybieranie przedziałów: W problemie wybierania maksymalnej liczby niekolidujących przedziałów na osi czasu, algorytmy zachłanne mogą być skuteczne.

Warto jednak zaznaczyć, że nie zawsze algorytmy zachłanne prowadzą do optymalnych rozwiązań dla wszystkich problemów. Czasem mogą dążyć do lokalnej optymalności, ale niekoniecznie do globalnej. Dlatego istnieją problemy, dla których algorytmy zachłanne nie są odpowiednie, a konieczne jest zastosowanie bardziej zaawansowanych metod.

Wydawanie reszty metodą zachłanną

Zadanie

Jasio jest w sklepie i sprzedawczyni ma do wydania pewną kwotę n złotych. Bohater poprosił, aby nominały zostały wydane w następujący sposób:

• w pierwszej kolejności należy wydać maksymalną liczbę banknotów o największym nominale,
• następnie maksymalną liczbę banknotów o maksymalnym nominale mieszczącym się w pozostałej kwocie do wydania,
• czynność powtarza aż do wydania całej reszty,

Np. 259 = 1x200 + 1x50 + 1x5 + 2x2.

Dostępne nominały: 500, 200, 100, 50, 20, 10, 5, 2, 1

Wejście

Jedna liczba n określająca resztę do wydania z zakresu [1..10⁹].

Wyjście

Dla danej reszty nominały od największego do najmniejszego. Każdy nominał poprzedzony jest niezerową wartością liczby nominałów oraz znakiem x.

Przykład

Wejście:
1899

Wyjście:
3x500 1x200 1x100 1x50 2x20 1x5 2x2

Rozwiązanie w języku Python

#******************algorytm.edu.pl*******************************
def wydaj(n):
    nominaly = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    i = 0 # wskazujemy, który aktualnie nominał będziemy wydawać
    while n > 0:
        if n >= nominaly[i]: # jeśli da się wydać przynajmniej jednym nominałem o wartości nominaly[i]
            print(n//nominaly[i],'x',nominaly[i],sep='', end=' ')
            n %= nominaly[i] # wyznaczamy to co nam zostało
        i += 1 # przechodzimy do kolejnego nominału

#******************Główna część programu**************************
wydaj(int(input())) # podaj resztę do wydania