NP-complete

NP-complete problemlerin özelliğini öğrenirsin.

NP-complete

Bir problem NP-complete ise hem NP'de hem de NP-hard'dır. Tüm NP problemleri bu probleme polinom zamanda azaltılabilir.

Eğer bir NP-complete problem polinom zamanda çözülürse, tüm NP polinom zamanda çözülür demektir; yani P=NP.

Brute force

Subset sum NP-complete bir problemdir. Basit çözüm, tüm 2^n alt kümeyi denemektir; bu O(2^n)'dir.

Küçük girdiler için brute force işe yarar. Büyük girdiler için yaklaşık algoritmalar gerekir.

Uygulama brute_force_subset fonksiyonu

brute_force_subset(arr, target) yaz. Tüm alt kümeleri dene, toplam target olan var mı döndür. print(brute_force_subset([3, 5, 7], 10)) ile True yazdır.

Örnek çözümü göster

def brute_force_subset(arr, target):
    # Tüm alt kümeleri dene
    n = len(arr)
    for mask in range(1 << n):
        s = 0
        for i in range(n):
            if mask & (1 << i):
                s += arr[i]
        if s == target:
            return True
    return False
print(brute_force_subset([3, 5, 7], 10))

Kendini test et

alt küme toplam

subset_sum([3, 5, ____], 10) → True

Cevabı göster

subset_sum([3, 5, 7], 10) → True

Subset sum hangi sınıftadır?
- P
- Logaritmik
- NP-complete
- Sabit zaman
Cevabı göster

NP-complete — Subset sum NP-complete'tir.
NP-complete: kavramları eşleştir

NP-complete

Zor
brute force

2^n
subset sum

Örnek
P=NP

Açık

Sıradaki ders: Azaltma

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler