algorithm - 对数组值求和，总和等于 X

Question

我有一个整数集合。我需要得到值总和等于 X 的所有可能性。

我需要这样的东西。

可以写成：delphi、c#、php、RoR、python、cobol、vb、vb.net

Answer 1

这是一个子集和问题。它是NP-Complete。

实现这一点的唯一方法是生成所有可能的组合并比较总和值。虽然存在优化技术。

这是 C# 中的一个：

static class Program
{
    static int TargetSum = 10;
    static int[] InputData = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    static void Main()
    {
        // find all permutations
        var permutations = Permute(InputData);

        // check each permutation for the sum
        foreach (var item in permutations) {

            if (item.Sum() == TargetSum) {

                Console.Write(string.Join(" + ", item.Select(n => n.ToString()).ToArray()));
                Console.Write(" = " + TargetSum.ToString());
                Console.WriteLine();

            }
        }

        Console.ReadKey();
    }

    static IEnumerable<int[]> Permute(int[] data) { return Permute(data, 0); }

    static IEnumerable<int[]> Permute(int[] data, int level)
    {
        // reached the edge yet? backtrack one step if so.
        if (level >= data.Length) yield break;

        // yield the first #level elements
        yield return data.Take(level + 1).ToArray();

        // permute the remaining elements
        for (int i = level + 1; i < data.Length; i++) {
            var temp = data[level];
            data[level] = data[i];
            data[i] = temp;

            foreach (var item in Permute(data, level + 1))
                yield return item;

            temp = data[i];
            data[i] = data[level];
            data[level] = temp;
        }

    }
}

Answer 2

动态编程将为精确解决方案产生最佳运行时间。Wikipedia 上的 Subset Sum Problem 页面有一些算法的伪代码。本质上，您订购所有数字并将所有可能的序列相加，以便最大限度地减少加法的数量。运行时是伪多项式。

对于多项式算法，您可以使用Approximation Algorithm。伪代码也可在子集求和问题页面上找到。

在这两种算法中，我会选择动态编程一种，因为它很简单，并且对大多数数据集都有很好的运行时间。

但是，如果整数都是非负数并且符合维基百科页面上的描述，那么您实际上可以使用近似算法在多项式时间内完成此操作。