2

次のような整数のリストがあるとします。

List<int> items = new List<int> {200, 100, 50, 20, 10, 5, 2, 1};

そして、私が13などの数字を持っている場合、LINQを使用して（または他の方法で）13になるリストから数字を見つけるにはどうすればよいですか。リストは常に降順です。

例: 13 = 10 + 2+ 1 なので、linq 操作は 10,2 と 1 を含む整数のリストを返します。

24 の場合のように完全一致が見つからない場合は、例外が生成されても問題ありません。

努力：

  [Test]
        public void Should_find_subset()
        {
            var items = new List<int>() {200, 100, 50, 20, 10, 5, 2, 1};

            var find = 13;
            var result = new List<int>();
            var subset = new List<int>();
            bool found = false;

            foreach (var item in items)
            {
                if (item == find)
                {
                    result.Add(item);
                    found = true;
                }

                if (item < find)
                {
                    subset.Add(item);
                    found = subset.Sum() == find;
                }

                if (found)
                    break;
            }
        }

ありがとう、

-マイク

4

2 に答える 2

3

を使用した単純で非効率的なアプローチAggregate:

List<int> items = new List<int> {200, 100, 50, 20, 10, 5, 2, 1};
var target = 373;

var result = items.Aggregate(new List<int>(), (acc, curr) => 
{
    if (acc.Sum() + curr <= target)
        acc.Add(curr);
    return acc;     
});

if(result.Sum() != target)
    throw new Exception(); // whatever

結果：

ここに画像の説明を入力

このような単純なアプローチがすべてのケースで機能するとは限らないことに注意してください。例: List is 68,50,20, and target is 70. これは、50, 20 ではなくエラーになります。

そのような場合を処理する別の非効率的なアプローチ:

List<int> items = new List<int> {68, 50, 20};
var target = 70;

var result = new List<int>();
while(result.Sum() != target && items.Any())
{
    result = new List<int>();
    foreach (var item in items)
        if (result.Sum() + item <= target)
            result.Add(item);
    if(result.Sum() != target)
        items.Remove(result.Last());
}

if(result.Sum() != target)
    throw new Exception(); // whatever, no solution found

結果：

ここに画像の説明を入力

大きな入力リストを使用すると、おそらく地獄のように遅くなります。

于 2013-09-20T13:35:41.017 に答える