7

嗨，我有一个List<decimal>]0;1] 之间的包含值。我想检查这些值的总和（或小计）是否等于 1（或几乎）。

我还可以使用Linq函数来过滤或操作列表。

期望的结果：

  • 包含 {0.7, 0.7, 0.7} 的列表应返回 false；
  • 包含 {0.7, 0.3, 0.7} 的列表应返回 true；
  • 包含 {0.777777, 0.2, 0.1} 的列表应返回 false；
  • 包含 {0.33333, 0.33333, 0.33333} 的列表应该返回 true；
  • 包含 {0.4, 0.5, 0.6, 0.3} 的列表应返回 true。

显然，我想要性能成本最低的东西。

4

5 回答 5

3

更新——现在不重复总结试试这个

bool isClose(IEnumerable<decimal> list, decimal epislon) {
  return isClose(Enumerable.Empty<decimal>(),list,0,list.Sum(),epislon);
}
// Define other methods and classes here
bool isClose(IEnumerable<decimal> left,IEnumerable<decimal> right, decimal leftSum,decimal rightSum, decimal epsilon) {
  if (leftSum>=1-epsilon && leftSum<=1+epsilon) return true;
  if (leftSum>1+epsilon) return false;
  if (leftSum+right.Sum()< 1-epsilon) return false;
  if (!right.Any()) return false;

  for (var i=0;i<right.Count();i++) {
    var skip=right.Skip(i);
    var newItem=skip.First();
    if (isClose(left.Concat(skip.Take(1)),skip.Skip(1),leftSum+newItem,rightSum-newItem,epsilon)) return true;
  }
  return false;
}



isClose(new[] {0.7m,0.7m,0.7m},0.001m); // returns false
isClose(new[] {0.7m,0.3m,0.7m},0.001m); //returns true
isClose(new[] {0.777777m,0.2m,0.1m},0.001m); //returns false
isClose(new[] {0.33333m,0.33333m,0.33333m},0.001m); //returns true

编辑第五次测试

isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true
于 2012-06-27T14:45:51.137 回答
1

这是子集和问题，是背包问题的一个特例。这很难（NP完全）。最著名的算法具有指数复杂度。然而，有多项式复杂度的近似算法。这些回答了“是否存在总和为 1±ε 的子集？”的问题。

于 2012-06-27T14:36:02.513 回答
1

这是一种相当直接、幼稚、蛮力的方法。它不会是有效的，但希望它更容易理解。

private const decimal threshold = .001M;

public static bool CloseEnough(decimal first, decimal second, decimal threshold)
{
    return Math.Abs(first - second) < threshold;
}

private static bool SubsetSum(List<decimal> data, int desiredSum)
{

    int numIteratons = (int)Math.Pow(2, data.Count);

    for (int i = 1; i < numIteratons; i++)
    {
        decimal sum = 0;
        int mask = 1;
        for (int j = 0; j < data.Count && sum < desiredSum + threshold; j++)
        {
            if ((i & mask) > 0)
            {
                sum += data[j];
            }
            mask <<= 1;
        }

        if (CloseEnough(sum, desiredSum, threshold))
        {
            return true;
        }
    }

    return false;
}
于 2012-06-27T15:03:44.217 回答
0 
public static bool SubListAddsTo(this IEnumerable<decimal> source,
  decimal target, decimal tolerance)
{
  decimal lowtarget = target - tolerance;
  decimal hightarget = target + tolerance;
  HashSet<decimal> sums = new HashSet<decimal>();
  sums.Add(0m);
  List<decimal> newSums = new List<decimal>();

  foreach(decimal item in source)
  {
    foreach(decimal oldSum in sums)
    {
      decimal sum = oldSum + item;
      if (sum < lowtarget)
      {
        newSums.Add(sum);//keep trying
      }
      else if (sum < hightarget)
      {
        return true;
      }
      //else { do nothing, discard }
    }
    foreach (decimal newSum in newSums)
    {
      sums.Add(newSum);
    }
    newSums.Clear();
  }
  return false;
}

测试者：

List<decimal> list1 = new List<decimal>(){0.7m, 0.7m, 0.7m}; 
List<decimal> list2 = new List<decimal>(){0.7m, 0.3m, 0.7m};
List<decimal> list3= new List<decimal>(){0.777777m, 0.2m, 0.1m};
List<decimal> list4 = new List<decimal>() { 0.33333m, 0.33333m, 0.33333m };
List<decimal> list5 = new List<decimal>() { 0.4m, 0.5m, 0.6m, 0.3m };

Console.WriteLine(list1.SubListAddsTo(1m, 0.001m));  //false
Console.WriteLine(list2.SubListAddsTo(1m, 0.001m));  //true
Console.WriteLine(list3.SubListAddsTo(1m, 0.001m));  //false
Console.WriteLine(list4.SubListAddsTo(1m, 0.001m));  //true
Console.WriteLine(list5.SubListAddsTo(1m, 0.001m));  //true
于 2012-06-27T14:52:05.117 回答
0

编辑：我的原始代码不允许近似值（0.9999 = 1）。

这使用变体数量的位图来掩盖源数组中的值，以强制所有变体。

在百万计数循环中对所有五个测试用例进行测试时，这比接受的答案快大约 7.5 倍（大约 41 秒对大约 5.5 秒）。它大约是 David B 的 sln 的两倍，比 Servy 的 sln 快约 15%。

    public static bool Test(decimal[] list, decimal epsilon)
    {
        var listLength = list.Length;
        var variations = (int)(Math.Pow(2, listLength) - 1);
        var bits = new bool[9];

        for (var variation = variations; variation > 0; variation--)
        {
            decimal sum = 0;

            bits[1] = (variation & 1) == 1;
            bits[2] = (variation & 2) == 2;
            bits[3] = (variation & 4) == 4;
            bits[4] = (variation & 8) == 8;
            bits[5] = (variation & 16) == 16;
            bits[6] = (variation & 32) == 32;
            bits[7] = (variation & 64) == 64;
            bits[8] = (variation & 128) == 128;

            for (var bit = listLength; bit > 0; bit--)
            {
                if (bits[bit])
                {
                    sum += list[bit - 1];
                }
            }

            if (Math.Abs(sum - 1) < epsilon)
            {
                return true;
            }
        }

        return false;
    }

编辑：这个 NewTest 版本比上述版本快 30%，比公认的解决方案快十倍以上。它消除了构建用于提供位掩码的数组，以支持 Servy 的方法，这是大部分改进的来源。它还删除了带来边际改进的 Math.Abs​​ 调用。

    private const decimal Epislon = 0.001m;
    private const decimal Upper = 1 + Epislon;
    private const decimal Lower = 1 - Epislon;

    private static bool NewTest(decimal[] list)
    {
        var listLength = list.Length;
        var variations = (int)(Math.Pow(2, listLength) - 1);

        for (var variation = variations; variation > 0; variation--)
        {
            decimal sum = 0;
            int mask = 1;

            for (var bit = listLength; bit > 0; bit--)
            {
                if ((variation & mask) == mask)
                {
                    sum += list[bit - 1];
                }
                mask <<= 1;
            }

            if (sum > Lower && sum < Upper)
            {
                return true;
            }
        }

        return false;
    }
于 2012-06-27T15:29:56.457 回答