4

たとえば、数値と日付の 2 つの列を持つデータ テーブルがあります。

125 | 2013/10/20
100 | 2013/10/21
150 | 2013/10/24
225 | 2013/10/24
250 | 2013/10/28
310 | 2013/10/30

ここで、数値の合計が 500 に一致する日付順のすべてのレコードを検索したいと考えています。1番目、3 番目、4 番目のレコード (125 + 150 + 225 = 500) が一致することは簡単にわかりますが、そのようなプログラムを作成するには、正しい一致が見つかるまで、データ テーブルを無数に調べることしか考えられません。

誰かがより賢いアイデアを持っていますか?

4

1 に答える 1

2

最悪の場合、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)
{
    // This stopping condition ensures that you will not have to walk the rest of the tree when you have already hit or exceeded your target.
    // It assumes that the Number values are all non-negative.
    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 の場合) はあまり良くありません ( order 2^n) が、例の場合のように、 の値のほとんどがNumber目標の合計と同程度の大きさである場合、その後、停止条件があなたの救助に飛び込み、多くの不要な操作を節約します.

于 2013-10-31T16:35:06.830 に答える