数组算法的组合

Question

我想找一个大小为5的数组加起来为15的组合。最好的方法是什么？

假设我有一个数组

7 8 10 5 3

在C++中查找所有加起来为15的数字的最佳方法是什么

Answer 1

如果，正如你在评论中提到的，10是问题中的最大数字(也是元素的最大数量)。然后使用暴力(使用巧妙的位掩码，参见this tutorial)就可以了：

// N is the number of elements and arr is the array.
for (int i = 0; i < (1 << N); ++i) {
    int sum = 0;
    for (int j = 0; j < N; ++j) if (i & (1 << j)) sum += arr[j];
    if (sum == required_sum); // Do something with the subset represented by i.
}

该算法的复杂度为O(N * 2^N)。注意，只要N< 32，代码就是正确的。请注意，具有一定和的子集的数量可以是指数的(大于2^(N/2))。例如，{1，1，1，1，..，1}和sum = N/2。

但是，如果N很大，但N* required_sum不是很大(最大可达数百万)，则可以使用以下递归(通过动态编程或记忆)：

f(0, 0) = 1
f(0, n) = 0 where n > 0
f(k, n) = 0 where k < 0
f(k + 1, S) = f(k, S - arr[k]) + f(k, S) where k >= 0

其中f(k，S)表示获得具有元素子集0..k的和S的可能性。动态编程表可用于生成所有子集。生成表的运行时间为O(N * S)，其中S是所需的和。从表生成子集的运行时间与这样的子集的数量成比例(可能非常大)。

有关该问题的一般说明：

一般来说，问题是NP-Complete。因此，它没有已知的多项式时间算法。然而，它确实有一个pseudo-polynomial time algorithm，即上面的递归。

Answer 2

“最好的”方式取决于你在优化什么。

如果数组中的元素不多，有一个简单的组合算法:对于从1到n (其中n是数组中的元素数)的所有长度，检查所有可能的n数字集合，并打印每个集合，每个集合的总和为15。

从实现时间的角度来看，这可能是最好的。从运行时效率的角度来看，动态编程解决方案(这是DP问题)可能是最好的；这里的DP解决方案是O(N³)，其中组合解决方案远不止于此。

DP算法(我不是在写代码)的要点是遍历您的数组，并跟踪您到目前为止所看到的子数组可以进行的所有可能的求和。当您到达每个新的数组元素时，遍历您之前获得的所有部分和并将其添加到它们中(而不是删除原始的部分和)。每当有东西达到15或超过它时，丢弃你跟踪的集合中的总和(如果它恰好达到15就打印出来)。

Answer 3

我的建议是使用递归。

跟踪baseindex和currentindex，并尝试在每次递归中累加值

当累加值为15时，返回currentindex的整数值；否则，如果currentindex达到5，累加值不是15，则返回0

当return为0并且baseindex仍然小于5时，则将1添加到base index，并重置当前索引和累加值，然后再次开始递归。