algorithm - 将 "sum"和 "multiply"运算符放在给定整数列表的元素之间，以便表达式产生指定值

Question

有人问我一个棘手的问题。鉴于: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 可以任意大

Answer 1

Let A and B be positive integers. Then A + B ≤ A × B + 1.

这个小事实可以用来构建一个非常有效的算法。

让我们定义一个图。图节点对应操作列表，例如[+, ×, +, +, ×]。如果可以通过将X中的单个+变为×来获得Y，则从图节点X到图节点Y有一条边。该图在对应于[+，+，...，+]的节点处有一个源.

现在从源节点执行广度优先搜索，边走边构建图。例如，当扩展节点 [+, ×, +, +, ×] 时，您(可选地构造 then)连接到节点 [×, ×, +, +, ×], [+, ×, ×, +, ×] 和 [+, ×, +, ×, ×]。如果评估结果大于 r + k(O)，则不要扩展到节点，其中 k(O) 是操作列表 O 中 + 的个数。这是因为“+ 1”在答案开头的事实 - 考虑 a = [1, 1, 1, 1, 1], r = 1 的情况。

此方法使用 O(n 2ⁿ) 时间和 O(2ⁿ) 空间(其中两者都可能是非常宽松的最坏情况界限)。这仍然是一种指数算法，但我认为您会发现它对于非恶意输入的表现非常合理。 (我怀疑这个问题是 NP 完全问题，这就是为什么我对这个“非恶意输入”转义条款感到满意。)