给定两组数字,找到总和相等的每一组的最小集合

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