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

5回目のテストを編集

isClose(new[] {0.4m, 0.5m, 0.6m, 0.3m},0.001m); //returns true
于 2012-06-27T14:45:51.137 に答える
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 に答える
1

これは部分和問題であり、ナップザック問題の特殊なケースです。難しいです（NP完全）。最もよく知られているアルゴリズムは、指数関数的な複雑さを持っています。ただし、多項式の複雑さを伴う近似アルゴリズムがあります。これらは、「合計が 1±ε になる部分集合は存在するか?」という質問に答えます。

于 2012-06-27T14:36:02.513 に答える
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) が許可されていませんでした。

これは、バリエーションの数のビットマップを使用してソース配列の値をマスクし、すべてのバリエーションをブルート フォースします。

これは、100 万回のループで 5 つのテスト ケースすべてをテストした場合、受け入れられた回答よりも約 7.5 倍高速です (約 41 秒対約 5.5 秒)。David B の sln の約 2 倍、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% 高速であり、承認されたソリューションよりも 10 倍以上高速です。ビットマスクを考え出すための配列の構築を削除し、改善の大部分がもたらされる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 に答える