arrays - 检查特殊数组方程的子集总和

Question

我试图解决以下问题。

我们得到 N 和 A[0]

N <= 5000
A[0] <= 10^6 and even 
if i is odd then 
A[i] >= 3 * A[i-1]
if i is even
A[i]= 2 * A[i-1] + 3 * A[i-2]
element at odd index must be odd and at even it must be even.

我们需要最小化数组的总和。

我们得到一个 Q 数字

 Q <= 1000
 X<= 10^18

我们需要确定是否有可能从我们的数组中获得子集和 = X。

我尝试过的，

创建最小和数组很容易。只需遵循方程式和约束即可。

我所知道的子集和方法是动态编程，它具有时间复杂度 sum*sizeof(Array) 但由于 sum 可以大到 10^18，这种方法将不起作用。

我是否缺少任何方程关系？

标签： arraysalgorithmdata-structuressubset-sum

Answer 1

我们可以用一点数学来做到这一点：对不起，乳胶我不确定它是否可能在堆栈上？

让X_n是序列（与您的定义相同A）

我认为X_0是积极的。

因此序列是严格递增的，并且最小化发生在X_{2n+1} = 3X_{2n}

我们可以计算X_{2n}和X_{2n+1}

v_0 = 
X0
X1

v_1 = 
X1
X2

v_0和之间的关系v_1是

M_a = 
0 1
3 2

v_1和之间的关系v_2是

M_b = 
0 1
0 3

v_2因此和之间的关系v_0是

M = M_bM_a = 
3 2
9 6

我们推断

v_{2n} = 
X_{2n}
X_{2n+1}

v_{2n} = M^n v_0

遵循经典的对角化......我们（除非弄错）得到

X_{2n} = 9^n/3 X_0 + 2*9^{n-1}X_1
X_{2n+1} = 9^n X_0 + 2*9^{n-1}/3X_1

回想一下，X_1 = 3X_0因此

X_{2n} = 9^n X_0
X_{2n+1} = 3.9^n X_0

现在，如果我们表示我们想要以 9 为基数检查的总和，我们得到

       9^{n+1}        9^n
___   ________  ___   ___
      X^{2n+2}        X^2n

在这些X^{2n}地方我们只能放置一个 1 或一个 0（这意味着我们2n-th从 中获取元素A）我们也可以将 a3放在这个地方的X^{2n}位置，这意味着我们2n+1th从数组中选择了元素

所以我们只需要分解 base9中的数字，并检查它的所有数字或其中一个0,1或3（以及它的前导数字是否超出我们的数组范围......）