我有一个包含数值的项目列表,我需要使用这些项目求和。我需要你的帮助来构建这样的算法。下面是一个用 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.
注意:我对结果中的项目数量没有限制。
这被称为子集和问题 http://en.wikipedia.org/wiki/Subset_sum_problem并被认为是计算机科学中的一个难题。不是很难做,而是很难做fast——你可以轻松地编写一个算法来做到这一点,但对于相当大的输入,这很容易需要数十亿年。
如果您对仅适用于小输入的缓慢解决方案感到满意,请尝试以下操作:
生成输入列表的所有子集。
对于每个子集,计算该子集中项目的总和。
返回总和匹配的第一个子集。
这是一个返回所有子集的方法(实际上子序列因为它保持了项目的顺序,尽管在您的情况下这没有什么区别):
/// <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);
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)