在列表中查找最接近的sumElement组合

Question

我在列表中找到最接近的sumElement组合时遇到了一些问题.

例:

这是我的清单:

 list = {32183,15883,26917,25459,22757,25236,1657}
 list.Sum = 150092

而现在我正在分裂

 list.Sum / z
 z = variable(user Input - in this example it's 3)

我明白了

50031

现在我想从listElement summs中找到最接近的数字.

最接近50031是

 32183 + 15883 = 48066
       or
 32183 + 15883 + 26917 = 74983

所以我选择48066,接下来我想找到下一个元素,但我们必须跳过已计数的元素(在这种情况下我必须跳过32183 + 15883)

所以现在我们只能使用这些元素26917,25459,22757,25236,1657(尚未计算)

  26917 + 25459 = 52376
        or
  26917 + 25459 + 22757 = 75133

所以我选择了52376

我们这样做z(变量)次

我们可以按此顺序对元素求和,我们无法添加

 32183 + 15883 + 1657

因为这个跳过夫妇列出元素

我们可以对这种元素求和,我们不能对列表进行排序. 我们不能这样做,因为这些数字是来自.csv文件的行数,所以我必须按此顺序执行.

现在我有:

for (int i = 0; i < z; i++)
{
    mid = suma/z ;

    najbli?szy = listSum.Aggregate((x, y) => Math.Abs(x - mid) < Math.Abs(y - mid) ? x : y);
}

它找到了第一个元素(正确),但我不知道如何正确循环它.所以我只得到第一个元素,在这个例子中我需要3个.

任何人都可以帮我完成这个吗？

Answer 1

我编写的代码似乎可以实现您所描述的功能。这个想法是保留bin代码将添加连续数字的位置。

连续的，因为你说我们不能添加，如果我们

跳过几个列表元素

现在，当决定添加到 时bin，如果 的总和bin小于目标值，它总是会尝试这样做。并且仅当添加新值使总数更接近目标值时才会添加。如果不满足这些条件，则该数字将不会添加到bin.

因此，如果代码决定不向 中添加数字bin，那么它将创建一个新的bin. 现在，始终存储迄今为止最好的代码bin，一旦使用 a 完成代码bin，它就会将其与该代码进行比较，如果更好，则替换它，如果不只是丢弃当前代码bin并重新开始。

这些是我的参数：

var list = new List<int>{32183,15883,26917,25459,22757,25236,1657};
var sum = list.Sum();
var z = 3; // user input
var mid = (int)Math.Ceiling(sum / (double)z); // cutout point

注意：我使用 Ceiling 进行舍入，因为sum(150092) 除以 3 是 50030.666666...

var bin = new List<int>();
var binTotal = 0;
var bestBin = bin;
var bestBinTotal = binTotal;
var candidatesCount = 0;

for(var index = 0; index < list.Count; index++)
{
    var current = list[index];
    var keep =
        (
            // The total of the bin is yet to reach the cutout point
            binTotal < mid
            // And adding the current will make it clouser
            && Math.Abs(mid - (binTotal + current)) < Math.Abs(mid - binTotal)
        )
        // but if this is the last candidate, screw that and add anyway
        || candidatesCount == (z - 1);
    if (keep)
    {
        bin.Add(current);
        binTotal += current;
    }
    else
    {
        candidatesCount++;
        if (Math.Abs(mid - binTotal) < Math.Abs(mid - bestBinTotal))
        {
            bestBin = bin;
            bestBinTotal = binTotal;
        }
        bin = new List<int>{current}; // because we didn't add it
        binTotal = current;
    }
}

Console.WriteLine("Result: {"+ string.Join(", ", bestBin) +"}; Total: " + bestBinTotal);

输出是Result: {32183, 15883}; Total: 48066

我们可以看到 到 的距离48066是50031，而到的1965距离是。所以代码正确地决定了更接近。5003152376234548066

注意：在 LinqPad 上测试。

事实上，这些垃圾箱仅用于存储选定的值，因此如果您不需要，可以将其删除。如果您想要的是所有候选人，您可以按如下方式修改代码：

var candidates = new List<int>();
var binTotal = 0;
var bestBinTotal = binTotal;

for(var index = 0; index < list.Count; index++)
{
    var current = list[index];
    var keep =
        (
            // The total of the bin is yet to reach the cutout point
            binTotal < mid
            // And adding the current will make it clouser
            && Math.Abs(mid - (binTotal + current)) < Math.Abs(mid - binTotal)
        )
        // but if this is the last candidate, screw that and add anyway
        || candidates.Count == (z - 1);
    if (keep)
    {
        binTotal += current;
    }
    else
    {
        candidates.Add(binTotal);
        if (Math.Abs(mid - binTotal) < Math.Abs(mid - bestBinTotal))
        {
            bestBinTotal = binTotal;
        }
        binTotal = current; // because we didn't add it
    }
}

// Fix to add the final candidate:

candidates.Add(binTotal);

Console.WriteLine("Result: {"+ string.Join(", ", candidates) +"}; Best: " + bestBinTotal);

输出是Result: {48066, 52376, 49650}; Best: 48066