从列表中选择项目以求和

Question

我有一个包含数值的项目列表，我需要使用这些项目求和。我需要你的帮助来构建这样的算法。下面是一个用 C# 编写的示例，描述了我的问题：

int sum = 21;

List<Item> list = new List<Item>();
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 5 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 12 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 3 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 2 });
list.Add(new Item() { Id = Guid.NewGuid(), Value = 7 });

List<Item> result = // the items in the list that has the defined sum.

注意：我对结果中的项目数量没有限制。

Answer 1

这称为子集和问题，被认为是一个难题计算机科学。并不像“难以做到”那么难，而是很难快速——你可以轻松地编写一个算法来做到这一点，但对于相当大的输入，这很容易需要数十亿年。

如果您对仅适用于小输入的缓慢解决方案感到满意，请尝试如下操作：

• 生成输入列表的所有子集。

• 对于每个子集，计算该子集中的项目总和。

• 返回总和匹配的第一个子集。

这是一个返回所有子集的方法（实际上是子序列，因为它维护项目的顺序，尽管在您的情况下这没有什么区别）：

/// <summary>
/// Returns all subsequences of the input <see cref="IEnumerable<T>"/>.
/// </summary>
/// <param name="source">The sequence of items to generate
/// subsequences of.</param>
/// <returns>A collection containing all subsequences of the input
/// <see cref="IEnumerable<T>"/>.</returns>
public static IEnumerable<IEnumerable<T>> Subsequences<T>(
        this IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");
    // Ensure that the source IEnumerable is evaluated only once
    return subsequences(source.ToArray());
}

private static IEnumerable<IEnumerable<T>> subsequences<T>(IEnumerable<T> source)
{
    if (source.Any())
    {
        foreach (var comb in subsequences(source.Skip(1)))
        {
            yield return comb;
            yield return source.Take(1).Concat(comb);
        }
    }
    else
    {
        yield return Enumerable.Empty<T>();
    }
}

所以您现在可以编写类似这样的内容...

var result = list.Subsequences()
                 .FirstOrDefault(ss => ss.Sum(item => item.Value) == sum);

Answer 2

这就是所谓的子集和问题，经过修改 - 你不想达到零，而是达到一个特定的数字。

以下是 Wiki 对此的说法 - http://en.wikipedia.org/wiki/Subset_sum_problem。

您可能会根据您对该领域的了解想到一些优化。例如，如果最大数+最小数大于总和->最高的数字永远不会被使用，你可以排除它（并尝试对新的最高数字进行相同的操作..）。

我记得按照塞缪尔的建议做了 - 递归方式，这并没有那么糟糕，（但当然总是存在 stackoverflow 问题......）。

Answer 3

递归，添加元素直到 A) 你达到总和或 B) 你得到太多，如果 A 你完成了，如果 B 你改变元素尝试所有可能的配置。如果当前元素已经大于最后一个超过总和的元素，则可能禁止系统添加元素

Answer 4

我不太确定你在这里追求的是哪一个太阳。如果您想要合并所有值的总和，请使用以下代码：

int result = list.Sum( i => i.Value);

如果您想要具有特定值的所有元素，请使用以下代码：

int x = 3;
List<Item> result = list.Where( i => i.Value == x);