Problem wydawania reszty
Wprowadzenie
Problem wydawania reszty (ang. Coin Change Problem) to klasyczny problem algorytmiczny polegający na znalezieniu minimalnej liczby monet potrzebnych do wydania określonej kwoty. Jest to doskonały przykład ilustrujący różnicę między strategią zachłanną a programowaniem dynamicznym.
Problem formalnie:
- Dane: kwota n i zbiór nominałów monet {c₁, c₂, ..., cₖ}
- Cel: znaleźć minimalną liczbę monet sumujących się do n
Problem wydawania reszty występuje w:
- Automatach sprzedających (wydawanie reszty klientom)
- Kasach fiskalnych (optymalizacja wydawania reszty)
- Bankomatach (wybór banknotów do wypłaty)
- Systemach płatności (minimalizacja liczby transakcji)
- Grach komputerowych (systemy walut)
- Teorii liczb (reprezentacja liczb)
Algorytm zachłanny - podstawy
Strategia zachłanna
Idea: Zawsze wybieraj największą monetę nie przekraczającą pozostałej kwoty.
Algorytm zachłanny:
1. Posortuj monety malejąco
2. Dopóki reszta > 0:
- Wybierz największą monetę ≤ reszta
- Dodaj ją do rozwiązania
- Odejmij jej wartość od reszty
Implementacja podstawowa
Wyjście:
=== Algorytm zachłanny - przykłady ===
System monet: [50, 20, 10, 5, 2, 1]
Kwota: 37 zł → Monety: [20, 10, 5, 2]
→ Liczba monet: 4
Kwota: 63 zł → Monety: [50, 10, 2, 1]
→ Liczba monet: 4
Kwota: 99 zł → Monety: [50, 20, 20, 5, 2, 2]
→ Liczba monet: 6
Kwota: 142 zł → Monety: [50, 50, 20, 20, 2]
→ Liczba monet: 5
Kwota: 7 zł → Monety: [5, 2]
→ Liczba monet: 2
Systemy kanoniczne vs niekanoniczne
System kanoniczny
Definicja: System monet jest kanoniczny, jeśli algorytm zachłanny zawsze daje optymalne rozwiązanie.
Przykłady systemów kanonicznych: - Polski: {1, 2, 5, 10, 20, 50, 100, 200, 500} - Amerykański: {1, 5, 10, 25, 100} - Euro: {1, 2, 5, 10, 20, 50, 100, 200}
Właściwość: Każdy nominał jest "właściwą" wielokrotnością mniejszych.
Wyjście:
=== System kanoniczny (Polski) ===
Kwota Monety (zachłanne) Liczba
--------------------------------------------------
1 [1] 1
2 [2] 1
3 [2, 1] 2
4 [2, 2] 2
5 [5] 1
6 [5, 1] 2
7 [5, 2] 2
8 [5, 2, 1] 3
9 [5, 2, 2] 3
10 [10] 1
15 [10, 5] 2
23 [20, 2, 1] 3
37 [20, 10, 5, 2] 4
48 [20, 20, 5, 2, 1] 5
63 [50, 10, 2, 1] 4
77 [50, 20, 5, 2] 4
99 [50, 20, 20, 5, 2, 2] 6
System niekanoniczny - kontrprzykład
System niekanoniczny: Algorytm zachłanny NIE daje optymalnego rozwiązania.
Wyjście:
=== System NIEKANONICZNY - zachłanna strategia ZAWODZI ===
System monet: [25, 10, 1]
Kwota do wydania: 30
ALGORYTM ZACHŁANNY:
Krok 1: Weź 25 (największa ≤ 30) → reszta = 5
Krok 2: Weź 1 (największa ≤ 5) → reszta = 4
Krok 3: Weź 1 (największa ≤ 4) → reszta = 3
Krok 4: Weź 1 (największa ≤ 3) → reszta = 2
Krok 5: Weź 1 (największa ≤ 2) → reszta = 1
Krok 6: Weź 1 (największa ≤ 1) → reszta = 0
Monety: [25, 1, 1, 1, 1, 1]
Liczba monet: 6
ROZWIĄZANIE OPTYMALNE:
Weź 3 monety po 10
Monety: [10, 10, 10]
Liczba monet: 3
✗ Zachłanna: 6 monet
✓ Optymalna: 3 monety
✗ Różnica: 3 monet!
============================================================
Więcej przykładów dla systemu [25, 10, 1]:
============================================================
Kwota: 30 → Zachłanna: 6 monet, Może być lepiej: 3 monet ✗
Kwota: 40 → Zachłanna: 7 monet, Może być lepiej: 4 monet ✗
Kwota: 50 → Zachłanna: 2 monet, Może być lepiej: 5 monet ✓
Kwota: 60 → Zachłanna: 8 monet, Może być lepiej: 6 monet ✗
Kwota: 70 → Zachłanna: 9 monet, Może być lepiej: 7 monet ✗
Kwota: 80 → Zachłanna: 10 monet, Może być lepiej: 8 monet ✗
Rozwiązanie przez programowanie dynamiczne
Algorytm optymalny (działa dla wszystkich systemów)
Wyjście (fragment):
=== Programowanie dynamiczne ===
System monet: [25, 10, 1]
Kwota: 30
PORÓWNANIE:
Zachłanne: 6 monet → [25, 1, 1, 1, 1, 1]
DP (optymalne): 3 monet → [10, 10, 10]
============================================================
Porównanie dla różnych kwot:
============================================================
Kwota Zachłanna DP (optymalne) Status
--------------------------------------------------
1 1 1 ✓
2 2 2 ✓
3 3 3 ✓
...
30 6 3 ✗
31 7 4 ✗
...
Wizualizacja algorytmu DP
Wyjście:
=== Programowanie dynamiczne - wizualizacja ===
Kwota: 15
Monety: [10, 6, 1]
Tablica DP (dp[i] = min monet dla kwoty i):
dp[ 1] = min(dp[ 1], dp[ 0] + 1) = min(∞, 1) = 1 [użyto monety 1]
dp[ 2] = min(dp[ 2], dp[ 1] + 1) = min(∞, 2) = 2 [użyto monety 1]
dp[ 3] = min(dp[ 3], dp[ 2] + 1) = min(∞, 3) = 3 [użyto monety 1]
...
dp[ 6] = min(dp[ 6], dp[ 0] + 1) = min(7, 1) = 1 [użyto monety 6]
...
dp[10] = min(dp[10], dp[ 0] + 1) = min(∞, 1) = 1 [użyto monety 10]
...
dp[15] = min(dp[15], dp[ 9] + 1) = min(3, 2) = 2 [użyto monety 6]
Tablica dp dla kwot 0-15:
Kwota: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
dp[i]: 0 1 2 3 4 5 1 2 3 4 1 2 2 3 4 2
Odtwarzanie rozwiązania:
Krok 1: Kwota 15 → użyj monety 6 → reszta 9
Krok 2: Kwota 9 → użyj monety 6 → reszta 3
Krok 3: Kwota 3 → użyj monety 1 → reszta 2
Krok 4: Kwota 2 → użyj monety 1 → reszta 1
Krok 5: Kwota 1 → użyj monety 1 → reszta 0
Wynik: 5 monet → [6, 6, 1, 1, 1]
Weryfikacja systemu kanonicznego
Test kanoniczności
Wyjście:
=== Test kanoniczności systemów monet ===
System: Amerykański (quarters)
Monety: [1, 5, 10, 25]
Kanoniczny: ✓ TAK
System: Polski (uproszczony)
Monety: [1, 2, 5, 10, 20, 50]
Kanoniczny: ✓ TAK
System: Niekanoniczny #1
Monety: [1, 3, 4]
Kanoniczny: ✗ NIE
Kontrprzykłady (pierwsze 3):
Kwota 6: zachłanna=3 monet, optymalna=2 monet
Kwota 9: zachłanna=4 monet, optymalna=3 monet
Kwota 12: zachłanna=5 monet, optymalna=3 monet
System: Niekanoniczny #2
Monety: [1, 5, 6, 9]
Kanoniczny: ✗ NIE
Kontrprzykłady (pierwsze 3):
Kwota 11: zachłanna=3 monet, optymalna=2 monet
Kwota 16: zachłanna=4 monet, optymalna=3 monet
Kwota 17: zachłanna=4 monet, optymalna=3 monet
System: Niekanoniczny #3
Monety: [1, 10, 25]
Kanoniczny: ✗ NIE
Kontrprzykłady (pierwsze 3):
Kwota 30: zachłanna=6 monet, optymalna=3 monet
Kwota 31: zachłanna=7 monet, optymalna=4 monet
Kwota 32: zachłanna=8 monet, optymalna=5 monet
Zastosowania praktyczne
1. Automat sprzedający
Wyjście:
=== Automat sprzedający ===
Stan początkowy:
Stan magazynu monet:
50 zł: 10 szt
20 zł: 20 szt
10 zł: 30 szt
5 zł: 40 szt
2 zł: 50 szt
1 zł: 100 szt
==================================================
Transakcje:
==================================================
Transakcja 1: Reszta 37 zł
Wydane monety: [20, 10, 5, 2]
Liczba monet: 4
Transakcja 2: Reszta 63 zł
Wydane monety: [50, 10, 2, 1]
Liczba monet: 4
Transakcja 3: Reszta 18 zł
Wydane monety: [10, 5, 2, 1]
Liczba monet: 4
Transakcja 4: Reszta 99 zł
Wydane monety: [50, 20, 20, 5, 2, 2]
Liczba monet: 6
==================================================
Stan końcowy:
Stan magazynu monet:
50 zł: 8 szt
20 zł: 17 szt
10 zł: 27 szt
5 zł: 37 szt
2 zł: 45 szt
1 zł: 98 szt
2. Bankomat - wybór banknotów
Wyjście:
=== Bankomat ===
Dostępne nominały: [500, 200, 100, 50, 20, 10]
Wypłata: 280 zł
200 zł × 1
50 zł × 1
20 zł × 1
10 zł × 1
Suma banknotów: 4
Wypłata: 370 zł
200 zł × 1
100 zł × 1
50 zł × 1
20 zł × 1
Suma banknotów: 4
Wypłata: 1250 zł
500 zł × 2
200 zł × 1
50 zł × 1
Suma banknotów: 4
Wypłata: 2340 zł
500 zł × 4
200 zł × 1
100 zł × 1
20 zł × 2
Suma banknotów: 8
Warianty problemu
Wariant 1: Nieograniczona liczba monet vs ograniczona
Złożoność obliczeniowa
Porównanie algorytmów
| Algorytm | Złożoność czasowa | Złożoność pamięciowa | Poprawność |
|---|---|---|---|
| Zachłanny | O(n) | O(1) | Tylko dla systemów kanonicznych |
| DP (bottom-up) | O(amount × n) | O(amount) | Zawsze poprawny |
| DP (top-down) | O(amount × n) | O(amount) | Zawsze poprawny |
gdzie:
- n = liczba różnych nominałów
- amount = kwota do wydania
Podsumowanie
Kluczowe wnioski
| Aspekt | Algorytm zachłanny | Programowanie dynamiczne |
|---|---|---|
| Poprawność | Tylko systemy kanoniczne | Wszystkie systemy |
| Szybkość | O(n) - bardzo szybki | O(amount × n) - wolniejszy |
| Pamięć | O(1) - minimalna | O(amount) - więcej |
| Implementacja | Prosta | Bardziej złożona |
| Zastosowanie | Znane systemy (USD, EUR, PLN) | Dowolne systemy |
Kiedy używać którego?
✅ Użyj zachłannego gdy: - System monet jest kanoniczny (USD, EUR, PLN) - Szybkość jest kluczowa - Pamięć jest ograniczona
✅ Użyj DP gdy: - System może być niekanoniczny - Potrzebujesz gwarancji optymalności - Masz wystarczająco pamięci
Systemy kanoniczne w praktyce
✅ Przykłady kanonicznych: - Polski: {1, 2, 5, 10, 20, 50, 100, 200, 500} - Amerykański: {1, 5, 10, 25, 100} - Euro: {1, 2, 5, 10, 20, 50, 100, 200}
❌ Kontrprzykłady (niekanoniczne): - {1, 10, 25} - dla kwoty 30 - {1, 3, 4} - dla kwoty 6 - {1, 5, 6, 9} - dla kwoty 11
Co dalej?
Po opanowaniu problemu wydawania reszty, następne tematy to:
- Lekcja 75: Problem planowania zadań
- Activity selection problem
- Interval scheduling
-
Weighted job scheduling
-
Lekcja 76: Kompresja Huffmana
- Budowa drzewa Huffmana
- Kodowanie i dekodowanie
-
Zastosowania w kompresji
-
Zaawansowane algorytmy zachłanne:
- Dijkstra (najkrótsza ścieżka)
- Prim i Kruskal (MST)
- Load balancing
Zadania praktyczne
Zadanie 1: Weryfikator kanoniczności
Napisz funkcję sprawdzającą czy dany system monet jest kanoniczny i zwracającą wszystkie kontrprzykłady.
Zadanie 2: Optymalizacja automatu
Zaimplementuj system automatu, który śledzi stan monet i optymalizuje ich zużycie w dłuższym okresie.
Zadanie 3: Wielowalutowe wydawanie
Rozszerz problem na wydawanie reszty używając monet z różnych walut z kursami wymiany.
Zadanie 4: Minimalizacja różnych nominałów
Znajdź rozwiązanie minimalizujące liczbę RÓŻNYCH nominałów (nie całkowitą liczbę monet).
Zadanie 5: Generowanie systemów kanonicznych
Napisz algorytm generujący system kanoniczny o określonych właściwościach (np. n nominałów, maksymalny 100).
Następna lekcja: Problem planowania zadań - optymalizacja szeregowania