首页 > 一道算法题求教

一道算法题求教

在效率尽可能高的情况下解答:
在给定一个由n个整数构成的集合S和另一个整数x时,判断出S中是否存在有任意个其和等于x的元素?


通过维基百科和stackoverflow 知道这是subset problem

采用动态规划进行求解:
1. 设集合x的最小和以及最大和分别是min,max,设一个二维数组 m[n][max-min]
m[i][s] = 1表示找到了x[1...i]的一个子集和等于s

因此初试条件:m[1][x1] = 1
递推关系:
m[2][x] = 1 if m[1][x-x2] = 1, 否则 m[2][x] = m[1][x]


任意个其和?应该说有多少种方案吧!典型组合数学,去翻翻书就知道了.

【热门文章】
【热门文章】