Sınırsız bozuk parayla tam para üstü
Görev tanımı
Problem
Bir otomat coins'te listelenen her değerden sınırsız bozuk para tutuyor. Tam olarak amount geri ödeyebiliyorsa True, değilse False döndür.
Örnekler
Input: coins = [4, 7], amount = 15
Output: True
Neden: 4 + 4 + 7 = 15
Input: coins = [4, 6], amount = 9
Output: False
Neden: 4'lerin ve 6'ların her karışımı çift
Input: coins = [5], amount = 0
Output: True
Neden: edge case: sıfır ödemek hiç bozuk para gerektirmez
İpuçları
0 / 3
Her zaman en büyük bozuk parayı almak başarısız olur: 4 ve 7 bozuk paralarıyla 16 için önce 7'yi almak 9 bırakır ve 4'lerin ile 7'lerin hiçbir karışımı bunu ödeyemez, oysa 4 + 4 + 4 + 4 işe yarar. Hangi tutarların ödenebildiği açısından düşün.
Bir a tutarı, bir bozuk para için a eksi o bozuk para ödenebiliyorsa ödenebilir. 0 tutarı hiç bozuk para kullanmadan ödenebilir.
Tutara göre indekslenmiş, 0. indeksi True olan bir boolean listesi tut. Her bozuk para için tutarları bozuk paranın değerinden yukarı doğru dolaş ve a eksi bozuk para ödenebiliyorsa a'yı ödenebilir olarak işaretle. Yukarı doğru dolaşmak aynı bozuk paranın yeniden kullanılmasına izin verir.
- Hedef zaman
- O(len(coins) · amount)
- Hedef alan
- O(amount)
Kısıtlar
- unlimited supply of every coin
Çözüm
Bu, evet ya da hayır cevaplı unbounded knapsack'tir; coin change'in yapılabilirlik yarısı. ok[a], a tutarının ödenip ödenemeyeceğini söyler; bir bozuk para, a - coin zaten ödenebiliyorsa a'yı ödenebilir yapar. Tutarlar üzerindeki döngü yukarı doğru gider; böylece a'ya ulaştığında a - coin elemanı bu aynı bozuk parayı zaten içeriyor olabilir, sınırsız stokun izin verdiği de tam olarak bu. Döngüyü aşağı doğru çalıştırmak bunu her bozuk parayı bir kez kullanma problemine çevirirdi. Zaman O(len(coins) · amount), alan O(amount).
def can_pay(coins, amount):
ok = [False] * (amount + 1)
ok[0] = True # zero needs no coins
for coin in coins:
for a in range(coin, amount + 1): # upward: a coin may be reused
if ok[a - coin]:
ok[a] = True
return ok[amount]
print(can_pay([4, 7], 15)) # -> True
print(can_pay([4, 6], 9)) # -> False
print(can_pay([5], 0)) # -> TrueKodda değil de fikirde mi takıldın? Coin Change bunu anlatıyor.