4

假设我有这样的课程：

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

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

我有一个List<Work>大约 20 个值，它们都被填满了：

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

有没有什么可能的方法可以分组workToDo为每个段的时间总和是特定值的段？SayworkToDo的值如下：

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

如果我希望时间总和为 7，则每个段或List<Work>应该有一堆值，其中所有时间的总和为 7 或接近它。这甚至是遥不可及的，还是只是一个愚蠢的问题/想法？我正在使用此代码将其workToDo分成 4 段：

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

但我不知道如何根据泰晤士报来做到这一点。

4

3 回答 3

2

这是一个查询，将您的数据分组到时间接近 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）。

于 2012-10-04T04:14:53.690 回答
1

您所描述的是一个包装问题（任务被包装到 7 小时的容器中）。虽然可以在解决此问题的方法中使用 LINQ 语法，但我知道 LINQ 中没有固有的解决方案。

于 2012-10-04T02:45:40.557 回答
1

该解决方案通过所有组合递归并返回总和与目标总和足够接近的组合。

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

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);
于 2012-10-04T15:18:15.113 回答