Cho hai tập hợp số, tìm tập hợp nhỏ nhất từ ​​mỗi nơi tổng bằng

Question

Tôi đang làm việc trên một ứng dụng cần khớp hai tập hợp dữ liệu dựa trên các tiêu chí khác nhau, bao gồm tổng số bất kỳ mục nào từ mỗi bộ . Tôi đã chưng cất vấn đề xuống tuyên bố này:

Cho một tập hợp các mục và giao dịch, tìm tập hợp các mục nhỏ nhất trong đó tổng bằng tổng của tập hợp giao dịch nhỏ nhất. (Có một số phức tạp tôi bỏ qua cho bài đăng này, nhưng hiện tại tôi chỉ quan tâm đến tổng số tiền phù hợp, không phải ngày tháng, mô tả, chênh lệch thanh toán bù trừ, v.v.)

Hoặc, toán học: Cho hai bộ số , tìm tập nhỏ nhất từ ​​mỗi nơi mà các khoản tiền bằng nhau.

Các câu hỏi SO tương tự khác mà tôi đã chạy qua giả sử bạn biết tổng trước hoặc biết số lượng từ mỗi tập hợp mà bạn sắp thực hiện.

Và đây là một thử nghiệm mà (tôi nghĩ) minh họa những gì tôi đang làm.

[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(); 
    } 

Tôi đang tìm kiếm một giải pháp thanh lịch mà sẽ làm cho đường chuyền này, nhưng sẽ mất bất kỳ giả hoặc gợi ý mà được tôi ở đó;)

Answer 1

lực lượng Brute:

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(); 

sử dụng Phương thức con từ EvenMoreLINQ project.

Answer 2

Nếu hai bộ chứa một số điểm chung, đó là một giải pháp kích thước 1.

Nếu không, hãy thử toàn bộ số tiền của hai số (có N-chọn-hai, hoặc N*(N-1)/2 trong mỗi bộ) . So sánh chúng với bộ sưu tập các số đơn và hai số.

Nếu không có niềm vui, hãy thử tất cả tổng của ba số, so sánh chúng với số tiền 1, 2 hoặc 3 số; và như vậy cho đến khi tất cả các khoản tiền (2 ** N cho một tập hợp kích thước N) đã được thử.

Đây là mã hoạt động ngừng tìm kiếm ngay khi tìm thấy giải pháp. (Có thể có các khoản tiền nhỏ hơn với cùng số lượng bản tóm tắt). Đó là trong python, nhưng đó là thực tế giả mã :-)

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) 

Điều này được thiết kế để tìm một giải pháp trong số lượng so sánh nhỏ nhất. Nếu bạn cũng muốn tổng là tối thiểu, sau đó tại mỗi kích thước n tạo ra tất cả các khoản tiền n-phần cùng một lúc, sắp xếp chúng và kiểm tra chúng theo thứ tự ngày càng tăng.

Answer 3

Điều này có thể được giải quyết bằng cách sử dụng lập trình động trong thời gian O(nW) khi W là kích thước của tổng lớn nhất. Giải quyết các knapsack problem cho cả hai bộ để tạo ra một mảng cho mỗi có chứa tất cả các khoản tiền có thể và theo dõi số lượng các mặt hàng được sử dụng. Sau đó, so sánh các khoản tiền bằng nhau trong mỗi mảng để tìm số tiền tối thiểu cho mỗi

Không được thử nghiệm, nhưng đây là ý tưởng.

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