代码之家 › 专栏 › 技术社区 › Musa Hafalir

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

combinations list algorithm .net c#

4

Musa Hafalir · 技术社区 · 15 年前

我有一个项目清单,其中有数值,我需要实现一个总和使用这些项目。我需要你的帮助来建立这样一个算法。下面是一个用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.

注意:我对结果中的项数没有限制。

4 回复 | 直到 15 年前

1

7

Timwi 15 年前

这就是所谓的 Subset sum problem

如果您对只适用于小输入的缓慢解决方案感到满意,请尝试以下方法:

生成输入列表的所有子集。
返回和匹配的第一个子集。

下面是一个返回所有子集的方法(实际上

/// <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);

2

Oren A 15 年前

这就是所谓的子集和问题,修改了-你不想得到零,而是一个特定的数字。

http://en.wikipedia.org/wiki/Subset_sum_problem .

你可以根据你对这个领域的知识来考虑一些优化。例如,如果最高的数字+最低的数字大于总和->最高的数字将永远不会被使用,您可以排除它(并对新的最高数字尝试相同的方法…)。

3

1

Samuel 15 年前

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

4

-1

Øyvind Bråthen 15 年前

我不太清楚你在找哪个太阳。如果要合并所有值的总和,请使用以下代码:

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

如果希望所有元素都具有特定值,请使用以下代码:

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