LINQ按Sum值分组

Question

假设我有这样一个类：

public class Work
{
    public string Name;
    public double Time;

    public Work(string name, double time)
    {
        Name = name;
        Time = time;
    }
 }

我有一个包含大约20个已填充值的List<Work>：

List<Work> workToDo = new List<Work>();
// Populate workToDo

有没有可能将workToDo分组成多个片段，每个片段的时间总和为特定值？比如workToDo具有以下数值：

Name | Time
A    | 3.50
B    | 2.75
C    | 4.25
D    | 2.50
E    | 5.25
F    | 3.75

如果我想让总时间为7，每个片段或List<Work>应该有一堆值，其中所有时间的总和为7或接近7。这是否可能实现或只是一个愚蠢的问题/想法？我正在使用此代码将workToDo分成4个片段：

var query = workToDo.Select(x => x.Time)
        .Select((x, i) => new { Index = i, Value = x})
        .GroupBy(y => y.Index / 4)
        .ToList();

但我不确定如何基于Times来实现它。

- matthewr

---

可以实现，但您必须更具体地说明您想如何分组。总和离7有多接近？我们可以一直将元素包含在一个段中，直到超过7吗？段中的元素必须是连续的吗？ - Risky Martin

你是否仍希望按名称分组，但为了确保每个结果不超过7个而重复名称？ - Enigmativity

还是你想要创建一个类似这样的列表：{ A + B，C + D，E，F }？ - Enigmativity

@RiskyMartin 希望您能够指定或更改一个变量，以确定物品可以离7有多远。我猜您可以继续添加物品，直到其在边界内（例如，在7的范围内为6至8之间）。 - matthewr

Answer 1

以下是一个查询，将您的数据分组，其中时间接近7点，但不超过:

Func<List<Work>,int,int,double> sumOfRange = (list, start, end) => list
                  .Skip(start)
                  .TakeWhile ((x, index) => index <= end)
                  .ToList()
                  .Sum (l => l.Time);

double segmentSize = 7;
var result = Enumerable.Range(0, workToDo.Count ())
    .Select (index => workToDo
                         .Skip(index)
                         .TakeWhile ((x,i) => sumOfRange(workToDo, index, i) 
                                              <= segmentSize));

你的示例数据集输出结果如下：

A 3.5
B 2.75
total: 6.25

B 2.75
C 4.25
total: 7

C 4.25
D 2.5
total: 6.75

D 2.5
total: 2.5

E 5.25
total: 5.25

F 3.75
total: 3.75

如果你想允许一个段落的长度超过七个字符，那么你可以将segmentSize变量增加25%左右（即变成8.75）。

- Brad Rem

---

另外，有没有办法让结果不是一个接一个地显示？例如，一个输出可以是“D 2.5和F 3.75，总共为6.25”。 - matthewr

Answer 2

这个解决方案递归地遍历所有组合，并返回那些和接近目标和的组合。

以下是漂亮的前端方法，让您可以指定工作列表、目标总和以及和值必须接近多少：

public List<List<Work>> GetCombinations(List<Work> workList,
                                        double targetSum,
                                        double threshhold)
{
    return GetCombinations(0,
                           new List<Work>(),
                           workList,
                           targetSum - threshhold,
                           targetSum + threshhold);
}

这是一个递归方法，它完成所有工作：

private List<List<Work>> GetCombinations(double currentSum,
                                         List<Work> currentWorks,
                                         List<Work> remainingWorks,
                                         double minSum,
                                         double maxSum)
{
    // Filter out the works that would go over the maxSum.
    var newRemainingWorks = remainingWorks.Where(x => currentSum + x.Time <= maxSum)
                                          .ToList();
    // Create the possible combinations by adding each newRemainingWork to the 
    // list of current works.
    var sums = newRemainingWorks
                   .Select(x => new
                          {
                              Works = currentWorks.Concat(new [] { x }).ToList(),
                              Sum = currentSum + x.Time
                          })                                
                   .ToList();
    // The initial combinations are the possible combinations that are
    // within the sum range.                   
    var combinations = sums.Where(x => x.Sum >= minSum).Select(x => x.Works);
    // The additional combinations get determined in the recursive call.
    var newCombinations = from index in Enumerable.Range(0, sums.Count)
                          from combo in GetCombinations
                                        (
                                            sums[index].Sum,
                                            sums[index].Works,
                                            newRemainingWorks.Skip(index + 1).ToList(),
                                            minSum,
                                            maxSum
                                        )
                          select combo;
    return combinations.Concat(newCombinations).ToList();        
}

这行代码将获取总和为7 +/- 1的组合：

GetCombinations(workToDo, 7, 1);

- Risky Martin

Answer 3

您所描述的是装箱问题（即将任务装入7小时容器中）。虽然在解决此问题时可以使用LINQ语法，但我不知道LINQ本身有任何解决方案。

- Mark

---

谢谢提供链接，我不知道这个问题有一个名称。 - matthewr