在最坏的情况下,您确实需要遍历数据集的所有2^n个子集,但如果您的所有项都是非负数,则可以从过滤掉“item.Number <= 500”开始。
这里是一个可能的“Subsets”方法(实际上是
如何获取数组的所有子集?的答案,但不要告诉他们):
public static IEnumerable<IEnumerable<T>> Subsets(this IEnumerable<T> source)
{
var first = source.FirstOrDefault();
if (first == null) return new[] { Enumerable.Empty<T>() };
var others = source.Skip(1).Subsets();
return others.Concat(others.Select(s => s.Concat(new { first })));
}
一旦你有了
Subsets
方法,你可以按以下方式过滤结果,尽管性能仍然是数量级为亿万(或者如果你想挑剔的话,是
2^n
)。
var sets = items.Where(i => i.Number <= 500)
.Subsets().Where(s => s.Sum(i => i.Number) == 500);
然而,如果您对“Number”有非负的限制,您可以将“Subsets”操作与搜索目标和结合起来。这意味着您需要定义:
public static IEnumerable<IEnumerable<T>> SubsetsAddingUpTo(this IEnumerable<T> source, int target)
{
if (target < 0) return Enumerable.Empty<IEnumerable<T>>();
var first = source.FirstOrDefault();
if (first == null) return Enumerable.Empty<IEnumerable<T>>();
var tail = source.Skip(1).Where(i => i.Number <= target).ToList();
var othersIncludingFirst = tail.SubsetsAddingUpTo(target - first.Number);
var othersExcludingFirst = tail.SubsetsAddingUpTo(target);
return othersExcludingFirst.Concat(othersIncludingFirst.Select(s => s.Concat(new { first })));
}
因为方法内部会检查 "
<= target
",所以你不需要进行任何预过滤。但是,在搜索之前可以对数据进行排序,以按照日期层次顺序给出结果集。调用方式如下:
var sets = items.OrderByDescending(i => i.Date).SubsetsAddingUpTo(500);
这实际上应该给你相当不错的性能。最坏情况(每个项目的数字为0或1)不会很好(顺序
2^n
),但是如果大多数
Number
的值与您的目标总和具有类似的数量级,就像您的示例一样,那么停止条件将挺身而出,为您节省大量不必要的操作。