我遇到了一个棘手的问题。考虑到:A = [a1,a2，…an](长度为"n"的正整数列表)r(正整数)
查找{*， +}的列表运营商0 =[1, 2，…-1]因此，如果我们将这些运算符放在"A"的元素之间，结果表达式的值将为"r"。只需要一个解决方案。
例如ifA = [1,2,3,4]R = 14然后0 = [*， +， *]
我通过一些优化实现了一个简单的递归解决方案，但当然它是指数O(2^n)时间，所以对于长度为40的输入，它可以工作很长时间。
我想问你们是否知道这个的次指数解?
A的元素在0-10000之间，R可以任意大
设A、B为正整数。则A + B≤A &倍;1.
这个小事实可以用来构造一个非常有效的算法。
让我们定义一个图。图节点对应于操作列表，例如[+，×， +， +， ×]。图节点X到图节点Y存在一条边，如果Y可以通过将单个+改为&次得到;图中[+，+，…]对应的节点有一个源。, +]。
现在从源节点执行宽度优先搜索，并在此过程中构建图。例如，当展开一个节点[+，×， +， +， ×]时，您(可以选择构造它)连接到节点[×， ×， +， +， ×]， [+， ×， +， ×]，和[+，×， +， ×]。如果计算结果大于r + k(O)，则不要展开到节点，其中k(O)是操作列表O中+的个数。这是因为答案开头的事实中有"+ 1"——考虑a = [1,1,1,1,1]， r = 1的情况。
这种方法使用O(n 2n)时间和O(2n)空间(两者都可能是非常松散的最坏情况边界)。这仍然是一个指数算法，但是我想你会发现它对于非险恶输入的表现非常合理。(我怀疑这个问题是np完全的，这就是为什么我对这个"非邪恶输入"转义子句很满意。)
的O (rn ^ 2) - O (rn)讨论DP方法。如果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] *…* [n]
我们称由前i个数组成的a[]的"前缀"为p [i]。如果对P[i]上的每一个0 <= i <= n-1记录P[i]上某公式所能达到的值<= r的完备集，那么基于上述，我们就可以很容易地计算出P[n]所能达到的值<= r的完备集。具体来说，设X[i][j]为一个真值或假值，表示前缀P[i]是否可以达到值j。(X[][]可以存储为一个大小为n -(r+1)位图的数组。)然后我们要做的是计算X[n][r]，如果r可以通过a[]上的某个公式得到，则为真，否则为假。(X[n][r]还不是完整的答案，但它可以用来得到答案。)
X[1][a[1]] = true。对于任意2 <= i <= n和0 <= j <= r，我们可以使用
计算X[i][j]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进行比较，并返回真或假。在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]为真，则问题有一个解决方案(满足公式)，我们可以在O(n^2)时间内重建一个解决方案，通过追溯DP表，从X[n][r]开始，在每个位置寻找使当前位置假设值为"真"的任何项——即任何为真的项。(我们可以通过每个(i, j)组合存储不止一个比特来更快地完成这个重建步骤——但是由于r被允许是"任意大的"，并且这种更快的重建不会提高整体时间复杂度，因此使用每个DP表项使用最少比特的方法可能更有意义)所有令人满意的解决方案都可以这样重建。通过回溯所有真实的项，而不是只选一个——但它们可能是指数级的。
明显变化有两种方法可以加速单个X[i][j]值的计算。首先，因为所有的项都与||结合在一起，我们可以在结果为真时立即停止，因为没有后面的项可以再次使它为假。第二，如果在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]s at a time:对于k != j, X[i][j]独立于X[i][k]，所以如果我们使用bitset来存储这些值，我们可以使用简单的按位或操作并行计算8,32或64个(或者更多，使用SSE2等)。也就是说，我们可以计算X[i][j]， X[i][j+1]，…， X[i][j+31]并行，将它们或成结果，然后并行计算它们的第二项，并将它们或成，以此类推。我们仍然需要以这种方式执行相同数量的减法，但乘积都是相同的，因此我们可以将乘法次数减少8/32/64倍——当然，还可以减少内存访问次数。OTOH，这使得上一段的第一个优化更难完成——你必须等到8/32/64位的整个块变成真的，才能停止迭代。
0:[]中的零可以让我们提前停止。具体来说，如果我们刚刚计算了X[i][r]对于某些i <N，并且发现>和在a[]中位置I右边的任何地方都有一个0，那么我们可以停止:我们已经有了一个计算前I个数为r的公式，我们可以用这个0来"消灭"位置I右边的所有数字通过创建一个包含所有数字的大乘积项
:任何包含值1的a[]条目的一个有趣的特性是，它可以移动到a[]中的任何其他位置，而不会影响是否存在解。这是因为每一个令人满意的公式要么在这个1的至少一侧有一个*，在这种情况下，它乘以其他项在那里没有影响，同样在其他地方也没有影响;或者它的两边都有一个+(想象在第一个位置之前和最后一个位置之后都有额外的+符号)，在这种情况下，它可能会被添加到任何地方。
所以，在做其他操作之前，我们可以安全地将所有1的值分流到a[]的末尾。这样做的重点是现在我们根本不需要计算这些X[][]行，因为它们只会以一种非常简单的方式影响结果。假设有m <a[]里有N个1，我们把它移到了末尾。之后计算m> 的1组成，那么至少1必须被"加"——它们不能全部乘以其他项。)
下面是另一种可能有用的方法。它有时被称为"中间相遇"算法，并在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))作为渐近复杂度，因为实际上最大的项占主导地位。
您需要做一些簿记来实际恢复+'s和*'s，我省略了它们以简化解释。