एल्गोरिथ्म संख्याओं के एक समूह का चयन करने के लिए एक न्यूनतम कुल

Question

को देखते हुए संख्या n[1], n[2], n[3], .... n[x] का एक सेट और एक नंबर एम

मैं

n[a] + n[b] + n[c] + ... + n[?] >= M 

संयोजन होना चाहिए का सबसे अच्छा संयोजन को खोजने के लिए चाहते हैं तक पहुँचने के लिए किसी भी अन्य संयोजन के साथ बेहतर परिणाम देने के साथ एम तक पहुंचने या जाने के लिए आवश्यक न्यूनतम तक पहुंचें।

PHP में ऐसा कर रहा है इसलिए PHP पुस्तकालयों का उपयोग ठीक है। यदि नहीं, तो बस एक सामान्य एल्गोरिदम करेगा। धन्यवाद!

Answer 1

pseudocode: 

list<set> results; 
int m; 
list<int> a; 

// ...  

a.sort(); 

for each i in [0..a.size] 
    f(i, empty_set);  

// ... 

void f(int ind, set current_set) 
{ 
    current_set.add(a[ind]); 

    if (current_set.sum > m) 
    { 
     results.add(current_set); 
    } 
    else 
    { 
     for (int i=ind + 1; i<a.size; ++i) 
     { 
      f(i, current_set); // pass set by value 

      // if previous call reached solution, no need to continue 
      if (a[ind] + current_set.sum) > m 
       break; 
     } 
    } 
} 

// choose whatever "best" result you need from results, the one 
// with the lowest sum or lowest number of elements 

Answer 2

मुझे लगता है कि greedy algorithm दृष्टिकोण काम करेगा। सेट में आप कितने नंबरों की अपेक्षा करते हैं? यदि यह काफी कम है तो आप backtrack आज़मा सकते हैं, लेकिन मैं इसे बड़े सेट के लिए अनुशंसा नहीं करता।

Answer 3

मुझे लगता है कि यह एनपी-पूर्ण है (सामान्य में करने का तेज़ तरीका ढूंढना संभव नहीं है)। जिस तरह से आपने प्रश्न का मूल्यांकन किया है, वह मुझे लक्ष्य Subset sum problems को एक लक्ष्य पूर्णांक के साथ हल करने के बारे में सोचता है जो एम

आपके उदाहरण में, यह निर्धारित करने की कोई ज्ञात विधि नहीं है कि एम तक पहुंचा जा सकता है या नहीं। केवल एक क्रूर बल समाधान आपको बताएगा कि यह संभव नहीं है, और केवल तभी आप एम + 1 की जांच कर सकते हैं।

हालांकि, आप डीपी solution पर विचार करना चाहेंगे, क्योंकि इससे आपको कम से कम समस्या का समाधान करने के बारे में एक विचार मिलेगा (हालांकि धीरे-धीरे)। approximate समाधान भी है जो आपकी संख्या छोटी होने पर सही होगा। इसका उपयोग करें। अंत में, यह इंगित करने लायक है कि समस्या का आकार बिट्स की संख्या में मापा जाता है, न कि सेट के आकार (या योग)।

जैसा ऊपर बताया गया है, यह Knapsack problem से संबंधित है।

Answer 4

इस तरह की समस्याओं को बाइनरी linear programming (पूर्णांक रैखिक प्रोग्रामिंग का एक विशेष मामला) कहा जाता है। यह प्रसिद्ध एनपी-हार्ड है - यानी सामान्य रूप से हल करने के लिए कुशल नहीं है।

हालांकि, वाणिज्यिक और मुफ्त उपयोग दोनों, अच्छे हलकों मौजूद हैं, उदाहरण के लिए ओपन सोर्स सॉल्वर lpsolve जिसे आप अपने प्रोग्राम से कॉल कर सकते हैं।

/संपादित करें: पुराना उत्तर बंक था। मैंने कारकों को भ्रमित कर दिया। साथ output_set = शून्य

algo(input_set , target_sum, output_set) 
    if input_set is NULL 
     error "target_sum can never be reached with all input_set" 
     return 
    the_max = maximum(input_set) 
    remove the_max from input_set 
    if the_max > target_sum 
     algo(input_set, target_sum, ouptput_set) 
     return 
    add the_max to output_set 
    algo(input_set, target_sum - the_max, output_set) 

कॉल:

Answer 5

एक लालची समाधान एक छद्म काम करेगा। दक्षता के लिए सॉर्ट intput_set।

Answer 6

यह समस्या लगभग subset sum problem है, जो Knapsack समस्या से संबंधित है लेकिन अलग है, और एनपी पूर्ण है। हालांकि, एक रैखिक समाधान होता है यदि सभी संख्याएं कुछ स्थिर से छोटी हैं, और एक बहुपद समय अनुमान है। उपरोक्त संदर्भित विकिपीडिया पेज देखें।

Answer 7

यह एक क्लासिक Dynamic Programming समस्या (भी अन्य उत्तर 0-1 बस्ता और सबसेट योग समस्याओं के साथ इसकी समानता का उल्लेख द्वारा इंगित) की तरह दिखता है।पूरी चीज एक साधारण पसंद तक उबालती है: सूची में प्रत्येक तत्व के लिए, क्या हम इसे अपने योग में उपयोग करते हैं या नहीं। के बाद से इस समारोह अतिव्यापी subproblems (यह एक ही subproblems बार बार की पड़ताल), यह एक अच्छा विचार के साथ समारोह memoize है है

f(index,target_sum)= 
    0  if target_sum<=0 (i.e. we don't need to add anymore) 
    infinity if target_sum>0 and index is past the length of n (i.e. we have run out of numbers to add) 
    min(f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index]) otherwise (i.e. we explore two choices - 1. take the current number 2. skip over the current number and take their minimum) 

: हम जवाब गणना करने के लिए एक सरल पुनरावर्ती क्रिया ऊपर लिख सकते हैं पहले से गणना की गई मानों को पकड़ने के लिए एक कैश।

यहाँ अजगर में कोड है:

#! /usr/bin/env python 

INF=10**9 # a large enough number of your choice 

def min_sum(numbers,index,M, cache): 
    if M<=0: # we have reached or gone past our target, no need to add any more 
     return 0 
    elif len(numbers)==index: # we have run out of numbers, solution not possible 
     return INF 
    elif (index,M) in cache: # have been here before, just return the value we found earlier 
     return cache[(index,M)] 
    else: 
     answer=min(
      min_sum(numbers,index+1,M,cache), # skip over this value 
      min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value 
     ) 
     cache[(index,M)]=answer # store the answer so we can reuse it if needed 
     return answer 

if __name__=='__main__': 
    data=[10,6,3,100] 
    M=11 

    print min_sum(data,0,M,{}) 

यह समाधान केवल न्यूनतम राशि, न कि वास्तविक इसे बनाने के लिए इस्तेमाल किया तत्वों देता है। आप आसानी से अपने समाधान में जोड़ने के विचार को बढ़ा सकते हैं।

Answer 8

लालची समाधान काम करता है यदि प्रश्न कम से कम वस्तुओं की मांग करता है। लेकिन अधिकतम (..) फ़ंक्शन इस बात को ध्यान में रखेगा कि जब एम ऋणात्मक अधिकतम होता है तो उसे संख्या की दूरी 0 (abs() के मान को वापस करनी चाहिए)।

अधिकतम() फ़ंक्शन बाइनरी ढेर के माध्यम से कार्यान्वित किया जा सकता है। जटिलता ओ (एन। एलोग्न) है।