一尘不染

编写算法来确定是否可以通过一组其他数字和特定运算符来达到目标​​数字?

algorithm

我试图学习有关算法设计的更多信息,并且给自己带来了创建一个简单的游戏的挑战,该游戏向用户提供数字数组,目标数字和一系列运算符(加,减,乘,除)
,也许平方根等等)。我需要做的是确定是否可以使用数组中的可用数字来确定目标数字。

我对从哪里开始感到有些困惑。在不同轮次的游戏,不同的运营商可以是可用的,例如+, -, *, and /+ and -+ and *,或所有除+

我的意思是说,对于每种运算符组合(无论有多少,无论是20个还是其他),我实际上都需要一个单独的算法?如果是这样,那么我是否需要遍历网格中的每个数字,对数组中的每个其他数字执行每个可用的运算符?这似乎太乱了,但是我不确定是否还有其他选择。此选项也不会遵循通过多个操作的任何特定路径(例如,如果我想进行操作7,那么12 + 5 - 10如果这些是数组中唯一可用的数字,则可以这样做)。

谁能给我一些从哪里开始这类问题的指点?


阅读 192

收藏
2020-07-28

共1个答案

一尘不染

您面临的是Partition
Problem
的更广泛的问题,即NP-
Complete

分区问题是:给定n数字,将它们分成两个(不同的)组AB使sum(A) = sum(B)。现在,很容易看出,如果您遇到+,-运算符和目标编号0的问题,这基本上是相同的问题,并且从分区问题到问题的减少都很大。

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

替代方法是:

  1. 蛮力(由@Sayakiss建议)
  2. 根据操作员的不同,您可能可以使用某些分支定界技术。
  3. 对于分区问题,至少在某些情况下,也可以在这里使用伪多项式动态规划解决方案

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

2020-07-28