这是一个创建于 2125 天前的主题，其中的信息可能已经有所发展或是发生改变。
Given an array with positive integers and another integer for example {7 2 4} and 9, you are required to generate an equation, by inserting operator add ("+") and minus ("-") among the array. The left side of equation are consist of the array and the right side of equation is the integer. Here the result is 7-2+4=9.
无意间在 http://www.raychase.net/1285 里看到的，作者没去说这题的思路。除了穷举外，还有什么好方法呢 🤔
 |
1
geelaw 2019-01-21 17:16:44 +08:00 via iPhone
这个问题（很直白地）是 subset sum，数字都很小的时候用最常见的那个 dynamic programming。此外还可以用 @ChaoXu 之前的研究结果。
该问题是 NP-hard，所以不要期待一个多项式时间的算法。 |
 |
3
guyeu 2019-01-21 17:29:14 +08:00
emmmm 这个问题比 subset sum 多了个限定条件，感觉用二叉树+剪枝可以试试。
|
 |
5
qinyusen 2019-01-21 18:21:25 +08:00
|
 |
7
aijam 2019-01-22 05:06:29 +08:00
|
Select Language