संख्याओं के दो सेट दिए गए, प्रत्येक से सबसे छोटा सेट खोजें जहां योग बराबर है

Question

मैं ऐसे एप्लिकेशन पर काम कर रहा हूं जिसमें विभिन्न मानदंडों के आधार पर डेटा के दो सेटों से मिलान करने की आवश्यकता है, जिसमें प्रत्येक सेट से किसी भी आइटम की संख्या शामिल है । मैंने इस कथन को समस्या को दूर कर दिया है:

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

या, गणितीय रूप से: संख्याओं के दो सेट दिए गए , प्रत्येक से सबसे छोटा सेट खोजें जहां रकम बराबर हैं।

अन्य समान SO प्रश्न जो मैंने पूरे किए हैं, मानते हैं कि आप समय से पहले राशि जानते हैं, या आप जिस सेट के लिए जा रहे हैं, उससे मात्रा को जानते हैं।

और यहां एक परीक्षण है जो (मुझे लगता है) दिखाता है कि मैं क्या कर रहा हूं।

[TestMethod] 
    public void StackOverflowTest() 
    { 
     var seta = new[]{10, 20, 30, 40, 50}; 
     var setb = new[]{ 45, 45, 100, 200 }; 

     var result = Magic(seta, setb); 


     Assert.AreEqual(new[]{40,50},result.SetA); 
     Assert.AreEqual(new[] { 45, 45 }, result.SetB); 
    } 
    class MagicResult 
    { 
     public int[] SetA { get; set; } 
     public int[] SetB { get; set; } 

    } 
    private MagicResult Magic(int[] seta, int[] setb) 
    { 
     throw new NotImplementedException(); 
    } 

मैं एक सुरुचिपूर्ण समाधान है कि इस पास कर देगा, लेकिन किसी भी स्यूडोकोड या सुझाव है कि मुझे वहाँ हो जाता है ले जाएगा के लिए देख रहा हूँ;)

Answer 1

ब्रूट बल:

var result = (from a in seta.Subsets() 
       from b in setb.Subsets() 
       where a.Count() > 0 && b.Count() > 0 
       where a.Sum() == b.Sum() 
       orderby a.Count() + b.Count() 
       select new MagicResult { SetA = a.ToArray(), SetB = b.ToArray() } 
      ).First(); 

का उपयोग कर EvenMoreLINQ project से सब्सक्रिप्शन विधि।

Answer 2

दो सेट आम में एक संख्या शामिल है, वहाँ आकार 1.

यदि नहीं का एक समाधान है, दो संख्याओं का सभी राशियों की कोशिश (देखते हैं एन चयन-दो प्रत्येक सेट में, या N*(N-1)/2) । एकल संख्या और दो-संख्या के योगों के संग्रह के खिलाफ उनकी तुलना करें।

यदि कोई खुशी नहीं है, तो तीन संख्याओं की सभी रकम आज़माएं, उन्हें 1, 2 या 3-संख्या के आंकड़ों के मुकाबले तुलना करें; और तब तक सभी रकम (आकार एन के एक सेट के लिए 2 ** एन) की कोशिश की गई है।

यहां काम करने वाला कोड है जो जल्द ही समाधान ढूंढने पर खोज बंद कर देता है। (समान संख्या में सारांश के साथ छोटी रकम हो सकती है)। यह अजगर में है, लेकिन वह व्यावहारिक रूप से छद्म कोड :-)

from itertools import combinations 

# To allow lists of different sizes: ensure list1 is never the short one 
if len(list1) < len(list2): 
    list1, list2 = list2, list1 

def found(val, dict1, dict2): 
    print "Sum:", val 
    print "Sum 1", dict1[val] 
    print "Sum 2", dict2[val] 

def findsum(list1, list2): 
    # Each dict has sums as keys and lists of summands as values. 
    # We start with length 1: 
    dict1 = dict() 
    dict2 = dict() 

    for n in range(1, max(len(list1), len(list2))+1): 
     # Check all size n sums from list1 against size < n sums in list2 
     for nums in combinations(list1, n): 
      s = sum(nums) 
      if s in dict1: # Is this sum new for our list? 
       continue 

      dict1[s] = nums 
      if s in dict2: 
       found(s, dict1, dict2) 
       return # If you want to look for a smallest sum, keep going 

     # If list2 is too short, nothing to do 
     if len(list2) < n: 
      continue 

     # Check all size n sums from list2 against size <= n sums in list1 
     for nums in combinations(list2, n): 
      s = sum(nums) 
      if s in dict2: # Is this sum new for our list? 
       continue 

      dict2[s] = nums 
      if s in dict1: 
       found(s, dict1, dict2) 
       return # If you want to look for a smallest sum, keep going 

findsum(list1, list2) 

यह तुलना की सबसे छोटी संख्या में एक समाधान खोजने के लिए डिज़ाइन किया गया है है। यदि आप यह भी चाहते हैं कि राशि न्यूनतम हो, तो प्रत्येक आकार में सभी एन-पार्ट राशि एक बार में उत्पन्न करें, उन्हें क्रमबद्ध करें और उन्हें बढ़ते क्रम में जांचें।

Answer 3

इसे O(nW) समय में गतिशील प्रोग्रामिंग का उपयोग करके हल किया जा सकता है जहां डब्ल्यू सबसे बड़ा योग का आकार है। knapsack problem दोनों सेटों के लिए प्रत्येक सेट के लिए एक सरणी उत्पन्न करने के लिए हल करें जिसमें सभी संभावित रकम शामिल हैं और उपयोग की गई वस्तुओं की संख्या का ट्रैक रखें। फिर, प्रत्येक

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

arr1dp = [None]*W; arr1dp[0] = 0; 
arr2dp = [None]*W; arr2dp[0] = 0; 


# knapsack arr1 
for i in range(len(arr1)): 
    for cur_item in arr1: 
     if (arr1dp[cur_item] is not none): 
      arr1dp[cur_item+i] = min(arr1dp[cur_item]+1,arr1dp[cur_item]) 

# do the same for arr2 
# omitted for brevity 

# find the smallest match 
for i in range(W): 
    if arr1dp[i] is not none and arr2dp[i] is not none: 
     min_val = min(min_val,arr1dp[i]+arr2dp[i])