复杂类型的子集和

本文关键字：子集 类型 复杂 | 更新日期: 2023-09-27 18:06:35

下面是使用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来得到我的结果

复杂类型的子集和

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);
相关文章：