給定兩組數字，找出總和相等的最小集合

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*(N-1)/2每組） 。將它們與單個號碼和兩個號碼彙總進行比較。

如果沒有快樂，嘗試所有三個數字的總和，比較它們與1,2或3個數字的總和;依此類推，直到嘗試所有和（2 ** N爲一組大小）爲止。

這是工作代碼，只要找到解決方案就會停止搜索。 （可能有更少的和數和相同數目的和）。它在蟒蛇，但是這實際上是僞代碼:-)

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) 

這樣設計是爲了找到比較的最小數量的解決方案。如果你還希望這個總和最小，那麼在每一個規模n上一次生成所有的n部分總和，然後按照遞增順序對它們進行排序。

Answer 3

這可以使用動態編程在O(nW)時間解決，其中W是最大和的大小。解決這兩個集合的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])