算法记录:
给定一个数组x,每个元素都是正整数,找出其中满足条件“求和等于y”的所有子数组。(简化问题,每个元素都不相等)
x=[x1,...,xn],暴力搜索,复杂度O(2^n),不可取。
动态规划思路。构建矩阵A:
- A[j,i]=k,如果k!=-1,表示数组[x1,...,xk]包含求和等于j的子数组,如果k=-1,表示数组[x1,...,xi]不包含求和等于k的子数组。
- 最终需要返回能构成求和等于y的子数组,则先看A[y, :]行,检测是否有不等于-1的值,如果有,例如A[y,z],则说明[A1, ..., Az]包含目标子数组,并且Az是其中的元素。
接下来迭代地求解求和等于y-xz的子数组。
算法实现如下,下面的算法只找出了一个子数组,稍作修改可以找出所有子数组。
矩阵A非常稀疏,可以通过优化的数据结构减少开销。
import numpy as np
x = [1,2,3,4]
n = len(x)
M = sum(x) + 1
A = (np.ones(M * n)*-1).reshape(M, n)
## 计算矩阵A
i = 0
A[x[i], i] = i
for i in range(1, n):
for j in range(M):
if A[j, i - 1] != -1 and j + x[i] < M:
A[j + x[i], i] = i
A[x[i] , i] = i
print(A)
y=4
## 寻找子数组
res = []
while y > 0:
idss = (A[y]>=0)
if idss.any():
idss = A[y, idss]
ids = int(idss[0])
res.append(ids)
y = int(y - x[ids])
else:
break
print(res)