按“等和”分组

Question

我试着取一个数字列表，把它们分成>=n组，这样每组的和近似相等（但不一定完全相等），并且“离群值”可以在它们自己的一组中。

因此，对于一个由3个组组成的目标和一个类似于以下内容的输入：

[3, 2, 1, 4, 2, 5]

输出可能是：

[[5,1], [4,2], [3,2]]

6, 6, 5

我想我已经把方法学弄清楚了，作为伪代码，它看起来像这样：

let target = Ceil(Sum(Series) / NumberOfTargetGroups) //The ideal size of each group

while (count(UnpickedNumbers) > 0)
    let CurrentGroup = new group
    while (sum(CurrentGroup) < target)
        for each Unpicked in sortDesc(UnpickedNumbers)
            if (sum(CurrentGroup) + Unpicked)
                Add Unpicked to current group
                Remove unpicked from available numbers

我搞不懂的是，如何将该逻辑转换为groupby(n=>...)-之所以要这样做，是因为数字列表实际上来自一系列对象的属性，我希望以这种方式对这些对象进行分组。

Answer 1

划分是NP完全问题。我已经预先说明了代码段：

public IEnumerable<IEnumerable<TObject>> Algo<TObject>(IEnumerable<TObject> source, int groups,
                                                       Func<TObject, int> intSelector)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }

    source = source.OrderByDescending(intSelector);
    var evaluated = source as IList<TObject> ?? source.ToList();
    if (groups > evaluated.Count())
    {
        throw new ArgumentException("Invalid group count.");
    }

    var result = new List<List<TObject>>();
    for (var i = 0; i < groups; i++)
    {
        result.Add(new List<TObject> { evaluated[i] });
    }

    for (var i = groups; i < evaluated.Count(); i++)
    {
        var bestIndex = 0;
        var bestSum = result[bestIndex].Sum(intSelector);
        for (var j = 1; j < result.Count; j++)
        {
            var sum = result[j].Sum(intSelector);
            if (sum < bestSum)
            {
                bestSum = sum;
                bestIndex = j;
            }
        }

        result[bestIndex].Add(evaluated[i]);
    }

    return result;
}

它的效率不高（有很多方法可以优化它），结果也不总是最优的。但希望它将是您的算法的基础（也许大约对您来说就足够了-测试它！）。

编辑：我已为您修改了代码段-您不必使用groupby。用法：

var widgets = new List<Widget>  { W1, W2, etc. };
var result = Algo(widgets, groups: 3, intSelector: widget => widget.Height);