Pisanie dynamicznych algorytmów

6.1 Główne kroki w tworzeniu dynamicznych algorytmów.

Główne kroki w tworzeniu dynamicznych algorytmów

1. Określenie podzadań:

Rozbij problem na mniejsze podzadania, które mogą być rozwiązane niezależnie od siebie. Te podzadania powinny się pokrywać, aby można było korzystać z wyników poprzednich obliczeń.

2. Identyfikacja stanów:

Określ wszystkie możliwe stany, które mogą pojawić się przy rozwiązywaniu problemu. Stany powinny opisywać wszystkie niezbędne informacje do przejścia z jednego kroku do kolejnego.

3. Formułowanie relacji rekurencyjnej:

Określ, jak rozwiązanie problemu dla bieżącego stanu zależy od rozwiązań dla poprzednich stanów. Ta relacja powinna wyrażać, jak można uzyskać optymalne rozwiązanie, korzystając z rozwiązań dla podzadań.

4. Określenie przypadków bazowych:

Określ przypadki bazowe, dla których rozwiązanie problemu jest znane bezpośrednio bez potrzeby dalszych obliczeń.

5. Wypełnianie tabeli:

Stwórz tabelę (zazwyczaj tablicę lub macierz) do przechowywania rozwiązań wszystkich podzadań. Użyj relacji rekurencyjnej i przypadków bazowych do wypełnienia tabeli od dołu do góry lub od góry do dołu.

6. Optymalizacja (memoizacja):

Jeśli używasz podejścia rekurencyjnego, dodaj memoizację, aby zapisać wyniki podzadań i uniknąć ich powtórnych obliczeń.

Czasowa i przestrzenna złożoność dynamicznych algorytmów

Złożoność czasowa:

• Złożoność czasowa dynamicznych algorytmów zazwyczaj wyraża się przez liczbę podzadań i czas, potrzebny na obliczenie każdego z podzadań.
• W większości przypadków złożoność czasowa wynosi O(n) lub O(n^2), gdzie n to rozmiar danych wejściowych.

Złożoność przestrzenna:

• Złożoność przestrzenna zależy od liczby stanów, które trzeba przechować.
• W niektórych przypadkach możliwe jest zmniejszenie złożoności przestrzennej przez użycie optymalizacji, takich jak redukcja pamięci do O(n) lub O(1).

6.2 Problem plecakowy.

Problem plecakowy to klasyczny problem optymalizacji kombinatorycznej, który pojawia się w różnych dziedzinach, w tym informatyce, ekonomii i zarządzaniu logistyką. Głównym celem problemu jest jak najefektywniejsze wykorzystanie ograniczonych zasobów.

Opis problemu plecakowego

Mamy plecak, który może wytrzymać określoną wagę W. Mamy także n przedmiotów, z których każdy ma określoną wagę wt[i] i wartość val[i]. Musisz określić, które przedmioty wziąć, aby zmaksymalizować całkowitą wartość przedmiotów w plecaku, nie przekraczając jego pojemności wagowej.

Rodzaje problemów plecakowych

1. Problem plecakowy 0/1 (0/1 Knapsack Problem):

Każdy przedmiot można albo wziąć, albo nie (nie można brać częściowo).

2. Problem plecakowy z podziałem (Fractional Knapsack Problem):

Każdy przedmiot można podzielić i wziąć dowolną jego część.

3. Wielokrotny problem plecakowy (Multiple Knapsack Problem):

Mamy kilka plecaków z różnymi ograniczeniami wagowymi.

Formułowanie problemu plecakowego 0/1 w terminach teorii algorytmów:

Relacja rekurencyjna:

Dla każdego przedmiotu i i dla każdej możliwej wagi w (od 0 do W), optymalne rozwiązanie można wyrazić w następujący sposób:

• Jeśli przedmiot i nie jest dodawany do plecaka, to optymalna wartość wynosi optymalną wartość dla i − 1 przedmiotów i wagi w.
• Jeśli przedmiot i jest dodawany do plecaka, to optymalna wartość wynosi wartość tego przedmiotu plus optymalna wartość dla i − 1 przedmiotów i wagi w − wt[i].

Złożoność czasowa i przestrzenna

Złożoność czasowa:

Złożoność czasowa tego algorytmu wynosi O(nW) gdzie n to liczba przedmiotów, a W to pojemność plecaka. Jest to związane z koniecznością wypełnienia tabeli rozmiaru n × W.

Złożoność przestrzenna:

Złożoność przestrzenna również wynosi O(nW), ponieważ potrzebna jest tablica do przechowywania wyników pośrednich.

Przykłady implementacji problemu plecakowego 0/1

def knapsack(W, wt, val, n):
    # Tworzymy tabelę do przechowywania wyników pośrednich
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Wypełniamy tabelę dp od dołu do góry
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Przykład użycia
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Maksymalna wartość plecaka: {knapsack(W, wt, val, n)}")
        

6.3 Problem rozmieniania monet.

Problem rozmieniania monet to klasyczny problem programowania dynamicznego, który polega na znalezieniu minimalnej liczby monet lub liczby sposobów na uzyskanie określonej kwoty pieniędzy z zestawu monet o podanych nominałach. Ten problem ma dwa podstawowe warianty:

Minimalna liczba monet (Minimum Coin Change Problem):

Znajdź minimalną liczbę monet, która sumuje się do zadanej kwoty.

Liczba sposobów (Number of Ways to Make Change):

Znajdź liczbę różnych sposobów na uzyskanie zadanej kwoty z podanego zestawu monet.

Wariant 1. Minimalna liczba monet

Opis problemu

Dane:

• Nieograniczony zbiór monet o określonych nominałach.
• Celowa kwota S.

Należy:

• Znajdź minimalną liczbę monet, która sumuje się do kwoty S.

Rozwiązanie z użyciem programowania dynamicznego

Relacja rekurencyjna:

• Niech dp[i] oznacza minimalną liczbę monet potrzebną do uzyskania kwoty i.
• Dla każdej monety c z zestawu monet, jeśli i ≥ c, wtedy: dp[i] = min(dp[i], dp[i − c] + 1)

Przypadki bazowe:

• dp[0] = 0 (dla kwoty 0 potrzeba 0 monet).

Złożoność czasowa i przestrzenna:

• Złożoność czasowa: O(n ⋅ S), gdzie n to liczba nominałów monet, S — celowa kwota.
• Złożoność przestrzenna: O(S), ponieważ potrzebna jest tablica do przechowywania minimalnej liczby monet dla każdej kwoty od 0 do S.

Przykład implementacji w Pythonie

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Przykład użycia
coins = [1, 2, 5]
S = 11
print(f"Minimalna liczba monet dla kwoty {S}: {min_coins(coins, S)}")
        
        

Problem rozmieniania monet demonstruje elastyczność programowania dynamicznego. Używa się go do nauczania i badania technik algorytmicznych, ponieważ pokazuje, jak można używać relacji rekurencyjnych i przypadków bazowych do efektywnego rozwiązywania problemów.