AI'yı Denetle
En Az Bozuk Para
Açgözlü seçim her zaman doğru mu? Üç çözümü etiketle.Problem
min_coins(amount): 1, 3 ve 4'lük paralarla amount tutarını en az kaç parayla ödersin? (0 ≤ amount ≤ 30)Çözüm A
1def min_coins(amount):
2 count = 0
3 for c in (4, 3, 1):
4 count += amount // c
5 amount %= c
6 return count
Çözüm B
1def min_coins(amount):
2 best = [0] + [amount + 1] * amount
3 for x in range(1, amount + 1):
4 for c in (1, 3, 4):
5 if c <= x:
6 best[x] = min(best[x], best[x - c] + 1)
7 return best[amount]
Çözüm C
1def min_coins(amount):
2 if amount == 0:
3 return 0
4 return 1 + min(min_coins(amount - c) for c in (1, 3, 4) if c <= amount)