从列表中选择项目以达到总和

Question

从列表中选择项目以达到总和

4

我有一个包含数字值的项目列表，需要使用这些项目来实现求和。我需要您的帮助来构建这样的算法。以下是用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.

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

- Musa Hafalir

4

这是NP完全问题：它被称为子集和问题。http://en.wikipedia.org/wiki/Subset_sum_problem。不幸的是，你不会找到任何*简单*的解决方案 - 迄今为止找到的最佳解决方案运行在O(2 ^ (N/2))中。 - Ani

这些值需要是可用值中最大的吗？ - Damian Leszczyński - Vash

作业标签丢失了吗？ - Jimmy Hoffa

@Jimmy Hoffa。不，这并不是真正的作业，因为我不是学生 :) 我有一个折扣总额和订单列表。我需要在用户界面上自动检查订单以获取总和。 - Musa Hafalir

1

@Musa Hafalir，我认为您可能没有意识到一些限制，如果您真的没有任何限制，那么我们可以寻找x % item[i] == 0，然后添加此项直到我们达到该总和（x）。所以我认为您只能使用每个值一次，这是一个限制。;-) - Damian Leszczyński - Vash

显示剩余6条评论

4个回答

2

这是一个子集求和问题，与修改版的不同之处在于，您不想得到零，而是要得到一个特定的数字。

以下是维基百科对此的解释：http://en.wikipedia.org/wiki/Subset_sum_problem。

根据您了解的领域知识，您可能会想出一些优化方法。例如，如果最大数加上最小数大于总和，则永远不会使用最大数，您可以将其排除（并尝试对新的最大数进行相同的操作）。

我记得我是按照Samuel建议的方式进行的——递归方式，并没有那么可怕，但是当然有stackoverflow的问题...

- Oren A

1

递归，添加元素直到A）达到总和或B）超过总和，如果是A，则完成，如果是B，则更改元素并尝试所有可能的配置。也许禁止系统在当前元素已经大于超过总和的最后一个元素时添加元素。

- Samuel

-1

我不确定你想要哪个“sun”。如果你想要所有值的总和，可以使用以下代码：

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

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

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

- Øyvind Bråthen

应该是 list.Where(i => i.Value == x);（双等号表示相等）。 - Benny Jobigan

@Benny Jobigan，但是这根本不是提问者想要的。 - colithium

抱歉这里拼错了，我已经修正了。 - Øyvind Bråthen

@colithium 是的，我现在明白解决方案是不同的。很难理解OP想要什么。无论如何，我只是指出了代码中的一个拼写错误（尽管我怀疑那个代码是否能编译）。 - Benny Jobigan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timwi · Accepted Answer

这被称为子集和问题，在计算机科学中被认为是一个难题。不是难以完成，而是难以快速完成——你可以轻松编写一个算法来解决它，但对于大规模的输入，它将需要数十亿年的时间。

如果您满意一个只适用于小输入的缓慢解决方案，请尝试以下方法：

- 生成输入列表的所有子集。 - 对于每个子集，计算该子集中项目的总和。 - 返回第一个总和匹配的子集。

这里是一种返回所有子集的方法（实际上是子序列，因为它保持了项目的顺序，尽管在您的情况下这没有区别）：

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