2

下面是使用 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

但我想用复杂对象属性而不是 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 以获得我的结果。

4

1 回答 1

3 
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);
于 2013-03-31T11:24:53.413 回答