change-making problem

Angol

Főnév

change-making problem (tsz. change-making problems)

(informatika) A visszaadás probléma vagy érmeprobléma (change-making problem) egy klasszikus dinamikus programozási feladat, amelynek célja:

Adott címletekből álló érmesorozat és egy adott összeg esetén határozd meg, hogyan lehet az összeget előállítani a lehető legkevesebb érme felhasználásával.

2. Formális definíció

Legyen adott:

Egy érmesorozat ${\textstyle C=\{c_{1},c_{2},...,c_{k}\}}$ (pl. 1, 2, 5, 10, 20, 50 Ft)
Egy összeg ${\textstyle N\in \mathbb {N} }$

Cél:

Minimális számú érmével állítsuk elő az ${\textstyle N}$ összeget
Minden címlet korlátlan számban áll rendelkezésre (alapváltozat)

3. Motiváció – Hol használjuk?

🏦 Bankautomaták
💳 Vásárlási rendszerek
🧮 Összegkombinációk számítása
🧠 AI és játékelmélet
📦 Erőforrás-felosztás modellezése

4. Problémaváltozatok

Változat	Leírás
Minimális érmék száma	Alapprobléma
Összes lehetséges kombináció	Kombinatorikai kérdés
Minden érme csak egyszer használható	0–1 érmeprobléma
Véges sok érme minden címletből	Tovább általánosított
Nincs megoldás	Nem minden N állítható elő adott címletekből

5. Megoldás – Dinamikus programozás

Legyen:

${\textstyle dp[n]}$ : minimális érmeszám, amivel ${\textstyle n}$ -et elő lehet állítani
Kezdeti érték: ${\textstyle dp[0]=0}$
Rekurzív reláció:

$dp[n]=\min _{c\in C,c\leq n}\{dp[n-c]+1\}$

Ez azt jelenti: az ${\textstyle n}$ -hez a legjobb olyan előző állapotot keressük, ahonnan egy érme hozzáadásával ${\textstyle n}$ -t kapunk.

6. Python példa – minimális érmék száma

def min_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Példa: 11 Ft visszaadása 1, 2, 5 Ft-os érmékkel
coins = [1, 2, 5]
amount = 11
print("Minimális érmék száma:", min_coins(coins, amount))  # 3 (5+5+1)

7. Megoldás visszafejtése – Hány darab melyikből?

A fenti algoritmust bővíthetjük úgy, hogy tároljuk, melyik érmét használtuk.

def coin_combination(coins, amount):
    dp = [float('inf')] * (amount + 1)
    choice = [-1] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                choice[a] = c

    if dp[amount] == float('inf'):
        return None

    # Kombináció visszaállítása
    result = []
    while amount > 0:
        result.append(choice[amount])
        amount -= choice[amount]
    
    return result

print(coin_combination([1, 2, 5], 11))  # [5, 5, 1]

8. Greedy algoritmus – Mikor működik?

Greedy (legnagyobb érmét válasszuk mindig) nem mindig működik.

Példa:

Érmesorozat: ${\textstyle C=\{1,3,4\}}$ , Összeg: 6

Greedy: 4 + 1 + 1 → 3 érme
Optimális: 3 + 3 → 2 érme

➡️ Greedy algoritmus akkor működik biztosan, ha az érmék kanonikus rendszert alkotnak (pl. 1, 2, 5, 10, 20, 50, 100).

9. Teljes megoldások száma (kombinációs változat)

Cél: Hányféleképpen lehet az összeget előállítani érmékkel?

Ez a coin change II probléma.

def count_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]

    return dp[amount]

print(count_ways([1, 2, 5], 5))  # 4 mód (pl. 5; 2+2+1; 2+1+1+1; 1+1+1+1+1)

10. Összefoglalás

A visszaadás probléma egy dinamikus programozási alapfeladat, amelyre több változat is létezik:

✔️ Miért fontos?

Mert alapvető kombinatorikai gondolkodást tanít
Mert sok valós életbeli probléma redukálható erre
Mert jól demonstrálja a top-down vs bottom-up DP-t
Mert könnyen bővíthető további megszorításokkal

✔️ Típusok:

Minimális érmék száma
Összes kombináció
Heurisztikus (greedy) megoldás
0–1 érmeprobléma (mindenből csak egyszer lehet választani)

További információk

change-making problem - Szótár.net (en-hu)
change-making problem - Sztaki (en-hu)
change-making problem - Merriam–Webster
change-making problem - Cambridge
change-making problem - WordNet
change-making problem - Яндекс (en-ru)
change-making problem - Google (en-hu)
change-making problem - Wikidata
change-making problem - Wikipédia (angol)