두 세트의 숫자가 주어진 경우 합계가 같은 위치에서 가장 작은 세트를 찾으십시오.

Question

각 세트의 항목 수의 합계를 포함하여 다양한 기준에 따라 두 세트의 데이터를 일치시켜야하는 응용 프로그램을 작성 중입니다. . 나는 문을 아래로 문제를 증류했습니다 :

주어진 항목 및 거래, 합계가 거래의 가장 작은 집합의 합계와 같은 항목의 가장 작은 세트를 찾으십시오. (이 게시물에 대해서는 약간의 복잡성이 있지만, 지금은 날짜, 설명, 삭제 차이 등이 아닌 총 금액 일치에만 관심이 있습니다)

또는 수학적으로 두 세트의 숫자가 주어 졌을 때 , 합계가 같은 위치에서 가장 작은 세트를 찾으십시오.

다른 비슷한 질문은 이전에 합계를 알고 있다고 가정합니다. 또는 각 세트의 양을 알고 있다고 가정합니다.

그리고 여기에 내가하려는 일이 설명되어있는 테스트가 있습니다. 나는이 패스를 만들 것이다, 그러나 어떤 의사 또는이 저를 얻는다 제안을합니다 우아한 솔루션을 찾고 있어요

[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를) . 단일 숫자 및 두 숫자 합계와 비교하십시오.

기쁨이 없다면 3 개의 숫자를 모두 합하여 1,2 또는 3 개의 숫자 합계와 비교해보십시오. 크기 N의 집합에 대한 모든 합계 (2 ** N)가 시도 될 때까지 계속됩니다.

해결책을 찾자 마자 검색을 중지하는 작동 코드가 있습니다. (동일한 수의 summand를 가진 더 작은 합계가있을 수 있습니다). 그것은 파이썬에서, 그러나 그 이는 비교의 가장 작은 수의 해결책을 찾기 위해 설계되었습니다

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])