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

4

如果我听到组合，我建议这个项目：排列、组合和变化

这是工作代码：

List<int> items = new List<int> { 200, 100, 50, 20, 10, 5, 2, 1 };
var allMatchingCombos = new List<IList<int>>();
for (int i = 1; i < items.Count; i++)
{
    IEnumerable<IList<int>> matchingCombos = new Combinations<int>(items, i, GenerateOption.WithoutRepetition)
        .Where(c => c.Sum() == 13);
     allMatchingCombos.AddRange(matchingCombos);
}

foreach(var combo in allMatchingCombos)
   Console.WriteLine(string.Join(",", combo));

输出：10,2,1

编辑：由于您已明确要求使用 LINQ，因此这是一个完整的 LINQified 方法：

List<IList<int>> allMatchingCombos = Enumerable.Range(1, items.Count)
    .SelectMany(i => new Combinations<int>(items, i, GenerateOption.WithoutRepetition)
                    .Where(c => c.Sum() == 13)
                    .ToList())
    .ToList();
于 2013-09-20T14:14:01.363 回答
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 是 68,50,20，target 是 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 回答