एल्गोरिथ्म एक और नंबर

Question

मैं एक दशमलव संख्या के लिए आकार n योग की सूची में से जो नंबर और अन्य दशमलव संख्या (के सरणी तत्वों कॉल) की एक सरणी (यह लक्ष्य कॉल) को खोजने के लिए और मैं की जरूरत है तत्व से संख्याओं के सभी संयोजनों को खोजने के लिए जो लक्ष्य के अनुरूप हैं।

मुझे सी # (.NET 2.0) में समाधान के लिए प्राथमिकता है लेकिन शायद सर्वश्रेष्ठ एल्गोरिदम जीत चाहे भरोसा हो।

आपका विधि हस्ताक्षर कुछ ऐसा दिखाई देगा:

public decimal[][] Solve(decimal goal, decimal[] elements) 

Answer 1

दिलचस्प जवाब। पॉइंटर्स को विकिपीडिया के लिए धन्यवाद - दिलचस्प होने पर - वे वास्तव में समस्या को हल नहीं करते हैं क्योंकि जैसा कि मैं सटीक मैचों की तलाश में था - परंपरागत बिन-पैकिंग/नापसैक समस्या की तुलना में एक लेखांकन/पुस्तक ब्लॉसिंग समस्या का अधिक।

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

public class Solver { 

    private List<List<decimal>> mResults; 

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) { 

     mResults = new List<List<decimal>>(); 
     RecursiveSolve(goal, 0.0m, 
      new List<decimal>(), new List<decimal>(elements), 0); 
     return mResults; 
    } 

    private void RecursiveSolve(decimal goal, decimal currentSum, 
     List<decimal> included, List<decimal> notIncluded, int startIndex) { 

     for (int index = startIndex; index < notIncluded.Count; index++) { 

      decimal nextValue = notIncluded[index]; 
      if (currentSum + nextValue == goal) { 
       List<decimal> newResult = new List<decimal>(included); 
       newResult.Add(nextValue); 
       mResults.Add(newResult); 
      } 
      else if (currentSum + nextValue < goal) { 
       List<decimal> nextIncluded = new List<decimal>(included); 
       nextIncluded.Add(nextValue); 
       List<decimal> nextNotIncluded = new List<decimal>(notIncluded); 
       nextNotIncluded.Remove(nextValue); 
       RecursiveSolve(goal, currentSum + nextValue, 
        nextIncluded, nextNotIncluded, startIndex++); 
      } 
     } 
    } 
} 

:

जो लोग रुचि रखते हैं के लिए, यहाँ मेरी समाधान जो प्रत्यावर्तन (स्वाभाविक रूप से) का उपयोग करता है मैं भी बल्कि [] [] वापसी प्रकार के रूप में दिया गया दशमलव से> विधि हस्ताक्षर के बारे में अपना मन बदल और सूची के लिए चला गया है

यदि आप किसी एप्लिकेशन इस काम करता है परीक्षण करना चाहते हैं, इस कंसोल अनुप्रयोग कोड का प्रयास करें:

class Program { 
    static void Main(string[] args) { 

     string input; 
     decimal goal; 
     decimal element; 

     do { 
      Console.WriteLine("Please enter the goal:"); 
      input = Console.ReadLine(); 
     } 
     while (!decimal.TryParse(input, out goal)); 

     Console.WriteLine("Please enter the elements (separated by spaces)"); 
     input = Console.ReadLine(); 
     string[] elementsText = input.Split(' '); 
     List<decimal> elementsList = new List<decimal>(); 
     foreach (string elementText in elementsText) { 
      if (decimal.TryParse(elementText, out element)) { 
       elementsList.Add(element); 
      } 
     } 

     Solver solver = new Solver(); 
     List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray()); 
     foreach(List<decimal> result in results) { 
      foreach (decimal value in result) { 
       Console.Write("{0}\t", value); 
      } 
      Console.WriteLine(); 
     } 


     Console.ReadLine(); 
    } 
} 

मुझे आशा है कि इस मदद करता है किसी और अधिक तेजी से उनके जवाब पाने (होमवर्क के लिए या अन्यथा)।

चीयर्स ...

Answer 2

मुझे लगता है कि आप अपने हाथों पर एक bin packing problem (जो एनपी कठिन है) मिल गया है, तो मुझे लगता एकमात्र समाधान की कोशिश करने का होने जा रहा है हर संभव संयोजन जब तक आप काम नहीं करते हैं।

संपादित करें: के रूप में एक टिप्पणी में कहा, आप नहीं होगा हमेशाके लिए संख्या के हर सेट आपके सामने आने वाले हर संयोजन की कोशिश करने के लिए है। हालांकि, आपके द्वारा आने वाली किसी भी विधि में संख्याओं का सबसे खराब-केस-परिदृश्य सेट है जहां आप प्रत्येक संयोजन - या कम से कम संयोजन के उप-समूह को सेट के आकार के साथ तेजी से बढ़ने के लिए प्रयास करना होगा।

अन्यथा, यह एनपी-हार्ड नहीं होगा।

Answer 3

आपने knapsack problem का वर्णन किया है, केवल एकमात्र सच्चा समाधान ब्रूट फोर्स है। कुछ सन्निकटन समाधान हैं जो तेज़ हैं, लेकिन वे आपकी आवश्यकताओं के अनुरूप नहीं हो सकते हैं।

Answer 4

सबसेट-योग समस्या, और थोड़ा अधिक सामान्य knapsack समस्या, गतिशील प्रोग्रामिंग के साथ हल हो जाती है: सभी संयोजनों के बलपूर्वक बल गणना की आवश्यकता नहीं है। विकिपीडिया या अपने पसंदीदा एल्गोरिदम संदर्भ से परामर्श लें।

हालांकि समस्याएं एनपी-पूर्ण हैं, वे बहुत ही आसान "एनपी-पूर्ण" हैं। तत्वों की संख्या में एल्गोरिदमिक जटिलता कम है।

Answer 5

जबकि जानवर बल की समस्या को हल नहीं (के रूप में दूसरों पहले ही उल्लेख किया) आप पहली बार अपने संख्या सॉर्ट करने के लिए चाहते हो सकता है, और फिर संभव छोड़ दिया लोगों पर जाने के (के बाद से एक बार आप योग मान प्रदान किया , आप लक्ष्य - योग से बड़ा कोई भी नंबर नहीं जोड़ सकते हैं)।

यह आपके एल्गोरिदम को लागू करने के तरीके को बदल देगा (केवल एक बार क्रमबद्ध करने के लिए और फिर चिह्नित तत्वों को छोड़ने के लिए), लेकिन औसत पर प्रदर्शन में सुधार होगा।

Answer 6

public class Logic1 { 
    static int val = 121; 
    public static void main(String[] args) 
    { 
     f(new int[] {1,4,5,17,16,100,100}, 0, 0, "{"); 
    } 

    static void f(int[] numbers, int index, int sum, String output) 
    { 
     System.out.println(output + " } = " + sum); 
     //System.out.println("Index value1 is "+index); 
     check (sum); 
     if (index == numbers.length) 
     { 
      System.out.println(output + " } = " + sum); 
      return; 
     } 

     // include numbers[index] 
     f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]); 
     check (sum); 
     //System.out.println("Index value2 is "+index); 
     // exclude numbers[index] 
     f(numbers, index + 1, sum, output); 
     check (sum); 
    } 

    static void check (int sum1) 
    { 
     if (sum1 == val) 
      System.exit(0); 
    } 
}