Tam tutar için hediye kartları
Görev tanımı
Problem
cards'taki değerlere sahip hediye kartların var ve her kart en fazla bir kez kullanılabilir. Bir kart tamamen kullanılmalı. Kartlardan bazılarının toplamı tam olarak total ediyorsa True, değilse False döndür.
Örnekler
Input: cards = [3, 34, 4, 12, 5, 2], total = 9
Output: True
Neden: 4 + 5 = 9
Input: cards = [3, 34, 4, 12, 5, 2], total = 30
Output: False
Neden: küçük kartların toplamı yalnız 26, 34'lük kart da tek başına zaten fazla
Input: cards = [7], total = 0
Output: True
Neden: edge case: hiç kart kullanmamak tam olarak sıfır öder
İpuçları
0 / 3
Kartların her alt kümesini denemek 2 üzeri n. Bir kart grubuyla ilgili önemli olan tek şey ulaştığı toplam.
Şimdiye kadar görülen kartlarla 0'dan hedefe kadar hangi toplamlara ulaşılabildiğini takip et. Bir kart eklemek, t eksi o kart bu karttan önce ulaşılabilir idiyse t toplamını ulaşılabilir yapar.
Toplama göre indekslenmiş, 0. indeksi True olan bir boolean listesi tut. Her kart için toplamları hedeften kartın değerine kadar aşağı doğru dolaş ve t eksi kart ulaşılabilirse t'yi ulaşılabilir olarak işaretle. Aşağı doğru dolaşmak bir kartın iki kez kullanılmasını engeller.
- Hedef zaman
- O(n · total)
- Hedef alan
- O(total)
Kısıtlar
- each card is used at most once and in full
Çözüm
Bu, evet ya da hayır cevaplı 0/1 knapsack'tir; çoğu zaman subset sum (alt küme toplamı) diye anılır. reachable[t], şimdiye kadar görülen kartlardan bazılarının toplamının tam olarak t olup olmadığını söyler; her yeni kart ya dışarıda kalır ve eleman olduğu gibi kalır, ya da içeri girer ve cevabı reachable[t - card]'dan kopyalar. İç döngü yüksek toplamlardan düşüklere gider ki reachable[t - card] hâlâ bu karttan önceki kartları tarif etsin; her kartı tek kullanımda tutan da bu. Zaman O(n · total), alan O(total).
def exact_total(cards, total):
reachable = [False] * (total + 1)
reachable[0] = True # zero is paid with no cards
for card in cards:
for t in range(total, card - 1, -1): # downward: each card used at most once
if reachable[t - card]:
reachable[t] = True
return reachable[total]
print(exact_total([3, 34, 4, 12, 5, 2], 9)) # -> True
print(exact_total([3, 34, 4, 12, 5, 2], 30)) # -> False
print(exact_total([7], 0)) # -> TrueKodda değil de fikirde mi takıldın? 0/1 knapsack bunu anlatıyor.