aal*_*mos 13 algorithm math combinations
我遇到了一个棘手的问题.给定: A = [a1,a2,... an](长度为"n"的正整数列表) r(正整数)
找到{*,+}运算符列表O = [o1,o2,... on-1],这样如果我们将这些运算符放在"A"元素之间,则生成的表达式将计算为"r".只需要一种解决方案.
因此,例如,如果A = [1,2,3,4] r = 14则O = [*,+,*]
我已经实现了一个简单的递归解决方案和一些优化,但当然它是指数O(2 ^ n)时间,因此对于长度为40的输入,它可以工作多年.
我想问你们有没有人知道这个指数的解决方案吗？
A的更新元素在0-10000之间,r可以任意大
设A和B为正整数.然后A +B≤A×B + 1.
这个小事实可以用来构建一个非常有效的算法.
我们来定义一个图表.图节点对应于操作列表,例如,[+,×,+,+,×].如果可以通过在X中将单个+改变为a来获得Y,则从图节点X到图节点Y存在边缘.该图在节点处具有对应于[+,+,...,+]的源. .
现在,从源节点执行广度优先搜索,随时构建图形.例如,当扩展节点[+,×,+,+,×]时,您(可选地构造然后)连接到节点[×,×,+,+,×],[+,×,×,+, ×]和[+,×,+,×,×].如果评估结果大于r + k(O),则不要扩展到节点,其中k(O)是操作列表O中的+的数量.这是因为"+ 1"中的在答案开始时的事实 - 考虑a = [1,1,1,1,1],r = 1的情况.
这种方法使用O(n 2 n)时间和O(2 n)空间(两者都可能是非常宽松的最坏情况边界).这仍然是一个指数算法,但我认为你会发现它对非险恶的输入非常合理.(我怀疑这个问题是NP完全的,这就是为什么我对这个"非险恶的输入"逃避条款感到满意.)