【摘要】 <正> 1.导言子集和问题可描述如下:给定n个正整数W=（w₁,w₂,…,w_n）和正整数M,要求寻找这样一个子集I{1,2,…,n),使得∑w_i=M,i∈I。子集和问题属于NP完全问题,直接的枚举搜索可能遍历问题的所有2ⁿ个解空间,即直接搜索最坏情况下的时间复杂性为O（2ⁿ）。由于求解该问题的指数时间复杂性,子集和问题在信息密码学领域和数论研究中具有极重要的应用。因此,采用算法设计策略降低求解子集和问题过于庞大的计算量,具有重要的理论和实际意义。更多还原

【Abstract】 Due to the importance of the subset sum problem in cryptosystem,in the past two decade,much effort has been done in order to find techniques that could lead to practical algorithms with reasonable running time- Based on the two-list four-table algorithm,this paper proposes an improved algorithm for the solution of subset sum problem. To find a solution for the n-element subset problem,the proposed algorithm needs O(2^n/2-ε) memory, 1≤ε≤εn/4,and in O(ε(2^n/2) time. The theoretic analysis and the computational experiments show that our proposed algorithm can solve the subset problem instances that can’t be solved before,thus it is an improved result over the past researches.更多还原