这是一个
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
r
可以有多大? - kraskevichn
、r
和a[i]
值的约束条件是大致(或更精确)是什么? - kraskevich