Metoda zachłanna i programowanie dynamiczne

Dwie metody układania algorytmów z zakresu rozszerzonego. Metoda zachłanna w każdym kroku bierze to, co w danej chwili najlepsze: największą monetę, zajęcia, które najwcześniej się kończą. Jest prosta i szybka, ale nie zawsze daje najlepszy wynik. Programowanie dynamiczne liczy wyniki wszystkich mniejszych zadań, zapisuje je w tablicy i składa z nich odpowiedź, więc znajduje optimum także tam, gdzie zachłanność zawodzi.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta.

Przejdź wydawanie reszty krok po kroku

Wydawanie reszty zachłannie

Nominały są uporządkowane od największego. Dopóki reszta jest co najmniej równa nominałowi, wydaje się go i zmniejsza resztę:

def change(amount, coins):
    result = []
    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    return result


print(change(18, [10, 5, 2, 1]))
print(change(6, [4, 3, 1]))

[10, 5, 2, 1]
[4, 1, 1]

Drugi wynik nie jest najlepszy: kwotę 6 da się wydać dwiema monetami po 3.

Plan zajęć: najwięcej niekolidujących zajęć

Tu metoda zachłanna zawsze daje optimum, jeśli zajęcia są uporządkowane według końca: bierze się te, które kończą się najwcześniej i nie kolidują z poprzednio wybranymi.

events = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
events.sort(key=lambda e: e[1])
end = 0
chosen = []
for start, finish in events:
    if start >= end:
        chosen.append((start, finish))
        end = finish
print(chosen, len(chosen))

[(1, 4), (5, 7), (8, 9)] 3

Programowanie dynamiczne: najmniej monet

Tablica best[k] przechowuje najmniejszą liczbę monet dla kwoty k. Kwota k to ostatnia moneta c i najlepsze wydanie kwoty k - c, które jest już policzone:

def fewest_coins(amount, coins):
    best = [0] + [None] * amount
    for k in range(1, amount + 1):
        for c in coins:
            if c <= k and best[k - c] is not None:
                if best[k] is None or best[k - c] + 1 < best[k]:
                    best[k] = best[k - c] + 1
    return best[amount]


print(fewest_coins(6, [4, 3, 1]))
print(fewest_coins(18, [10, 5, 2, 1]))
print(fewest_coins(3, [2]))

2
4
None

Ta sama zasada daje ciąg Fibonacciego liczony od dołu: każdy wyraz raz, z dwóch już zapisanych (porównanie z rekurencją: ciąg Fibonacciego).

Najdłuższy wspólny podciąg

D[i][j] to długość najdłuższego wspólnego podciągu pierwszych i liter napisu a i pierwszych j liter napisu b. Gdy litery są równe, wspólny podciąg wydłuża się o 1, w przeciwnym razie bierze się lepszy z dwóch krótszych wariantów:

def lcs(a, b):
    D = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                D[i][j] = D[i - 1][j - 1] + 1
            else:
                D[i][j] = max(D[i - 1][j], D[i][j - 1])
    return D[len(a)][len(b)]


print(lcs("ABCBDAB", "BDCABA"))
print(lcs("informatyka", "matematyka"))

4
6

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Wydawanie reszty metodą zachłanną

Specyfikacja. Dane: kwota r i n nominałów N[1..n] uporządkowanych malejąco. Wynik: kolejne wydane nominały.

Lista kroków:

1. Wczytaj kwotę r i nominały N[1..n] (od największego).
2. Dla kolejnych nominałów N[i] wykonaj krok 3.
3. Dopóki r ≥ N[i], wydaj nominał N[i] (wypisz go) i odejmij go od r.
4. Zakończ, gdy przejrzysz wszystkie nominały.

Pseudokod:

wczytaj r, n, N
dla i = 1, 2, ..., n wykonuj
  dopóki r ≥ N[i] wykonuj
    wypisz N[i]
    r ← r - N[i]

Schemat blokowy:

Plan zajęć: najwięcej niekolidujących zajęć

Specyfikacja. Dane: n zajęć z początkami P[1..n] i końcami K[1..n], uporządkowanych rosnąco według końca. Wynik: numery wybranych zajęć i ich liczba.

Lista kroków:

1. Wczytaj n oraz P[1..n] i K[1..n]. Ustaw koniec = 0 (koniec ostatnich wybranych zajęć) i ile = 0.
2. Dla kolejnych zajęć i wykonaj krok 3.
3. Jeśli zajęcia i zaczynają się nie wcześniej niż koniec, wybierz je: zwiększ ile, ustaw koniec = K[i] i wypisz i.
4. Wypisz ile.

Pseudokod:

wczytaj n, P, K
koniec ← 0
ile ← 0
dla i = 1, 2, ..., n wykonuj
  jeżeli P[i] ≥ koniec to
    ile ← ile + 1
    koniec ← K[i]
    wypisz i
wypisz ile

Schemat blokowy:

Ciąg Fibonacciego metodą wstępującą

Specyfikacja. Dane: liczba naturalna n ≥ 1. Wynik: n-ty wyraz ciągu Fibonacciego (F[1] = F[2] = 1).

Lista kroków:

1. Wczytaj n. Zapisz w tablicy F[1] = 1 i F[2] = 1.
2. Dla i = 3, 4, …, n zapisz F[i] = F[i - 1] + F[i - 2]: każdy wyraz liczony jest raz, z wyników już zapisanych w tablicy.
3. Wypisz F[n].

Pseudokod:

wczytaj n
F[1] ← 1
F[2] ← 1
dla i = 3, 4, ..., n wykonuj
  F[i] ← F[i - 1] + F[i - 2]
wypisz F[n]

Schemat blokowy:

Najmniej monet (programowanie dynamiczne)

Specyfikacja. Dane: kwota r i n nominałów N[1..n] (w dowolnej kolejności). Wynik: najmniejsza liczba monet o sumie r (1000000, gdy kwoty nie da się wydać).

Lista kroków:

1. Wczytaj r i nominały N[1..n]. Ustaw M[0] = 0: kwota 0 nie wymaga monet.
2. Dla kolejnych kwot k = 1, 2, …, r wykonaj kroki 3-4.
3. Ustaw M[k] = 1000000 (jeszcze nie wiadomo, jak wydać k).
4. Dla każdego nominału N[i] ≤ k: jeśli M[k - N[i]] + 1 < M[k], zastąp M[k] liczbą M[k - N[i]] + 1 (ostatnia moneta to N[i]).
5. Wypisz M[r].

Pseudokod:

wczytaj r, n, N
M[0] ← 0
dla k = 1, 2, ..., r wykonuj
  M[k] ← 1000000
  dla i = 1, 2, ..., n wykonuj
    jeżeli N[i] ≤ k i M[k - N[i]] + 1 < M[k] to
      M[k] ← M[k - N[i]] + 1
wypisz M[r]

Schemat blokowy:

Najdłuższy wspólny podciąg

Specyfikacja. Dane: napisy a i b. Wynik: długość najdłuższego wspólnego podciągu napisów a i b (litery w tej samej kolejności, niekoniecznie obok siebie).

Lista kroków:

1. Wczytaj napisy a i b, n i m to ich długości.
2. Wypełnij zerami wiersz D[0][0..m] i kolumnę D[0..n][0]: z pustym napisem wspólny podciąg ma długość 0.
3. Dla i = 1, 2, …, n i j = 1, 2, …, m: jeśli a[i] = b[j], to D[i][j] = D[i - 1][j - 1] + 1, w przeciwnym razie D[i][j] = większa z liczb D[i - 1][j] i D[i][j - 1].
4. Wypisz D[n][m].

Pseudokod:

wczytaj a, b
n ← długość(a)
m ← długość(b)
dla i = 0, 1, ..., n wykonuj
  D[i][0] ← 0
dla j = 0, 1, ..., m wykonuj
  D[0][j] ← 0
dla i = 1, 2, ..., n wykonuj
  dla j = 1, 2, ..., m wykonuj
    jeżeli a[i] = b[j] to
      D[i][j] ← D[i - 1][j - 1] + 1
    w przeciwnym razie
      D[i][j] ← max(D[i - 1][j], D[i][j - 1])
wypisz D[n][m]

Schemat blokowy:

Najczęstsze błędy

• Zachłanność bez dowodu. Dla dowolnych nominałów metoda zachłanna może dać za dużo monet. Gdy zadanie nie gwarantuje “dobrych” nominałów, użyj programowania dynamicznego.
• Sortowanie zajęć według początku. Zachłanny wybór zajęć działa tylko po uporządkowaniu według końca.
• Brak przypadku “nie da się”. Kwoty 3 nie wydasz monetami 2. Tablica musi odróżniać “jeszcze nie policzone / niemożliwe” od zwykłej liczby.
• Przesunięte indeksy w tablicy D. Wiersz i kolumna 0 oznaczają pusty początek napisu, więc literę a[i - 1] porównuje się w wierszu i.

Ćwicz w przeglądarce

W kursie Algorytmy: zakres rozszerzony metoda zachłanna i programowanie dynamiczne mają osobne tematy:

• kiedy metoda zachłanna zawodzi,
• plan zajęć: najwięcej niekolidujących zajęć,
• Fibonacci metodą wstępującą,
• najmniej monet dla dowolnych nominałów,
• najdłuższy wspólny podciąg.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy. Pełna lista: algorytmy.

Dla nauczycieli

Zestawienie obu metod na tym samym zadaniu (reszta dla monet 4, 3, 1) dobrze pokazuje, po co jest programowanie dynamiczne. Tablicę best uczniowie mogą wypełnić na kartce i porównać z podglądem zmiennych. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.