सत्यापित करें कि दशमलव मानों की कोई सूची (या उस सूची का एक उपसूची) एक निश्चित राशि

Question

के बराबर हो सकती है हाय मेरे पास List<decimal> है जिसमें 0; 1] के बीच मान हैं। मैं यह जांचना चाहता हूं कि इन मानों का कुल (या उप-योग) 1 (या लगभग) के बराबर हो सकता है या नहीं।

मैं सूची को फ़िल्टर या हेरफेर करने के लिए Linq फ़ंक्शंस का भी उपयोग कर सकता हूं।

वांछित परिणाम:

• युक्त {0.7, 0.7, 0.7} झूठे लौट जाना सूची;
• {0.7, 0.3, 0.7} वाली एक सूची सही होनी चाहिए;
• {0.777777, 0.2, 0.1} वाली एक सूची में झूठी वापसी होनी चाहिए;
• {0.33333, 0.33333, 0.33333} वाली एक सूची सही होनी चाहिए;
• {0.4, 0.5, 0.6, 0.3} वाली एक सूची सही होनी चाहिए।

जाहिर है, मुझे सबसे कम प्रदर्शन लागत के साथ कुछ चाहिए।

Answer 1

अपडेट - अब repetively नहीं जुड़ते हैं इस

bool isClose(IEnumerable<decimal> list, decimal epislon) { 
    return isClose(Enumerable.Empty<decimal>(),list,0,list.Sum(),epislon); 
} 
// Define other methods and classes here 
bool isClose(IEnumerable<decimal> left,IEnumerable<decimal> right, decimal leftSum,decimal rightSum, decimal epsilon) { 
    if (leftSum>=1-epsilon && leftSum<=1+epsilon) return true; 
    if (leftSum>1+epsilon) return false; 
    if (leftSum+right.Sum()< 1-epsilon) return false; 
    if (!right.Any()) return false; 

    for (var i=0;i<right.Count();i++) { 
    var skip=right.Skip(i); 
    var newItem=skip.First(); 
    if (isClose(left.Concat(skip.Take(1)),skip.Skip(1),leftSum+newItem,rightSum-newItem,epsilon)) return true; 
    } 
    return false; 
} 



isClose(new[] {0.7m,0.7m,0.7m},0.001m); // returns false 
isClose(new[] {0.7m,0.3m,0.7m},0.001m); //returns true 
isClose(new[] {0.777777m,0.2m,0.1m},0.001m); //returns false 
isClose(new[] {0.33333m,0.33333m,0.33333m},0.001m); //returns true 

संपादित 5 वीं टेस्ट कोशिश

isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true 

Answer 2

यह सबसेट योग समस्या है, जो knapsack समस्या का एक विशेष मामला है। यह कठिन है (एनपी-पूर्ण)। सबसे अच्छी तरह से ज्ञात एल्गोरिदम में घातीय जटिलता है। हालांकि बहुपद जटिलता के साथ अनुमानित एल्गोरिदम हैं। ये सवाल का जवाब देते हैं 'क्या एक सबसेट है जो 1 ± ε?'

• http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/nanda-scribe-3.pdf
• http://en.wikipedia.org/wiki/Subset_sum_problem
• नुथ के TAOCP (शायद)

Answer 3

public static bool SubListAddsTo(this IEnumerable<decimal> source, 
    decimal target, decimal tolerance) 
{ 
    decimal lowtarget = target - tolerance; 
    decimal hightarget = target + tolerance; 
    HashSet<decimal> sums = new HashSet<decimal>(); 
    sums.Add(0m); 
    List<decimal> newSums = new List<decimal>(); 

    foreach(decimal item in source) 
    { 
    foreach(decimal oldSum in sums) 
    { 
     decimal sum = oldSum + item; 
     if (sum < lowtarget) 
     { 
     newSums.Add(sum);//keep trying 
     } 
     else if (sum < hightarget) 
     { 
     return true; 
     } 
     //else { do nothing, discard } 
    } 
    foreach (decimal newSum in newSums) 
    { 
     sums.Add(newSum); 
    } 
    newSums.Clear(); 
    } 
    return false; 
} 

द्वारा परीक्षण किया गया:

List<decimal> list1 = new List<decimal>(){0.7m, 0.7m, 0.7m}; 
List<decimal> list2 = new List<decimal>(){0.7m, 0.3m, 0.7m}; 
List<decimal> list3= new List<decimal>(){0.777777m, 0.2m, 0.1m}; 
List<decimal> list4 = new List<decimal>() { 0.33333m, 0.33333m, 0.33333m }; 
List<decimal> list5 = new List<decimal>() { 0.4m, 0.5m, 0.6m, 0.3m }; 

Console.WriteLine(list1.SubListAddsTo(1m, 0.001m)); //false 
Console.WriteLine(list2.SubListAddsTo(1m, 0.001m)); //true 
Console.WriteLine(list3.SubListAddsTo(1m, 0.001m)); //false 
Console.WriteLine(list4.SubListAddsTo(1m, 0.001m)); //true 
Console.WriteLine(list5.SubListAddsTo(1m, 0.001m)); //true 

Answer 4

यहाँ एक नहीं बल्कि सीधा, निष्कपट, जानवर बल दृष्टिकोण है। यह कुशल नहीं होगा, लेकिन उम्मीद है कि यह समझना आसान है।

private const decimal threshold = .001M; 

public static bool CloseEnough(decimal first, decimal second, decimal threshold) 
{ 
    return Math.Abs(first - second) < threshold; 
} 

private static bool SubsetSum(List<decimal> data, int desiredSum) 
{ 

    int numIteratons = (int)Math.Pow(2, data.Count); 

    for (int i = 1; i < numIteratons; i++) 
    { 
     decimal sum = 0; 
     int mask = 1; 
     for (int j = 0; j < data.Count && sum < desiredSum + threshold; j++) 
     { 
      if ((i & mask) > 0) 
      { 
       sum += data[j]; 
      } 
      mask <<= 1; 
     } 

     if (CloseEnough(sum, desiredSum, threshold)) 
     { 
      return true; 
     } 
    } 

    return false; 
} 

Answer 5

संपादित: अपने मूल कोड सन्निकटन (0.9999 = 1) के लिए अनुमति नहीं दी।

यह सभी भिन्नताओं को बलपूर्वक बल देने के लिए स्रोत सरणी में मानों को मुखौटा करने के लिए विविधताओं की संख्या का बिटमैप उपयोग करता है।

यह दस लाख गिनती लूप (लगभग 41 सेकंड बनाम लगभग 5.5 सेकंड) में सभी पांच परीक्षण मामलों पर परीक्षण किए जाने पर स्वीकार किए गए उत्तर से 7.5 गुना तेज है। डेविड बी के स्लन के रूप में यह लगभग दोगुना तेज़ है और Servy के sln से लगभग 15% तेज है।

public static bool Test(decimal[] list, decimal epsilon) 
    { 
     var listLength = list.Length; 
     var variations = (int)(Math.Pow(2, listLength) - 1); 
     var bits = new bool[9]; 

     for (var variation = variations; variation > 0; variation--) 
     { 
      decimal sum = 0; 

      bits[1] = (variation & 1) == 1; 
      bits[2] = (variation & 2) == 2; 
      bits[3] = (variation & 4) == 4; 
      bits[4] = (variation & 8) == 8; 
      bits[5] = (variation & 16) == 16; 
      bits[6] = (variation & 32) == 32; 
      bits[7] = (variation & 64) == 64; 
      bits[8] = (variation & 128) == 128; 

      for (var bit = listLength; bit > 0; bit--) 
      { 
       if (bits[bit]) 
       { 
        sum += list[bit - 1]; 
       } 
      } 

      if (Math.Abs(sum - 1) < epsilon) 
      { 
       return true; 
      } 
     } 

     return false; 
    } 

संपादित करें: इस NewTest संस्करण 30% से अधिक संस्करण की तुलना में तेजी से होता है और कई बार दस से अधिक स्वीकार किए जाते हैं समाधान की तुलना में तेजी है। यह Servy के दृष्टिकोण के पक्ष में बिटकमास्क के साथ आने के लिए सरणी बनाने के लिए हटा देता है, जहां सुधार का बड़ा हिस्सा आता है। यह Math.Abs ​​कॉल को भी हटा देता है जो मामूली सुधार देता है।

private const decimal Epislon = 0.001m; 
    private const decimal Upper = 1 + Epislon; 
    private const decimal Lower = 1 - Epislon; 

    private static bool NewTest(decimal[] list) 
    { 
     var listLength = list.Length; 
     var variations = (int)(Math.Pow(2, listLength) - 1); 

     for (var variation = variations; variation > 0; variation--) 
     { 
      decimal sum = 0; 
      int mask = 1; 

      for (var bit = listLength; bit > 0; bit--) 
      { 
       if ((variation & mask) == mask) 
       { 
        sum += list[bit - 1]; 
       } 
       mask <<= 1; 
      } 

      if (sum > Lower && sum < Upper) 
      { 
       return true; 
      } 
     } 

     return false; 
    }