एक संग्रह में संख्याओं का सेट ढूंढें जो किसी अन्य संख्या में

Question

एक गेम के लिए मैं एक ऐसी स्थिति कर रहा हूं जहां मेरे पास – नंबरों की सूची है [7, 4, 9, 1, 15, 2 ] (इस के लिए A नाम दिया गया) – और संख्याओं की एक और सूची – कहें [11, 18, 14, 8, 3] (नाम B) – मुझे प्रदान किया गया। लक्ष्य A में संख्याओं के सभी संयोजनों को ढूंढना है जो B में किसी संख्या तक जोड़ते हैं।

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14: उदाहरण के लिए
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

... और इतने पर। (इस के प्रयोजनों के लिए, 1 + 22 + 1 के समान है।)

इस तरह छोटे सूचियों के लिए, यह सिर्फ करने के लिए तुच्छ है, संयोजन जानवर-बल, लेकिन मैं इन हजारों की संख्या में करने के लिए हजारों देखकर की संभावना का सामना करना पड़ रहा है संख्याएं और एप्लिकेशन के जीवनकाल में इस दिनचर्या का बार-बार उपयोग करेंगे। क्या 100% कवरेज के साथ उचित समय में इसे पूरा करने के लिए कोई भी सुरुचिपूर्ण एल्गोरिदम उपलब्ध है? यह असफल रहा, क्या कोई सभ्य हेरिस्टिक है जो मुझे मिल सकता है जो मुझे उचित समय में संयोजनों का "अच्छा पर्याप्त" सेट दे सकता है?

मैं छद्म कोड में या किसी भी साधारण रूप से लोकप्रिय और पठनीय भाषा में एक एल्गोरिदम की तलाश में हूं ("और" वहां ....;) या यहां तक ​​कि केवल एक अंग्रेजी विवरण भी है कि यह कैसे कार्यान्वित करने के बारे में होगा तरह की खोज जोड़ने के लिए

---

संपादित:

अब तक प्रदान की अच्छी जानकारी के बहुत सारे। धन्यवाद भाई! अब के लिए संक्षेप में:

• समस्या एनपी-पूर्ण है इसलिए उचित समय में 100% सटीकता प्राप्त करने के लिए ब्रूट फोर्स से कम कोई रास्ता नहीं है।
• समस्या को subset sum या knapsack समस्याओं के रूप में देखा जा सकता है। दोनों के लिए प्रसिद्ध हेरिस्टिक हैं जो इस समस्या के अनुकूल हो सकते हैं।

विचारों को आते रहें! और फिर धन्यवाद!

Answer 1

यह समस्या एनपी-पूर्ण है ... यह उप-सेट योग समस्या का कुछ भिन्नता है जिसे एनपी-पूर्ण (वास्तव में, उप-सेट योग समस्या आपके से आसान है))।

अधिक जानकारी के लिए पढ़ें: http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

नेप्सेक समस्या (http://en.wikipedia.org/wiki/Knapsack_problem देखने की तरह लगता है। उस पृष्ठ पर वे भी समझाने समस्या सामान्य रूप में एनपी पूरा हो गया है कि।

मुझे लगता है कि इसका मतलब है कि अगर आप सभी मान्य संयोजनों खोजना चाहते हैं, तो आप सिर्फ जरूरत है बहुत समय।

Answer 3

यह subset sum problem का एक छोटा सा सामान्यीकरण है। आम तौर पर, यह एनपी-पूर्ण होता है, लेकिन जब तक सभी संख्याएं पूर्णांक होती हैं और B में अधिकतम संख्या अपेक्षाकृत छोटी होती है, तो विकिपीडिया लेख में वर्णित छद्म-बहुपद समाधान को चाल चलनी चाहिए।

Answer 4

जैसा कि 1 से 30 तक की संख्या के साथ टिप्पणियों में कहा गया है, समस्या का तेज़ समाधान है। मैंने इसे सी में परीक्षण किया और आपके दिए गए उदाहरण के लिए इसे केवल मिलीसेकंड की आवश्यकता है और यह बहुत अच्छी तरह से स्केल करेगा। जटिलता ओ (एन + के) है जहां एन सूची A की सूची है और के B की लंबाई की लंबाई है, लेकिन उच्च स्थिर कारक के साथ (28 से 9 8 संभावनाएं 1 से 30 तक प्राप्त करने के लिए हैं)।

#define WIDTH 30000 
#define MAXNUMBER 30 

int create_combination(unsigned char comb[WIDTH][MAXNUMBER+1], 
         int n, 
         unsigned char i, 
         unsigned char len, 
         unsigned char min, 
         unsigned char sum) { 
    unsigned char j; 

    if (len == 1) { 
     if (n+1>=WIDTH) { 
      printf("not enough space!\n"); 
      exit(-1); 
     } 
     comb[n][i] = sum; 
     for (j=0; j<=i; j++) 
      comb[n+1][j] = comb[n][j]; 
     n++; 
     return n; 
    } 

    for (j=min; j<=sum/len; j++) { 
     comb[n][i] = j; 
     n = create_combination(comb, n, i+1, len-1, j, sum-j); 
    } 

    return n; 
} 

---

int main(void) 
{ 
    unsigned char A[6] = { 7, 4, 9, 1, 15, 2 }; 
    unsigned char B[5] = { 11, 18, 14, 8, 3 }; 

    unsigned char combinations[WIDTH][MAXNUMBER+1]; 
    unsigned char needed[WIDTH][MAXNUMBER]; 
    unsigned char numbers[MAXNUMBER]; 
    unsigned char sums[MAXNUMBER]; 
    unsigned char i, j, k; 
    int n=0, m; 

    memset(combinations, 0, sizeof combinations); 
    memset(needed, 0, sizeof needed); 
    memset(numbers, 0, sizeof numbers); 
    memset(sums, 0, sizeof sums); 

    // create array with all possible combinations 
    // combinations[n][0] stores the sum 
    for (i=2; i<=MAXNUMBER; i++) { 
     for (j=2; j<=i; j++) { 
      for (k=1; k<=MAXNUMBER; k++) 
       combinations[n][k] = 0; 
      combinations[n][0] = i; 
      n = create_combination(combinations, n, 1, j, 1, i); 
     } 
    } 

    // count quantity of any summands in each combination 
    for (m=0; m<n; m++) 
     for (i=1; i<=MAXNUMBER && combinations[m][i] != 0; i++) 
      needed[m][combinations[m][i]-1]++; 

    // count quantity of any number in A 
    for (m=0; m<6; m++) 
     if (numbers[A[m]-1] < MAXNUMBER) 
      numbers[A[m]-1]++; 

    // collect possible sums from B 
    for (m=0; m<5; m++) 
     sums[B[m]-1] = 1; 

    for (m=0; m<n; m++) { 
     // check if sum is in B 
     if (sums[combinations[m][0]-1] == 0) 
      continue; 

     // check if enough summands from current combination are in A 
     for (i=0; i<MAXNUMBER; i++) { 
      if (numbers[i] < needed[m][i]) 
       break; 
     } 

     if (i<MAXNUMBER) 
      continue; 

     // output result 
     for (j=1; j<=MAXNUMBER && combinations[m][j] != 0; j++) { 
      printf(" %s %d", j>1 ? "+" : "", combinations[m][j]); 
     } 
     printf(" = %d\n", combinations[m][0]); 
    } 

    return 0; 
} 

---

1 + 2 = 3 
1 + 7 = 8 
2 + 9 = 11 
4 + 7 = 11 
1 + 4 + 9 = 14 
1 + 2 + 4 + 7 = 14 
1 + 2 + 15 = 18 
2 + 7 + 9 = 18