數字組合算法

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

如果這是針對遊戲程序員的位置，請勿使用暴力破解方法。我做到了，但幾年前卻失敗了。後來從內部的人那裏聽說，動態編程方法就是獲得這份工作的人。