Ödemede en iyi indirim stratejisi
Görev tanımı
Problem
Bir mağaza birkaç promosyon yürütüyor ama sipariş başına yalnız birini uyguluyor. Bir sepet, fiyatları kuruş cinsinden (item, price, quantity) listesidir. Tek bir arayüzü, bir name ve bir discount(cart) metodunu (method) paylaşan üç promosyon sınıfı yaz: PercentOff(pct) ara toplamdan yüzde pct indirim yapar, aşağı yuvarlanır; AmountOffOver(threshold, amount) ara toplam eşiğe ulaştığında sabit bir miktar indirir; BuyNGetOneFree(item, n) de bir ürünün her (n + 1). adedini bedava yapar. Sonra en büyük indirimi yapan promosyonu, eşitlikte listelenen ilkini seçen ve adını ödenecek toplamla döndüren checkout(cart, promotions) fonksiyonunu yaz. Hiçbir promosyon tasarruf sağlamıyorsa ara toplamla birlikte "no discount" döndür.
Örnekler
Input: cart = [("coffee", 1200, 3), ("mug", 900, 2)], all three promotions
Output: ('buy 2 coffee get 1 free', 4200)
Neden: bir bedava kahve 1200 kazandırır; %10'dan (540) ya da 5000 üstüne 800'den fazla
Input: cart = [("grinder", 9900, 1)], all three promotions
Output: ('10% off', 8910)
Neden: büyük bir siparişte yüzde sabit miktarı geçer
Input: cart = [("mug", 900, 1)], only AmountOffOver(5000, 800)
Output: ('no discount', 900)
Neden: edge case: sipariş eşiğin altında, bu yüzden hiçbir şey uygulanmaz
İpuçları
0 / 3
Ödeme hiçbir promosyonun nasıl çalıştığını bilmemeli. Yalnız bir ada ve her promosyona ne kadar tasarruf ettireceğini sormanın bir yoluna ihtiyacı var.
Her promosyon sınıfına kazandırılan kuruşu döndüren aynı discount(cart) metodunu ver. Taban bölmesiyle tam sayı kuruşlar toplamları kesin tutar.
checkout, anahtar olarak indirimle promosyonlar üzerinde max çağırır; bu, eşitlikte ilkini tutar; en iyi tasarruf 0 olduğunda da no discount'a düşer.
- Hedef zaman
- O(p · c)
- Hedef alan
- O(1)
Kısıtlar
- prices are integer cents
Çözüm
Bu, Strategy deseni: her promosyon tek bir arayüzün arkasında küçük bir sınıftır; böylece checkout onları bir if zinciri olmadan karşılaştırır ve yeni bir promosyon checkout'ta bir düzenleme değil, yeni bir sınıftır. Her sınıf kendi kuralını tutar: ara toplamın bir yüzdesi, bir eşiğin arkasında sabit bir miktar ya da alınan her n için bir bedava adet; hepsi tam sayı kuruş döndürür, böylece toplama hiçbir yuvarlama hatası sızmaz. Checkout her promosyona tasarrufunu sorar ve en büyüğünü tutar; eşitlik kuralı için max'ın eşit anahtarlardan ilkini döndürmesine dayanır. 0'lık bir tasarruf, hiçbir şey yapmayan bir promosyon olarak değil, no discount olarak raporlanır. p promosyon ve c sepet satırı için zaman O(p × c), girdi dışında alan O(1).
def subtotal(cart):
return sum(price * qty for _, price, qty in cart)
class PercentOff:
def __init__(self, pct):
self.name, self.pct = f"{pct}% off", pct
def discount(self, cart):
return subtotal(cart) * self.pct // 100 # round down, in cents
class AmountOffOver:
def __init__(self, threshold, amount):
self.name = f"{amount} off over {threshold}"
self.threshold, self.amount = threshold, amount
def discount(self, cart):
return self.amount if subtotal(cart) >= self.threshold else 0
class BuyNGetOneFree:
def __init__(self, item, n):
self.name = f"buy {n} {item} get 1 free"
self.item, self.n = item, n
def discount(self, cart):
return sum(price * (qty // (self.n + 1)) for name, price, qty in cart if name == self.item)
def checkout(cart, promotions):
best = max(promotions, key=lambda p: p.discount(cart), default=None) # first wins a tie
if best is None or best.discount(cart) == 0:
return "no discount", subtotal(cart)
return best.name, subtotal(cart) - best.discount(cart)
offers = [PercentOff(10), AmountOffOver(5000, 800), BuyNGetOneFree("coffee", 2)]
print(checkout([("coffee", 1200, 3), ("mug", 900, 2)], offers)) # -> ('buy 2 coffee get 1 free', 4200)
print(checkout([("grinder", 9900, 1)], offers)) # -> ('10% off', 8910)
print(checkout([("mug", 900, 1)], [AmountOffOver(5000, 800)])) # -> ('no discount', 900)
print(checkout([("tea", 1000, 5)], offers)) # -> ('800 off over 5000', 4200)Kodda değil de fikirde mi takıldın? Strategy deseni bunu anlatıyor.