K个数之和问题的一种递归思路

2020-03-02

抽象

$\text{K-Sum问题}$是指,给定正整数$t$,给定一个有$n$个整数的集合$\mathbf{A}$,求$\mathbf{A}$的所有满足$\sum A_i = t, i=1,\dots,p$的有$k$个元素的子集$\mathbf{A_1},\mathbf{A_2},\dots,\mathbf{A_p}$.我们提出,可将原问题,记为$P(A,n,k,t)$,划分为两个子问题,记为$P(\mathbf{A_r}, n-1, k-1, t-a_1)$和$P(\mathbf{A_r}, n-1, k-1, t)$,其中集合$\mathbf{A_r}$是集合$\mathbf{A}$除去元素$a_1$得到的,然后分别求解这两个子问题,最后经过简单的归并步骤,可由子问题的解转换到原问题的解.

符号和约定

为方便起见,我们对下列表述和符号及其意义做出相应的约定:

搜索空间:$P(\mathbf{A},n,k,t)$的搜索空间具体是指集合$\mathbf{A}$的所有$k$元子集.它的子问题的搜索空间的定义也是如此类比.将$P(\mathbf{A},n,k,t)$的搜索空间记为$Q(\mathbf{A},t)$,$P(\mathbf{A_r}, n-1, k-1, t-a_1)$的搜索空间记为$Q(\mathbf{A_r,t-a})$,$P(\mathbf{A_r}, n-1, k-1, t)$的搜索空间记为$Q(\mathbf{A_r},t)$

解空间:或者叫解集,解集中的每个元素都是对象问题的解,$P(A,n,k,t)$的解集记做$S_1$,$P(\mathbf{A_r}, n-1, k-1, t-a_1)$的解集记做$S_2$,$P(\mathbf{A_r}, n-1, k-1, t)$的解集记为$S_3$.

命题

$\text{命题1:}$$Q(A,t)$中的每一个元素$q_{At}$,都必然能够在$Q(A_{r},t-a_1)$或者$Q(A_{r},a)$中找到一个元素$q_{A_r,t-a_1}$,使$q_{A_r,t-a_1}$并入$a_1$后与$q_{At}$等价.

$\text{命题2:}$$Q(A_r,t-a_1)$中的每一个元素$q_{A_r,t-a_1}$并入$a_1$后都等价于$Q(A,t)$中的一个元素$q_{A,t}$,$Q(A_r,t)$中的每个元素在$Q(A,t)$中都有对应元素与之等价.

$\text{命题3:}$如果$s \in S_2$,那么$s$并入$a_1$后等价于$S_1$中的一个元素.如果$s \in S_3$那么它必然等价于$S_1$中的一个元素.

数学讨论mathematicsalgorithm

奇怪的favicon问题

本站中期发展规划