एन पूर्णांक के सेट को देखते हुए, sum> = k

Question

सरणी के साथ सभी संभावित सबसेट्स को सूचीबद्ध करें, सरणी के रूप में पूर्णांक के एक अनुरक्षित सेट को देखते हुए, सभी संभावित सबसेट ढूंढें जिनकी राशि किसी कॉन्स इंटीजर के से अधिक या बराबर है, उदा। : - हमारे सेट {1,2,3} है और कश्मीर = 2

संभव सबसेट: -

{2}, 
{3}, 
{1,2}, 
{1,3}, 
{2,3}, 
{1,2,3} 

मैं केवल एक अनुभवहीन एल्गोरिथ्म जो सेट के सभी उप-समूहों और जांच करता है कि योग को सूचीबद्ध करता है के बारे में सोच सकते हैं सबसेट का है> = के या नहीं, लेकिन इसका एक घातीय एल्गोरिदम और सभी सबसेट्स को सूचीबद्ध करने के लिए ओ (2^एन) की आवश्यकता होती है। क्या मैं इसे बहुपद समय में हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग कर सकता हूं?

Answer 1

लिस्टिंग सभी सबसेट अभी भी O(2^N) होने जा रहे हैं क्योंकि सबसे बुरे मामले में आपको अभी भी खाली सब के अलावा सभी सबसेट सूचीबद्ध करना पड़ सकता है।

गतिशील प्रोग्रामिंग आप सेट है कि sum >= K

आप नीचे से ऊपर जाने कितने सबसेट सीमा [1..K] से कुछ मूल्य को अभिव्यक्त का ट्रैक रखने की संख्या की गणना कर सकते हैं। इस तरह का एक दृष्टिकोण O(N*K) होगा जो छोटे K के लिए केवल व्यवहार्य होगा।

गतिशील प्रोग्रामिंग समाधान के साथ विचार एक उदाहरण के साथ सबसे अच्छा चित्रित किया गया है। इस स्थिति पर विचार करें। मान लें कि पहले i तत्वों से बना सभी सेटों में से आप जानते हैं कि t12 और t2 योग 3 पर योग है। मान लें कि अगला i+1 तत्व 4 है। सभी मौजूदा सेटों को देखते हुए हम तत्व i+1 तत्व को जोड़कर या इसे छोड़कर सभी नए सेट बना सकते हैं। अगर हम इसे छोड़ देते हैं तो हमें t1 सबसेट मिलते हैं जो 2 और t2 सबसेट्स को 3 पर मिलता है। अगर हम इसे जोड़ते हैं तो हम t1 सबसेट प्राप्त करते हैं जो 6 (2 + 4) और t2 पर है जो 7 (3 + 4) के बराबर है। इससे हमें उन सबसेट्स की संख्या मिलती है जो (2,3,6,7) पर हैं जो पहले i+1 तत्वों से मिलती हैं। हम N तक जारी रखते हैं।

छद्म कोड में यह कुछ इस तरह दिखाई दे सकता है:

int DP[N][K]; 
int set[N]; 

//go through all elements in the set by index 
for i in range[0..N-1] 
    //count the one element subset consisting only of set[i] 
    DP[i][set[i]] = 1 

    if (i == 0) continue; 

    //case 1. build and count all subsets that don't contain element set[i] 
    for k in range[1..K-1] 
     DP[i][k] += DP[i-1][k] 

    //case 2. build and count subsets that contain element set[i] 
    for k in range[0..K-1] 
     if k + set[i] >= K then break inner loop      
     DP[i][k+set[i]] += DP[i-1][k] 

//result is the number of all subsets - number of subsets with sum < K 
//the -1 is for the empty subset 
return 2^N - sum(DP[N-1][1..K-1]) - 1 

Answer 2

क्या मैं इसे बहुपद समय में हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग कर सकता हूं?

नहीं। समस्या @amit (टिप्पणियों में) उल्लेखों से भी कठिन है। यह पता लगाना कि कोई सबसेट मौजूद है जो एक विशिष्ट के लिए है subset-sum problem है, जो एनपी-हार्ड है। इसके बजाय आप के लिए पूछ रहे हैं कि कितने समाधान एक विशिष्ट के बराबर हैं, जो P# की अधिक कठिन कक्षा में है। इसके अतिरिक्त, आपकी सटीक समस्या थोड़ा अधिक कठिन है क्योंकि आप न केवल गिनना चाहते हैं, बल्कि के लिए सभी संभव सबसेट्स और लक्ष्य < के लिए गणना करें।

Answer 3

यदि के 0 है, और सेट का प्रत्येक तत्व सकारात्मक है तो आपके पास प्रत्येक संभावित सबसेट आउटपुट करने के अलावा कोई विकल्प नहीं है, इसलिए इस समस्या के निचले बाध्य ओ (2 ^एन) - समय लिया गया है उत्पादन का उत्पादन करने के लिए।

जब तक आप उस मूल्य के बारे में कुछ और नहीं जानते जिसे आपने हमें नहीं बताया है, तो कोई भी सामान्य सामान्य समाधान नहीं है कि प्रत्येक सबसेट की जांच करें।