algorithm - 在一个集合中查找一组数字，这些数字加起来等于另一个集合中的数字

Question

对于我正在制作的游戏，我有一个数字列表 – 例如 [7, 4, 9, 1, 15, 2](为此命名为 A) –和另一个数字列表——比如 [11、18、14、8、3](名为 B)——提供给我。目标是找到 A 中的所有数字组合，这些组合加起来等于 B 中的数字。例如:

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

……等等。 (就此而言，1 + 2 与 2 + 1 相同。)

对于像这样的小列表，仅暴力组合是微不足道的，但我面临着看到数千到数万个这样的数字的可能性，并且将在应用程序的整个生命周期内重复使用此例程。是否有任何一种优雅的算法可以在合理的时间内以 100% 的覆盖率完成这项工作？如果做不到这一点，我是否可以找到任何一种体面的启发式方法，可以在合理的时间内为我提供一组“足够好”的组合？

我正在寻找一种用伪代码或任何相当流行和可读的语言编写的算法(注意那里的“和”……；)或者甚至只是关于如何实现这种算法的英文描述搜索。

---

编辑添加:

到目前为止提供了很多有用的信息。哥们，谢啦!现在总结一下:

• 问题是 NP 完全问题，因此除了蛮力之外别无他法，无法在合理的时间内获得 100% 的准确率。
• 这个问题可以看作是 subset sum 的变体。或 knapsack问题。这两种方法都有众所周知的启发式方法，可能适用于此问题。

让创意源源不断!再次感谢!

Answer 1

这个问题是 NP-Complete...这是子集和问题的一些变体，已知是 NP-Complete(实际上，子集和问题比你的更容易)。

阅读此处了解更多信息: http://en.wikipedia.org/wiki/Subset_sum_problem