在给定的整数列表中，放置“求和”和“乘法”运算符，使表达式的结果为指定值。

Question

在给定的整数列表中，放置“求和”和“乘法”运算符，使表达式的结果为指定值。

algorithmmathcombinations

13

我遇到了一个麻烦的问题。给定： 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可以任意大

- aalmos

我确实想不起来有哪个算法可以做到这一点，但我相当确定如果这是一个现实世界的问题，启发式算法会非常有帮助。我可以想出几种方法，但是正如启发式算法所做的那样，它只对可能输入的子集有用，并且当然仍然存在一个无限集合的输入，其时间复杂度仍为 O(2^n)。 - Gerino

1

r 可以有多大？ - kraskevich

你所给出的A和r是否一定存在解决方案？ - Zéychin

1

n、r和a[i]值的约束条件是大致（或更精确）是什么？ - kraskevich

是的，这绝对是合理的。 - aalmos

显示剩余7条评论

3个回答

2

这是一个O(rn^2)时间复杂度，O(rn)空间复杂度的动态规划方法。如果r<<2^n，则其最坏情况的表现将优于指数级别的分支定界方法，尽管在许多实例中后者仍然可能更快。这是伪多项式时间，因为它需要与其输入的一部分（r）的值成比例的时间，而不是其大小（其大小将是log2(r)）。具体来说，它需要rn 位的内存，因此对于rn < 1,000,000,000和n < 1000（例如n = 100，r = 10,000,000），它应该在几秒钟内给出答案。

关键观察是涉及所有n个数字的任何公式都有一个由i个因子组成的最终项，其中1 <= i <= n。也就是说，任何公式必须属于以下n种情况之一：

(前n-1个数的公式) + a[n]
(前n-2个数的公式) + a[n-1] * a[n]
(前n-3个数的公式) + a[n-2] * a[n-1] * a[n]
...
a[1] * a[2] * ... * a[n]

这段文本描述了一种数学公式，其中包含了一系列的计算步骤。每一步都是基于前面的结果进行计算，并且包含了当前位置上的数字。最后一步计算的结果是将所有数字相乘的积。

让我们称a[]的前i个数字组成的“前缀”为P[i]。如果我们记录每个0 <= i <= n-1的值集合，这些值是通过一些公式在P[i]上可以达到的（即“the complete set of values <= r that can be reached by some formula on P[i]”），那么基于以上，我们就可以很容易地计算出P[n]可以达到的完整值集合。具体而言，令X[i][j]为一个true或false值，表示前缀P[i]是否能够达到值j。（X[][]可以存储为大小为n*(r+1)的位图数组。）然后我们要做的就是计算X[n][r]，如果r可以通过a[]的某个公式达到，则该值为true，否则为false。（X[n][r]还不是完整的答案，但它可以用来得到答案。）

X[1][a[1]] = true。对于所有其他的j，X[1][j] = false。对于任意2 <= i <= n和0 <= j <= r，我们可以使用...（原文未完）

X[i][j] = X[i - 1][j - a[i]]               ||
          X[i - 2][j - a[i-1]*a[i]]        ||
          X[i - 3][j - a[i-2]*a[i-1]*a[i]] ||
          ...                              ||
          X[1][j - a[2]*a[3]*...*a[i]]     ||
          (a[1]*a[2]*...*a[i] == j)

请注意，最后一行是一个等式测试，它将P[i]中所有i个数字的乘积与j进行比较，并返回true或false。在X[i][j]的表达式中，有i <= n个“项”（行），每个项可以在常数时间内计算出来（特别要注意的是，每行的乘法可以在常数时间内建立起来），因此计算单个值X[i][j]可以在O(n)时间内完成。要找到X[n][r]，我们需要为每个1 <= i <= n和每个0 <= j <= r计算X[i][j]，因此总共需要O(rn^2)的工作量。（严格来说，如果我们使用记忆化而不是自底向上的方法，可能不需要计算所有这些表条目，但许多输入都需要我们计算其中的大部分，因此后者可能会快一些，差不多只有一个小常数因子。此外，记忆化方法需要为每个DP单元格保留一个“已处理”标志——当每个单元格只有1位时，这会使内存使用量翻倍！）

重构一个解决方案

如果X [n] [r]为真，则问题有解（满足公式），我们可以通过跟踪DP表回溯，从X [n] [r]开始，在每个位置寻找使当前位置能够假定“true”的任何项 - 也就是说，任何真正的项。（我们可以通过存储每个（i，j）组合的不止一个比特来更快地执行此重构步骤 - 但由于允许r为“任意大”，而这种更快的重构不会改善总体时间复杂度，因此使用每个DP表条目最少的方法可能更有意义。）通过回溯所有真实术语而不仅仅选择任何一个，可以以这种方式重建所有满足的解决方案 - 但可能存在指数数量的解决方案。

加速

有两种方式能够加速计算个别 X[i][j] 值。首先，因为所有的项都与 || 相结合，所以一旦结果变为 true，我们就可以停止计算，因为后面的任何项都不可能再使其变为 false。其次，如果在 i 的左侧没有零存在，那么一旦最终数字的乘积大于 r，我们就可以停止计算，因为此后这个乘积不可能再减少。

当 a[] 中没有零时，第二种优化在实践中很可能非常重要: 它有潜力将内部循环的迭代次数大大降低，甚至比完整的 i-1 次迭代还要小得多。实际上，如果 a[] 不包含任何零，其平均值为 v，在计算特定的 X[i][j] 值的前 k 个项后，乘积约为 v^k -- 因此，内部循环迭代次数(项)的平均数量从 n 降至 log_v(r)=log(r)/log(v)。这可能远小于 n，这种情况下，该模型的平均时间复杂度将降至 O(rn*log(r)/log(v))。 [编辑：事实上，以下优化可以节省乘法的计算:)] 一次可以计算8/32/64个X[i][j]：对于k != j，X[i][j]独立于X[i][k]，因此如果我们使用位集来存储这些值，我们可以使用简单的按位OR运算并行计算8、32或64个（甚至可能更多，使用SSE2等）。也就是说，我们可以并行计算X[i][j]的第一个项、X[i][j+1]、...、X[i][j+31]，将它们OR到结果中，然后并行计算其第二项并进行OR操作，以此类推。虽然我们仍然需要执行相同数量的减法，但乘积都是相同的，因此我们可以将乘法的数量降低8/32/64倍，当然，还可以减少内存访问的次数。另一方面，这使得前一段落中的第一个优化变得更加困难--必须等待整个8/32/64位块变为真才能停止迭代。

零：

零：在a[]中出现的零可以让我们提前停止。具体来说，如果我们刚刚计算出某个i < n的X[i][r]为真，并且在位置i右侧的任何地方都有一个零，那么我们可以停止：我们已经有了一个关于前i个数字的公式，它的值为r，我们可以使用这个零来“消除”所有在位置i右侧的数字，通过创建一个包含所有这些数字的大乘积项。

一：任何包含值1的a[]条目的有趣属性是，它可以移动到a[]中的任何其他位置，而不影响是否存在解决方案。这是因为每个满足的公式都在这个1的至少一侧有一个*，在这种情况下它会乘以另一个项并在那里没有影响，并且同样不会在任何其他地方产生影响；或者它在两侧都有一个+（想象一下在第一个位置和最后一个位置之前和之后额外添加+符号），在这种情况下，它可以添加到任何地方。

因此，在做任何其他操作之前，我们可以安全地将a[]中的所有1值移至末尾。这样做的目的是我们现在不必评估X[][]中这些行的值，因为它们只以非常简单的方式影响结果。假设a[]中有m

- j_random_hacker

非常感谢您提供如此详细的解释和优美的DP解决方案，我真的很喜欢。不过很遗憾，在我的确切情况下，我认为它无法应用，因为数字r实在太大了（大到我必须使用GMP来处理它——我明白我没有在问题中提到这一点）。如果您愿意，我可以向您发送测试用例。 - aalmos

@aalmos：啊，那好吧。我还是很想看看这个实例。你可以选择一个适中的数字m < r（比如一百万左右），并解决所有输入（a[]和r）已被模m减少的问题：如果原问题有任何解，则必须存在此解。然后，您可以使用Xreduced[i][j mod m]“伪造”Xorig[i][j]，并对原始问题进行详尽的重建，在其他边界告诉您解决方案无法工作时停止递归。如果Xreduced[][]的“false positive”“true”值足够稀疏，则这将击败暴力破解。 - j_random_hacker

可能最好进行k>1次运行，使用不同（且互质的）m值：然后您可以使用Xreduced1 [i] [j mod m1]＆Xreduced2 [i] [j mod m2]＆...＆Xreducedk [i] [j mod mk]来伪造Xorig [i] [j]。这似乎是一种更有效的方法，可以将“错误”值放入Xorig [i] [j]中，因为只需要一个m值就可以在该位置上获得“错误”值-但是另一方面，在重建期间必须保留所有k个位图，因此每个m值的大小约为1/k。 - j_random_hacker

最后一个想法（暂时的 :-P）：首先像以前一样构建X[][]，直到某个最大值m（比如一百万）。然后启动一个“正常”的暴力指数时间搜索，从a[]的末尾开始向后构建公式。假设你当前使用a[]的最后k个数字并且值为y的公式；那么如果r - y < m，则可以测试X[n-k][r-y]并立即知道是否可能完成此公式！也就是说，您可以使用DP表来“扩大”您的暴力搜索目标。这可能比我上次的建议更容易和更实用。 - j_random_hacker

2

这里有另一种可能有用的方法，有时被称为“meet-in-the-middle”算法，时间复杂度为O(n * 2^(n/2))。基本思路是这样的：假设n = 40，你知道中间的槽位是一个+，那么你可以暴力枚举每个侧面的N := 2^20种可能性。令A是长度为N的数组，存储左侧的可能值，同样地，令B是长度为N的数组，存储右侧的可能值。

然后，在将A和B排序之后，很容易高效地检查是否有任意两个数之和等于r（例如，对于A中的每个值，在B上进行二分查找，如果两个数组都已排序，则甚至可以在线性时间内完成）。这部分需要O(N * log N) = O(n * 2^(n/2))的时间。

现在，这一切都是假设中间的槽位是一个+。如果不是，那么它必须是一个*，你可以将中间的两个元素组合成一个（它们的乘积），将问题缩小到n = 39。然后你可以尝试同样的方法，以此类推。如果你仔细分析一下，应该会得到O(n * 2^(n/2))作为渐近复杂度，因为实际上最大的项是占主导地位的。

你需要做一些簿记工作来恢复+和*，这里为了简化说明而省略了。

- arghbleargh

我喜欢将中间两个数字组合在一起的想法。一个建议：虽然它不会改变整体复杂度，但你可以通过按照格雷码顺序遍历可能性，在O(2^(n/2))时间内生成每一侧的2^(n/2)个可能性列表，而不是O(n2^(n/2))时间。 - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Timothy Shields · Accepted Answer

让A和B是正整数。那么A + B ≤ A × B + 1。这个小事实可以用来构建一个非常有效的算法。

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

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

此方法使用O（n 2 ^ n）时间和O（2 ^ n）空间（两者都可能是非常松散的最坏情况下限）。但是我认为您会发现它对于非邪恶输入表现得非常合理。（我怀疑这个问题是NP完全的，这就是为什么我对这个“非邪恶输入”逃脱条款感到满意的原因。）