在一个集合中查找一组数字,在另一个集合中添加一个数字

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-Complete,所以没有任何方法可以在合理的时间内获得100%的准确度.
• 该问题可以视为子集和或背包问题的变体.两者都有众所周知的启发式方法,可以适应这个问题.

保持想法来!再次感谢!

Answer 1

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

有关更多信息,请阅读此处:http: //en.wikipedia.org/wiki/Subset_sum_problem