编写一个算法来决定是否可以使用一组其他数字和特定运算符来达到目标​​数量？

Question

我正在努力学习更多有关算法设计的知识,并且我已经为自己设定了一个挑战,即创建一个简单的游戏,向用户展示一系列数字,目标数字和一系列运算符(加,减,乘,除,也许是平方根等等).我需要做的是决定是否可以使用数组中的可用数字来制作目标数字.

我有点难过从哪里开始.在不同轮次的游戏,不同的运营商可以是可用的,例如+, -, *, and /,+ and -仅+ and *,或全部除+等

我是否正确地说我将有效地为每个运算符组合需要一个单独的算法(但是有很多,有20个或者其他什么)？如果是这样,那么我是否需要遍历网格中的每个数字,在数组中的每个其他数字上执行每个可用的运算符？这似乎过于混乱,但我不确定还有其他选择.此选项也不会遵循通过多个操作的任何特定路径(例如,如果我想制作7,我可以这样做,12 + 5 - 10如果这些是我在阵列中可用的唯一数字).

谁能给我一些关于从哪里开始这种问题的指示？

Answer 1

您正面临着一个更普遍的分区问题问题,即NP-Complete.

分区问题是:给定n数字,将它们分成两个(不同的)组,A并且B这样sum(A) = sum(B).现在,很容易看出,如果你有+, - 运算符和目标号0的问题 - 这基本上是同样的问题,并且从分区问题到你的问题有一个不可避免的减少.

由此我们可以得出结论你的问题也是NP-Hard,并且没有已知的多项式解决方案来解决你的问题.

替代方案是:

1. 蛮力(由@Sayakiss建议)
2. 根据操作符 - 您可能可以使用一些分支和绑定技术.
3. 对于分区问题,存在伪多项式动态编程解决方案,也可以在这里使用,至少对于某些情况.

对不起,如果这是个坏消息 - 但至少你不会寻找(大多数计算机科学家认为)不存在的东西