c# - 复杂类型的子集和

Question

下面是使用 LINQ 给出简单数组结果的子集求和计算。

阅读自http://algorithmicalley.com/archive/2010/05/02/the-subset-sum-problem.aspx

          List<int> list = new List<int> { 60, 45, 45, 45, 45, 30 };

           var subsets = from m in Enumerable.Range(0, 1 << list.Count)

          select

              from i in Enumerable.Range(0, list.Count)

              where (m & (1 << i)) != 0

              select list[i];

          var result=subsets.First(set => set.Sum() == 180);

这个结果给出了预期的 45,45,45,45

但我想将这个子集与 Complex Object 属性相加，而不是 int 值

        List<Group> groups = new List<Group>{new Group{Count=60},
            new Group{Count=45},new Group{Count=45},new Group{Count=45},
            new Group{Count=45},new Group{Count=30},new Group{Count=60},
            new Group{Count=60},new Group{Count=15}
        };

然后

        var subsets = from m in Enumerable.Range(0, 1 << groups.Count)

                      select

                          from i in Enumerable.Range(0, groups.Count)

                          where (m & (1 << i)) != 0

                          select groups[i];

        List<Group> subset =?????????? something like group.Count.Sum()==180

欢迎使用 LINQ 或任何实现。我不知道如何处理此 LINQ 以获得我的结果。

Answer 1

var result = subsets.First(set => set.Select(s => s.Count).Sum() == 180);

请注意，您当前的算法将产生 36 个这样的集合，总和为 180，但您只关心第一个。不确定这是不是有意为之。

此外，如果您更改原始查询以包含此约束，您最终只会迭代直到找到有效子集，而不是继续构建所有 512 个可能的子集:

var result = (from m in Enumerable.Range(0, 1 << groups.Count)
    select
    from i in Enumerable.Range(0, groups.Count)
    where (m & (1 << i)) != 0
    select groups[i])
    .First(set => set.Select(s => s.Count).Sum() == 180);