数字组合算法

Question

编写一个给定一串数字和一个目标值的函数，打印出数字之间放置+和*的位置，以便它们与目标值精确组合。请注意，可能有多个答案，打印哪一个并不重要。

实例：

"1231231234",11353 -> "12*3+1+23*123*4" 
"3456237490",1185 -> "3*4*56+2+3*7+490" 
"3456237490",9191 -> "no solution" 

Answer 1

这可以通过回溯或通过动态规划来解决。

Answer 2

如果您有一个N位数值，那么+或*操作符有N-1个可能的位置。所以蛮力，有3 ^（N-1）的可能性。测试所有这些都是低效的。

但是

你的例子都是10位数。 3^9 = 19683，所以蛮力就是FINE！不需要任何爱好者。

因此，您只需遍历所有19683个案例，每次构建该案例的字符串并评估表达式。评估表达是一项直截了当的任务。迭代很简单（只需使用递增值，可以通过（i％3）读取第一个槽的状态，这会给出“无运算符”，“+”或“*”，第二个槽的状态为/ 3）％3，第三个插槽的状态为（i/9）％3等等。）

即使使用原始解析代码，CPU也很快。

蛮力选项在大约20位数字后开始变得难看，而且您必须切换到更加聪明。

Answer 3

的“聪明”的方法（使用动态编程）基本上是这样的：

对于原始串的每个串，找出它可以创建所有可能的值。 （例如，在您的第一个示例中，“12”可以变为1 + 2 = 3或1 * 2 = 2）

可能有很多不同的组合，但其中许多组合会重复。 （另外，你应该忽略所有大于目标的组合）。因此，当您添加“+”或“*”时，可以将它想象为将字符串的两个子字符串组合在一起。 （并且由于每个子字符串都有可能的值，因此可以看到这种组合是否可行）

这些值可以以类似方式生成：尝试以各种可能方式分割子字符串，并将每个半字符中的不同值的子串。

然后，“状态”的总数就像| S |^2 *目标 - 对于您的示例，它比012选择差比蛮力方法。但是如果你有一串长度为1000和目标为5000的字符串，那么问题就可以通过动态编程来解决。

Answer 4

Google Code Jam去年有这个问题的扩展版本（在Round 1C），称为丑陋的数字。您可以访问该链接，然后单击“比赛分析”获取解决该问题的一些方法，并将其扩展到大量的数字。

Answer 5

如果这是针对游戏程序员的位置，请勿使用暴力破解方法。我做到了，但几年前却失败了。后来从内部的人那里听说，动态编程方法就是获得这份工作的人。