给定两组数字，找到使得它们中和相等的最小集合。

Question

给定两组数字，找到使得它们中和相等的最小集合。

c#algorithmset

9

我正在开发一款应用程序，需要基于各种标准（包括来自每个集合的任意数量的项目的总和）匹配两组数据。我把问题简化为以下语句：

给定一组项目和交易，找到最小的项目集，使其总和等于最小交易集的总和。（本帖子忽略了一些复杂性，但现在我只关心总金额匹配，而不是日期、描述、结算差异等）

或者，数学上：给定两个数字集合，找到每个数字集合中的最小集合，使它们的总和相等。

我看过的其他类似的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();
    }

我正在寻找一个优雅的解决方案，使其通过，但是任何伪代码或建议都可以让我达到目标 ;)

- Daniel

1

包含一个测试方法的话，加一分:D - System Down

1

如果有多个符合此条件的集合，您会怎么做？另外，您是否希望找到总和最小的最小集合？ - Abe Miessler

最后一个 :) - 一个集合中只有1个元素，这样可以吗？ - Abe Miessler

@Abe：所谓“最小的集合”，是指含有最少数量项目的集合。因此，如果有多个符合条件的集合，则应返回具有最少项目数的那一个。如果有多个匹配项，则可以只返回第一个匹配项（在实际应用中，这不太可能发生）。 - Daniel

从A和B中各选择一个1是可以接受的。从A中选择一个1和从B中选择一个0是不可以接受的。如果测试中SetA和SetB都包含“42”，那么它将返回一个结果，其中setA中有42，setB中也有42。 - Daniel

3个回答

2

这可以使用动态规划在O(nW)的时间内解决，其中W是最大和的大小。为两个集合解决背包问题，生成一个包含所有可能和并跟踪所使用项目数量的数组。然后，比较每个数组中相等的总和，找到每个总和的最小值。

尚未测试，但这就是思路。

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

- dfb

1

如果两个集合中有共同的数字，则存在大小为1的解决方案。

如果没有，尝试所有两个数字的总和（每个集合中有N-choose-two或N*(N-1)/2）。将它们与单个数字和两个数字的总和集合进行比较。

如果没有找到，尝试所有三个数字的总和，将它们与1、2或3个数字的总和进行比较；以此类推，直到尝试了所有总和（对于大小为N的集合，总和为2 ** N）。

这是一段工作代码，它在找到解决方案后立即停止搜索。（可能存在具有相同总和数的更小总和）。它是用Python编写的，但实际上就是伪代码 :-)

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部分和，对它们进行排序并按递增顺序检查。

- alexis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dtb · Accepted Answer

暴力破解：

 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项目中的Subsets方法。