查找列表中最近的sumElement组合

我在列表中找到最近的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)

得到

现在我想从listElement和中找到最接近的数字。

最接近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

因为这个跳跃对列表元素

我们可以对这个排序中的元素求和，但不能对list排序。我们不能这样做，因为这些数字是来自。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个元素。

有谁能帮我完成这件事吗?

下面代码的输出是:

Target = 50031
32183 15883 Total: 48066
26917 25459 Total: 52376
22757 25236 1657 Total: 49650

您只需要调用FindSubsetsForTotal()来接收所有子集的序列，您只需迭代即可。

代码:

using System;
using System.Collections.Generic;
namespace Demo
{
    public class Program
    {
        static void Main()
        {
            var numbers = new[] {32183, 15883, 26917, 25459, 22757, 25236, 1657};
            int target = 50031;
            foreach (var subset in FindSubsetsForTotal(numbers, target))
            {
                int subtotal = 0;
                for (int i = subset.Item1; i <= subset.Item2; ++i)
                {
                    Console.Write(numbers[i] + " ");
                    subtotal += numbers[i];
                }
                Console.WriteLine("Total: " + subtotal);
            }
        }
        public static IEnumerable<Tuple<int, int>> FindSubsetsForTotal(IList<int> numbers, int target)
        {
            int i = 0;
            while (i < numbers.Count)
            {
                int end = endIndexOfNearestSum(numbers, i, target);
                yield return new Tuple<int, int>(i, end); // The subset is from i..end inclusive. Return it.
                i = end + 1;                              // On to the next subset.
            }
        }
        static int endIndexOfNearestSum(IList<int> numbers, int start, int target)
        {
            int sumSoFar    = 0;
            int previousSum = 0;
            for (int i = start; i < numbers.Count; ++i)
            {
                sumSoFar += numbers[i];
                if (sumSoFar > target)
                {
                    if (Math.Abs(sumSoFar - target) < Math.Abs(previousSum - target))
                        return i;
                    return i - 1;
                }
                previousSum = sumSoFar;
            }
            return numbers.Count - 1;
        }
    }
}

我已经写了代码，似乎做你所描述的。我们的想法是保留一个bin，其中代码将添加连续的数字。

连续因为你说如果

我们不能加

跳过对列表元素

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

因此，如果代码决定不向bin添加数字，那么它将创建一个新的bin。现在，在任何时候最好的bin都被存储，一旦代码用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

注意:我使用天花板进行四舍五入，因为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, 50031到52376的距离为2345。因此，代码正确地判断48066更接近。

注:在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

解决方案可以是:

  class Program
  {
    static IEnumerable<int> EnumNearestSums(IList<int> list, int z)
    {
      var target = (int)(list.Sum() / (double)z + 0.5);
      var index = 0;
      for (int i = 0; i < z; i++)
      {
        var sum = 0;
        for (int j = index; j < list.Count; j++)
        {
          index++;
          var tmp = sum + list[j];
          if (tmp > target)
          {
            if (Math.Abs(target - sum) < Math.Abs(target - tmp))
            {
              index--;
            }
            else
            {
              sum = tmp;
            }
            break;
          }
          else
          {
            sum = tmp;
          }
        }
        yield return sum;
      }
    }
    static void Main(string[] args)
    {
      var list = new[] { 32183, 15883, 26917, 25459, 22757, 25236, 1657 };
      var z = 3;
      foreach (var num in EnumNearestSums(list, z))
      {
        Console.WriteLine(num);
      }
      Console.ReadLine();
    }
  }

结果:480665237649650

嗯，这是我第二次尝试。如果你想要结果最接近的和，比如

list   = {32183, 15883, 26917, 25459, 22757, 25236, 1657 ...
target = 50031
answer = {48066, 52376, 49650, ...

您可以尝试将item s求和到target，然后决定是否取 item(并返回大于target的值)或将留给item(并返回小于target的值)

private static IEnumerable<int> Approximations(IEnumerable<int> values, int target) {
  int sum = 0;
  bool first = true; // we have to take at least one item
  foreach (var item in values) {
    if (sum + item < target || first) {
      first = false;
      sum += item;
    }
    else {
      if (sum + item - target < target - sum) {
        yield return sum + item; // better to take the item
        sum = 0;
        first = true;
      }
      else {
        yield return sum; // better to leave the item
        sum = item;
      }
    }
  }
  if (first) // nothing has been taken
    yield break; 
  yield return sum;
}

测试

 List<int> list = new List<int>() { 32183, 15883, 26917, 25459, 22757, 25236, 1657 };
 int z = 3;
 int target = list.Sum() / z; // 50031
 // 48066, 52376, 49650
 string answer = string.Join(", ", Approximations(list, target));

请注意，在文件的情况下，您不需要读取整个文件(如果target不依赖于文件包含):

 var solution = Approximations(File
   .ReadLines(@"C:MyFile.txt")
   .Select(line => int.Parse(line)),
   50031);

相关内容

最新更新

热门标签：