从列表中选择项目以获得总和

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&lt;T&gt;"/>.
/// </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&lt;T&gt;"/>.</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);